In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work, we considered acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. One of the main results of ESA2016 was that no acknowledgment-based protocol can be in equilibrium. In fact, it seems that many natural acknowledgment-based protocols fail to prevent users from unilaterally switching to persistent protocols that always transmit with probability 1. It is therefore natural to ask how powerful a protocol must be so that it can beat persistent deviators. In this paper we consider age-based protocols, which can be described by a sequence of probabilities of transmitting in each time step. Those probabilities are given beforehand and do not change based on the transmission history. We present a 3-player age-based protocol that can prevent users from unilaterally deviating to a persistent protocol in order to decrease their expected transmission time. It is worth noting that the answer to this question does not follow from the results and proof ideas of ESA2016. Our protocol is non-trivial, in the sense that, when all players use it, finite expected transmission time is guaranteed. In fact, we show that this protocol is preferable to any deadline protocol in which, after some fixed time, attempt transmission with probability 1 in every subsequent step. An advantage of our protocol is that it is very simple to describe, and users only need a counter to keep track of time. Whether there exist @math -player age-based protocols that do not use counters and can prevent persistence is left as an open problem for future research.
@cite_18: Backoff protocols are probably the most widely used protocols for contention resolution in multiple access channels. In this paper, we analyze the stochastic behavior of backoff protocols for contention resolution among a set of clients and servers. each server being a multiple access channel that deals with contention like an ethernet channel. We use the standard model in which each client generates requests for a given server according to a Bernoulli distribution with a specified mean. Theclient?server request rateof a system is the maximum over all client?server pairs (i,j) of the sum of all request rates associated with either clientior serverj. (Having a subunit client?server request rate is a necessary condition for stability for single-server systems.) Our main result is that any superlinear polynomial backoff protocol is stable for any multiple-server system with a subunit client?server request rate. Our result is the first proof of stability for any backoff protocol for contention resolution with multiple servers. (The multiple-server problem does not reduce to the single-server problem, because each client can only send a single message at any step.) Our result is also the first proof thatanyweakly acknowledgment based protocol is stable for contention resolution with multiple servers and such high request rates. Two special cases of our result are of interest. Hastad, Leighton, and Rogoff have shown that for a single-server system with a subunit client?server request rate anymodifiedsuperlinear polynomial backoff protocol is stable. These modified backoff protocols are similar to standard backoff protocols but require more random bits to implement. The special case of our result in which there is only one server extends the result of Hastad, Leighton, and Rogoff to standard (practical) backoff protocols. Finally, our result applies to dynamic routing in optical networks. Specifically, a special case of our result demonstrates that superlinear polynomial backoff protocols are stable for dynamic routing in optical networks.
@cite_22: We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expected delay (time to get serviced) of every message is O(log n ) when messages are generated according to a Bernoulli distribution with generation rate up to about 1 10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1 e , and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1 e . (Each message constitutes a new user.) To achieve (a), we first show how to simulate (b) using n synchronized users, and then show how to build the synchronization into the protocol.
@cite_7: 
@cite_8: In September 1968 the University of Hawaii began work on a research program to investigate the use of radio communications for computer-computer and console-computer links. In this report we describe a remote-access computer system---THE ALOHA SYSTEM---under development as part of that research program and discuss some advantages of radio communications over conventional wire communications for interactive users of a large computer system. Although THE ALOHA SYSTEM research program is composed of a large number of research projects, in this report we shall be concerned primarily with a novel form of random-access radio communications developed for use within THE ALOHA SYSTEM.
@cite_3: This paper was originally distributed informally as ARPA Satellite System Note 8 on June 26, 1972. The paper is an important one and since its initial limited distribution, the paper has been frequently referenced in the open literature, but the paper itself has been unavailable in the open literature. Publication here is meant to correct the previous gap in the literature. As the paper was originally distributed only to other researchers intimately familiar with the area covered by the paper, the paper makes few concessions to the reader along the lines of introductory or tutorial material. Therefore, a bit of background material follows. ALOHA packet systems were originally described by Abramson ("The ALOHA System--Another Alternative for Computer Communication," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37, 1970, pp. 281--285). In an ALOHA a single broadcast channel is shared by a number of communicating devices. In the version originally described by Abramson, every device transmits its packets independent of any other device or any specific time. That is, the device transmits the whole packet at a random point in time; the device then times out for receiving an acknowledgment. If an acknowledgment is not received, it is assumed that a collision occured with a packet transmitted by some other device and the packet is retransmitted after a random additional waiting time (to avoid repeated collisions). Under a certain set of assumptions, Abramson showed that the effective capacity of such a channel is 1 (2e). Roberts in the present paper investigates methods of increasing the effective channel capacity of such a channel. One method he proposes to gain in capacity is to consider the channel to be slotted into segments of time whose duration is equal to the packet transmission time, and to require the devices to begin a packet transmission at the beginning of a time slot. Another method Roberts proposes to gain in capacity is to take advantage of the fact that even though packets from two devices collide in the channel (i.e., they are transmitted so they pass through the channel at overlapping times), it may be possible for the receiver(s) to "capture" the signal of one of the transmitters, and thus correctly receive one of the conflicting packets, if one of the transmitters has a sufficiently greater signal than the other. Roberts considers the cases of both satellite and ground radio channels.
@cite_24: This paper analyzes the worst-case performance of randomized backoff on simple multiple-access channels. Most previous analysis of backoff has assumed a statistical arrival model.For batched arrivals, in which all n packets arrive at time 0, we show the following tight high-probability bounds. Randomized binary exponential backoff has makespan Θ(nlgn), and more generally, for any constant r, r-exponential backoff has makespan Θ(nloglgr n). Quadratic backoff has makespan Θ((n lg n)3 2), and more generally, for r>1, r-polynomial backoff has makespan Θ((n lg n)1+1 r). Thus, for batched inputs, both exponential and polynomial backoff are highly sensitive to backoff constants. We exhibit a monotone superpolynomial subexponential backoff algorithm, called loglog-iterated backoff, that achieves makespan Θ(nlglg n lglglg n). We provide a matching lower bound showing that this strategy is optimal among all monotone backoff algorithms. Of independent interest is that this lower bound was proved with a delay sequence argument.In the adversarial-queuing model, we present the following stability and instability results for exponential backoff and loglog-iterated backoff. Given a (λ,T)-stream, in which at most n=λT packets arrive in any interval of size T, exponential backoff is stable for arrival rates of λ=O(1 lgn) and unstable for arrival rates of λ=Ω(lglgn lgn); loglog-iterated backoff is stable for arrival rates of λ=O(1 (lglgn )) and unstable for arrival rates of λ=Ω(1 lgn). Our instability results show that bursty input is close to being worst-case for exponential backoff and variants and that even small bursts can create instabilities in the channel.
Perhaps the most famous multiple-access communication protocol is the (slotted) ALOHA protocol @cite_8 @cite_3 . Follow-up papers study the efficiency of multiple-access protocols for packets that are generated by some stochastic process (see e.g. @cite_22 @cite_18 @cite_7 ), or worst-case scenarios of bursty inputs @cite_24 .