{rfName}
Un

Indexed in

License and use

Citations

153

Altmetrics

Analysis of institutional authors

Fernández AAuthor

Share

October 10, 2022
Publications
>
Article
No

Universal-stability results and performance bounds for greedy contention-resolution protocols

Publicated to:Journal Of The Acm. 48 (1): 39-69 - 2001-01-01 48(1), DOI: 10.1145/363647.363677

Authors: Andrews M; Awerbuch B; Fernández A; Leighton T; Liu Z; Kleinberg J

Affiliations

Bell Labs., Lucent Technologies, United States, Bell Laboratories, 600-700 Mountain Avenue, Murray Hill, NJ 07974, United States - Author
Cornell University, Ithaca, NY, United States, Department of Computer Science, Cornell University, Ithaca, NY 14853, United States - Author
Johns Hopkins University, Baltimore, MD, United States, Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218, United States - Author
Massachusetts Inst. of Technology, Cambridge, MA, United States, Esc. Sup. de Cie. Exp./Technologia, Universidad Rey Juan Carlos, 28933 Mostoles, Madrid, Spain - Author
Massachusetts Inst. of Technology, Cambridge, MA, United States, Institute of Computing Technology, Academia Sinica, Beijing, China - Author
Massachusetts Inst. of Technology, Cambridge, MA, United States, Laboratory for Computer Science, Massachusetts Inst. of Technology, Cambridge, MA 01219, United States - Author
See more

Abstract

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability - will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of networks (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

Keywords

Adversarial queueing theoryAlgorithmsComputational complexityEnd-to-end delayNetwork protocolsNetwork stabilityPacket networksPacket schedulingPacket switchingPoisson distributionPolynomial approximationProbabilityQueueing theoryRandom number generationRandom processes

Quality index

Bibliometric impact. Analysis of the contribution and dissemination channel

The work has been published in the journal Journal Of The Acm due to its progression and the good impact it has achieved in recent years, according to the agency WoS (JCR), it has become a reference in its field. In the year of publication of the work, 2001, it was in position 12/75, thus managing to position itself as a Q1 (Primer Cuartil), in the category Computer Science, Software Engineering.

From a relative perspective, and based on the normalized impact indicator calculated from the Field Citation Ratio (FCR) of the Dimensions source, it yields a value of: 29.1, which indicates that, compared to works in the same discipline and in the same year of publication, it ranks as a work cited above average. (source consulted: Dimensions Jul 2025)

Specifically, and according to different indexing agencies, this work has accumulated citations as of 2025-07-21, the following number of citations:

  • Scopus: 150

Impact and social visibility

From the perspective of influence or social adoption, and based on metrics associated with mentions and interactions provided by agencies specializing in calculating the so-called "Alternative or Social Metrics," we can highlight as of 2025-07-21:

  • The use, from an academic perspective evidenced by the Altmetric agency indicator referring to aggregations made by the personal bibliographic manager Mendeley, gives us a total of: 35.
  • The use of this contribution in bookmarks, code forks, additions to favorite lists for recurrent reading, as well as general views, indicates that someone is using the publication as a basis for their current work. This may be a notable indicator of future more formal and academic citations. This claim is supported by the result of the "Capture" indicator, which yields a total of: 34 (PlumX).

With a more dissemination-oriented intent and targeting more general audiences, we can observe other more global scores such as:

  • The Total Score from Altmetric: 3.

Leadership analysis of institutional authors

This work has been carried out with international collaboration, specifically with researchers from: China; Timor-Leste; United States of America.