Contention resolution addresses the fundamental challenge of coordinating access by devices to a shared resource, which is typically modeled as a multiple access channel. Introduced with the development of ALOHA in the early 1970s [1], the problem of contention resolution remains relevant in WiFi networks [16], cellular networks [32], and shared-memory systems [8,24].
Our problem is described as follows. There are n → 2 devices present at the start of the system, each with a packet to send on the shared channel, and n is a priori unknown. For ease of presentation, we adopt a slight abuse of language by referring to packets sending themselves (rather than referring to devices that send packets). Time proceeds in discrete, synchronized slots, and each slot has size that can accommodate the transmission of a packet. For any fixed slot, the channel provides ternary feedback, allowing each packet to learn whether 0 packets were sent, 1 packet was sent (a success), or 2+ packets were sent (a collision). Sending on the channel is performed in a distributed fashion; that is, a priori there is no central scheduler or coordinator. Traditionally, the contention-resolution problem focuses on minimizing the number of slots until all n packets succeed, which is referred to as the makespan.
However, in many modern systems, collisions also have a significant impact on performance. In the standard cost model, each collision can be viewed as a wasted slot that increases the makespan by 1, since no packet can succeed. Yet, in many settings, a collision wastes more than a single slot, and we denote this cost by C. 3 This cost can vary widely across different systems. In intermittently-connected mobile wireless networks [36], failed communication due to a collision may result in the sender having to wait until the intended receiver is again within transmission range. For WiFi networks, a collision may consume time proportional to the packet size [6]. In shared memory systems, concurrent access to the same memory location can result in delay proportional to the number of contending processes [8]. Thus, makespan gives only part of the performance picture, since collisions may add to the time until all packets succeed.
In this work, we account for the cost of collisions, in addition to the makespan. As we discuss later (see Section 3), existing contention-resolution algorithms do not perform well in this setting. For instance, randomized binary exponential backoff (BEB) [30], arguably the most popular of all contention-resolution algorithms, incurs a collision cost of ε(n C), where C is the cost of a single collision. New ideas are needed to achieve better performance in this model.
Our work addresses the case where an n → 2 number of packets are active at the start of the system. There is no known upper bound on n a priori, and packets do not have identifiers. A packet is active if it is executing a protocol; otherwise, the packet has terminated. Each packet must be successfully sent in a distributed fashion (i.e., there is no scheduler or central authority) on a multiple access channel, which we now describe.
Multiple Access Channel. Time is divided into disjoint slots, where each slot is sized to accommodate a single packet. In any slot, a packet may send itself or it may listen. For any fixed slot, if no packet is sent, then the slot is empty; if a single packet is sent, then it is successful; and if two or more packets are sent, then there it is a collision and none of these packets is successful. A packet that transmits in a slot immediately learns of success or failure; if it succeeds, the packet terminates immediately. Any packet that is listening to a slot, learns which of these three cases occurred; this is the standard ternary feedback model. Likewise, for any slot, a packet that is sending can also determine the channel feedback; either the packet succeeded (which it learns in the slot) or it failed (from which the packet infers a collision occurred). Packets cannot send messages to each other, and no other feedback is provided by the channel.
Metrics. A well-known measure of performance in prior work is the makespan, which is the number of slots required for all n packets to succeed. An equivalent metric in the static case is, throughput, which is defined as the time for n successes divided by the makespan.
In our model, each collision incurs a known cost of C, where 1 ↑ C ↑ n ω , for a known constant ω→ 0. 4 Given a contention-resolution algorithm, the pertinent costs are: (i) the collision cost, which is the number of collisions multiplied by C, and (ii) the makespan. Often we refer to "cost", by which we mean the maximum of (i) and (ii), unless specified otherwise.
Notation. Throughout this manuscript, lg(•) refers to logarithm base 2, and ln(•) refers to the natural logarithm. We use log y (x) to denote (log(x)) y , and we use poly(x) to denote x y for some constant y → 1. The notation Õ denotes the omission of a poly(log n) factor. We say an event occurs with high probability (w.h.p.) in n (or simply "with high probability") if it occurs with probability at least 1 ↔ O(1/n c ), for any tunable constant c → 1.
For any random variable X, we say that w.h.p. the expected value E[X] ↑ x if, when tallying the events in the expected value calculation, the sum total probability of those events where X > x is O(1/n c ) for any tunable constant c → 1. In our analysis, the expected collision cost holds so long as the subroutine DIAGNOSIS (described later) gives correct feedback to the packets, and this occurs with high probability.
We design and analyze a new algorithm, COLLISION-AVERSION BACKOFF (CAB), that solves the static contention resolution problem with high-probability bounds on makespan and the expected collision cost. The following theorems provide our formal result. How does this compare with prior results? For starters, consider SAWTOOTH-BACKOFF (STB), which w.h.p. has an asymptotically-optimal makespan of ϑ(n), but incurs ε(n) collisions. The expected cost for CAB is superior to STB when C is at least polylogarithmic in n. In Section 1.3, we elaborate on how our result fits with previous work on contention resolution.
In a well-known lower bound in the standard cost model, Willard [35] defines and argues about fair algorithms. These are algorithms where, in a fixed slot, every active packet sends with the same probability (and the probability may change from slot to slot). Our lower bound applies to fair algorithms as follows.
Theorem 2. Any fair algorithm that w.h.p. has a makespan of Õ(n ↓ C) has w.h.p. an expected collision cost of ε(n
Since CAB is fair and guarantees w.h.p. a makespan of Õ(n ↓ C), our upper bound is asymptotically tight up to a poly(log n)-factor for sufficiently large C. A more general form of our lower bound is given in Section 4, along with additional discussion.
Here, we discuss the potential value of our result and exploring beyond the standard cost model for contention resolution.
A Simple Answer. Prior contention-resolution algorithms that optimize for makespan suffer from many collisions. For example, arguably the most famous backoff algorithm is BEB (despite its sub-optimal makespan [9]), which has ε(n) collisions. Similarly, STB has asymptotically-optimal makespan, but also suffers ε(n) collisions [6]. Thus, these algorithms have cost θ(n + nC). In contrast, the expected completion time for CAB is Õ(n ↓ C), which is superior whenever C = poly(log n).
In the extreme, even a hypothetical algorithm that suffers (say, w.h.p.) a single collision would do poorly by comparison if collisions are sufficiently costly. Specifically, such an algorithm pays C, which is asymptotically worse than the expected completion time of CAB for C = π(n 2 ).
Perhaps the above is reasonable motivation (we think it is), but why not also consider the cost of successes? 5 Below, we argue that reducing collision cost remains important, and that adding a non-unit cost for successes does not seem interesting from a theory perspective.
Connecting to the Standard Cost Model. Let us temporarily consider the implications of a cost model where a success and a collision each have cost P → 1. In the standard cost model P = 1. In WiFi networks, both costs are also roughly equal, where P ↗ 1 [6].
In this context, reconsider STB's performance. Since, n packets must succeed, a cost of at least nP is unavoidable, and the additional ϑ(nP ) cost from collisions becomes (asymptotically) unimportant. (Indeed, any algorithm must pay at least nP for successes; given this unavoidable cost, it does not seem interesting from a theory perspective to consider a model where a success costs far more than a collision, since the cost from successes would dominate.) Likewise, CAB must also pay at least nP , which is (asymptotically) no better than STB.
Does reducing collision costs matter here? Yes, and the value of our result is best viewed via throughput (recall Section 1.1). STB has cn collisions, for some constant c > 0, and (ignoring empty slots) its throughput is less than nP/(nP + (cn)P ) < 1/(1 + c) < 1 ↔ 1/c; that is, the throughput is bounded away from 1 by a constant amount. Doing a similar calculation for CAB, there is nP cost for n packets to succeed, plus O(n ↓ P ), which accounts for collisions and empty slots. Thus, the expected throughput is E[nP/T ] where T is the completion time. Since,
Thus, for the standard cost model, with P = 1, our result is (unsurprisingly) not an improvement. However, as P grows, our result provides better throughput in expectation, approaching 1. There are settings where we expect P to be large, such as: wireless networks where P can be commensurate with packet size, routing in mobile networks where communication failure increases latency [36], and shared memory systems where concurrent access to the same memory location by multiple processes results in delay [8].
There is a large body of work on the static case for contention resolution, where n packets arrive together and initiate the contention resolution algorithm; this is often referred to as the static or batched-arrival setting. Bender et al. [9] analyze the makespan for BEB, as well as other backoff algorithms; surprisingly, they show that BEB has sub-optimal makespan.
An optimal backoff algorithm is STB [26,28]. Since we borrow from STB to create one of our subroutines (discussed further in Section 3.1), so we describe it here. Informally, STB works by executing over a doubly-nested loop, where the outer loop sets the current window size w to be double the one used in the preceding outer loop. Additionally, for each such window, the inner loop executes over a run of lg w windows of decreasing size: w, w/2, w/4, ..., 1. For each window, every packet chooses a slot uniformly at random (u.a.r.) to send in.
The static setting has drawn attention from other angles. Bender et al. [10] examines a model where packets have different sizes under the binary feedback model. Anderton et al. [6] provide experimental results and argue that packet size should be incorporated into the definition of makespan, since collisions tend to cost time proportional to packet size.
To the best of our knowledge, our work is the first to propose an algorithm for minimizing collision cost, and so it makes sense to start with the static setting. However, we note the dynamic setting has been addressed (under the standard cost model), where packet arrival times are governed by a stochastic process (see the survey by Chlebus [20]). Another direction that the research community has pursued is the application of adversarial queueing theory (AQT) [17] to contention resolution; for examples, see [22,21,3,2]. Under the AQT setting, packet arrival times are dictated by an adversary, but typically subject to constraints on the rate of packet injection and how closely in time (how bursty) these arrivals may be scheduled. Even more challenging, there is a growing literature addressing the case where packet arrival times are set by an unconstrained adversary; see [23,14,25]. Recent work in this area addresses additional challenges facing modern networks, such as energy efficiency [29,15], malicious disruption of the shared channel [12,7,31,19,5,4], and the ability to have a limited number of concurrent transmission succeed [13].
Due to space constraints, our proofs for the upper bound are provided in Section A of our appendix. However, we do reference some well-known inequalities based on the Taylor series that are omitted here, but can be found in Section A.1.
Here, we present an overview of our analysis, with the aim of imparting some intuition the design choices behind CAB, as well as highlighting the novelty of our approach. To this end, we first consider two natural-but ultimately flawed-ideas for solving our problem.
Straw Man 1. An immediate question is: Why can we not use a prior contention-resolution algorithm to solve our problem? For example, in the static setting, a well-known backoff algorithm, such BEB guarantees w.h.p. that all packets succeed with makespan ϑ(n log n) [9]. Under BEB, the packets execute over a sequence of disjoint windows, where window i → 0 consists of 2 i contiguous slots. Every active packet sends in a slot chosen u.a.r. from the current window. Unfortunately, a constant fraction of slots in each window i ↑ lg(n) + O(1) will be collisions. Each collision imposes a cost of C leading to a collision cost of ε(nC).
↘ ≃
Despite yielding a poor result, this straw man provides three useful insights. First, we cannot have packets start with a "small" window, since this leads to many collisions. Many backoff algorithms start with a small window, and will not yield good performance for this same reason. Second, we should seek to better (asymptotically) balance the costs of makespan and collisions. Under BEB, these costs are highly unbalanced, being ϑ(n log n) and ε(nC), respectively. We may trade off between makespan and collision cost; that is, we can make our windows larger, which increases our makespan, in order to dilute the probability of collisions.
Third, a window of size ϑ(n ↓ C) seems to align with these first two insights; that is, it appears to asymptotically balance makspan and collision cost. To understand the latter claim, suppose that in each slot, every packet sends with probability ϑ(1/(n ↓ C)). We can argue (informally) that, for any fixed slot, the probability of any two packets colliding is at least
Thus, over n ↓ C slots in the window, the expected number of collisions is
and each collision has cost C, so the expected collision cost is O(n ↓ C). Of course, this informal analysis falls short, since collisions may involve more than two packets, and we have not shown that all n packets can succeed over this single window (they cannot). Yet, this insight offers us hope that we can outperform prior backoff algorithms by achieving costs that are o(nC).
How should we find a window of ϑ(n ↓ C)? Since n is unknown a priori, we cannot simply instruct packets to start with that window size. It is also clear from the above discussion that we cannot grow the window to this size using prior backoff algorithms. This obstacle leads us to our second straw man.
Straw Man 2. Perhaps we can estimate n and then start directly with a window of size ϑ(n ↓ C). A well-known "folklore" algorithm for estimating n is the following. In each slot i → 0, each packet sends with probability 1/2 i ; otherwise, the packet listens. This algorithm, along with improvements to the quality of the estimation, is explored by Jurdzinski et al. [29], but we sketch why it works here.
Intuitively, when i is small, say a constant, then the probability of an empty slot is very small: (1 ↔ 1/2 ε(1) ) n ↑ e →ε(n) by Fact 1(a). However, once i = lg(n), then the probability of an empty slot is a constant: 1) by Fact 1(c). In other words, once a packet witnesses an empty slot, it can infer that its sending probability is ϑ(1/n), and thus the reciprocal yields an estimate of n to within a constant factor.
At first glance, it may seem that we can estimate n, and then proceed to send packets in a window of size ϑ(n ↓ C). Unfortunately, for each slot i ↑ lg(n), this algorithm (and others like it) will likely incur a collision, and thus the expected collision cost is ε(C log n). To see why this is a problem, suppose that C = n 4 . This implies that the expected collision cost is ε(C) = ε(n 4 ), while the makespan is at best O(n
That is, there is an n-factor discrepancy between the expected collision cost and makespan, which grows worse for larger values of C; this approach is not trading off well between these two metrics.
↘ ≃ Even though the above algorithm racks up a large collision cost, it highlights how channel feedback can provide useful hints. If packets are less aggressive with their sending, we can reduce collisions while still receiving feedback that lets us reach our desired window size of ϑ(n ↓ C).
Motivating Sample Size. Hoping to avoid the problems illustrated in our discussion above, all packets begin with an initial current window size that can be "large"; the exact size we motivate momentarily. Recall that we aim for packets to tune their sending probability to be ϑ(1/(n ↓ C)), so we are aiming for a window size of ϑ(n ↓ C). However, this must be achieved with low expected collision cost. To do this, the packets execute over a sample of s slots. For each slot in the sample, every packet sends with probability 1 divided by the current window size, and monitors the channel feedback.
What does this channel feedback from the sample tell us? Suppose we have reached our desired window size of
Then, the window size may be large relative to n, and so we should expect empty slots to occur frequently, while successes do occur, but less often; the probability of success is approximately n
To correctly diagnose w.h.p. (using a Chernoff bound) that w = ϑ(n ↓ C), we rely on receiving ϑ(log n) successes. This dictates our sample size to be s
The details behind this intuition are given in Section A.2 of our appendix, where we show that samples of size ϑ( ↓ C log(n)) are sufficient to make correct decisions that tune the window size to be ϑ(n ↓ C). Furthermore, in Section A.3 of our appendix, we show that the corresponding cost from this tuning is Õ(n ↓ C).
Motivating Initial Window Size. Suppose we are not at our desired window size. Then, the feedback from sampling tells us what to do. If our current window size is too large (i.e., our sending probability is too low), then the number of successes will be "small", since most slots are empty, and we should decrease our window size. Else, if the current window size is too small, (i.e., our sending probability is too high) then the number of successes is again "small", since most slots are collisions, and we should increase the window size. But wait, in the latter case, can we tolerate the cost of the resulting collisions? In the worse case, the entire sample might consist of collisions, resulting in a potentially large cost of s C = ϑ(C 3/2 log n).
We remedy this problem by setting our initial window size to be C. Then, the probability of a collision in a fixed slot is approximately n 2 (1/C 2 ) and so the expected cost is roughly
This reasoning is formalized in Lemma 13 of our appendix.
In light of the above, we emphasize that CAB does not avoid all collisions; in fact, many collisions may occur when the collision cost is "small" (i.e., C ↑ n). However, as the collision cost grows "larger" (i.e., C > n), CAB expresses an increasing aversion to collisions by having packets tune their respective sending probabilities such that we expect o(1) collisions per sample. The cost analysis for sampling is given in Section A.3 of our appendix.
Borrowing from Sawtooth Backoff. By using sampling, ultimately a window size of ϑ(n ↓ C) is reached. At this point, every active packet executes the analog of the final run of STB (recall Section 2). Specifically, each packet sends with probability p = ϑ(1/(n ↓ C)), which we show is sufficient to have at least half of the active packets succeed (see Lemma 20). Then, the window is halved, and the process repeats where the remaining packets send with probability p/2. This halving process continues until all packets succeed. By the sum of a geometric series, the number of slots in this process is O(n ↓ C). Informally, the expected collision cost per slot is roughly n
, and thus O(n ↓ C) over all slots in the window. The analysis of cost is provided in Section A.4 of our appendix.
This section describes and gives intuition for CAB, whose pseudocode is given in Figure 2. As stated in our model (Section 1.1), when a packet succeeds it terminates immediate; for ease of presentation, we omit this from our pseudocode.
From a high-level view, each packet keeps track of a current window size, wcur; this size is critical, as it dictates the per-slot sending probability of each packet, which is ϑ(1/wcur). Each packet keeps track of its own notion of a current window. However, in each slot, since every packet is either listening or sending (and, thus, learning whether the slot contained a success or a collision), all packets receive the same channel feedback and adjust their respective current window identically (stated formally in Lemma 8). Therefore, for ease of presentation, we refer only to a single current window.
Defining Ranges. In order to describe how CAB works, we define the six size ranges that the current window (or just "window" for short), wcur, can belong to during an execution.
These ranges are depicted in Figure 1. We note that the particular constants in these ranges are not special; they are chosen for ease of analysis. To gain intuition, we now describe the events we expect to witness in the ROCK-BOTTOM, LOW, GOOD, and HIGH ranges when CAB executes; we defer an in-depth discussion of UNCERTAIN-LOW and UNCERTAIN-HIGH until the end of the next subsection.
The ROCK-BOTTOM range captures "tiny" window sizes, starting from 1 up to n ↔ 1. In this range, the probability of sending exceeds 1/n, and we expect that most slots will be collisions. The next range is LOW, and it includes window sizes from n to just below 10n ↓ C. This range represents a moderate increase in window size, allowing for more successes than ROCK-BOTTOM, although there can still be many collisions. As discussed in Section 3.1, in ROCK-BOTTOM and in the bottom portion of LOW, we can afford to have an single sample consist entirely of collisions, since C = O(n) (see Lemma 16). However, lingering in these ranges would ultimately lead to sub-optimal expected collision cost.
The GOOD range spans from 200n ↓ C to just below 10 3 n ↓ C. In this range, the window sizes are sufficiently large that we expect o(1) collisions, along with handful of successes; notably, less successes than LOW. This turns out to be a "good" operating range for the algorithm, where the balance between collision costs and makespan is achieved, as discussed in Section 3 (i.e., our third insight after Straw Man 1).
The HIGH range covers window sizes from 10 5 n ↓ C and above. In this range, the window sizes are very large, leading to a very low probability of collisions, which is good. However, there are also far-fewer successes compared to GOOD, which means that lingering in this range would lead to a sub-optimal number of slots until all packets succeed.
1 Initial window size wcur ⇑ C 2 repeat 3 #successes, #collisions ⇑ 0 4 COLLECT-SAMPLE(C, wcur) 5 DIAGNOSIS(#successes, #collisions, wcur) 6 until true; 7 Function COLLECT-SAMPLE(C, wcur): 8 #successes ⇑ 0 9 #collision ⇑ 0 for slot i = 1 to d ↓ C ln(wcur) do Send with probability 1/wcur; otherwise, listen if slot is a success then #successes++ else if slot is a collision then #collisions++ Function DIAGNOSIS(#successes, #collisions, wcur): if #successes > 2d ln(wcur) 10 5 then if #successes ↑ d ln(wcur) 20e then if #collisions → d → C ln(wcur) 8e 2 then 20 wcur ⇑ 2wcur else 22 Execute RUNDOWN (wcur) else wcur ⇑ 2wcur else if #collisions → d → C ln(wcur) 8e 2 then wcur ⇑ 2wcur else wcur ⇑ wcur/2 Function RUNDOWN(wcur): w 0 ⇑ wcur while wcur → 8 ↓ C lg(w 0 ) do for each slot j = 1 to wcur do Send packet with probability 2/wcur wcur ⇑ wcur/2 . exactly what will happen, although we do prove that the algorithm is making "progress". We will elaborate on this further after describing our methods for sampling and interpreting channel feedback, which we address next.
Sampling and Diagnosing Feedback. CAB navigates these ranges by using two subroutines: COLLECT-SAMPLE and DIAGNOSIS. As motivated earlier in Section 3.1, a sample is a contiguous set of d ↓ C ln(wcur) slots that are used by each packet to collected channel feedback. Specifically, under COLLECT-SAMPLE, in each slot of the sample, every packet sends independently with probability 1/wcur and records the result if it is a success or a collision.
Based on the number of successes and the number of collisions, DIAGNOSIS attempts to determine the range to which wcur belongs. We discuss these thresholds in order to give some intuition for how DIAGNOSIS is making this determination. To simplify the presentation, we omit discussion of UNCERTAIN-LOW and UNCERTAIN-HIGH until the end of this section. The process by which CAB homes in on the range to which wcur belongs is depicted in Figure 3.
We begin with the first if-statement on Line 17. This line checks if the number of successes is at least a logarithmic amount (in wcur); if so, this indicates that wcur cannot be in the HIGH range, which would yield far fewer successes (see Lemma 13). Therefore, if meet the conditional on Line 17, it must be the case that wcur belongs to ROCK-BOTTOM, LOW, or GOOD.
Line 18 checks whether the number of successes falls below a "large" logarithmic amount; if not, then we are seeing a "large" number of successes that indicates wcur cannot be in ROCK-BOTTOM or in GOOD, and so must be in LOW (see Lemma 10). Otherwise, the number of successes falls below this logarithmic amount, indicating that wcur is in the ROCK-BOTTOM or in GOOD ranges. To discern between these two cases, Line 19 checks if the number of collisions exceeds d
, which indicates wcur ⇓ ROCK-BOTTOM (see Lemmas 6, 7, and 9). Otherwise, wcur falls within the GOOD and the job of DIAGNOSIS is complete -at this point, RUNDOWN will be executed.
How can an algorithm with low expected collision cost make a decision based on whether ϑ( ↓ C log(wcur)) collisions occur? Recall that in this case, we are deciding between wcur ⇓ ROCK-BOTTOM and wcur ⇓ GOOD. We will only witness this number of collisions when wcur is in the ROCK-BOTTOM range, where C ↑ n and so we can tolerate this cost. Otherwise, as described above, wcur ⇓ GOOD and the expected number of collisions is only Õ(1/ ↓ C) (see the discussion preceding Lemma 11 in our appendix).
The remaining portion of DIAGNOSIS starts with the else-statement on Line 25. This line is executed only if the conditional on Line 17 is not met; that is, we have very few successes. This can occur only if wcur ⇓ ROCK-BOTTOM or wcur ⇓ HIGH. The former case is (again) diagnosed be checking whether there are many collisions (Line 26) and, if so, the window is doubled; otherwise, we are in the latter case and the window is halved. Again, we only have many collisions if wcur is in the ROCK-BOTTOM or lower portion of the LOW ranges, where C ↑ n and so we can tolerate this cost.
What about the uncertain ranges? In UNCERTAIN-LOW, a sample will contain enough successes to satisfy Line 17. However, it is unclear whether the number of successes will be "large" (if wcur is in the lower portion of UNCERTAIN-LOW) or "moderate" (if wcur is in the upper portion of UNCERTAIN-LOW). In the former case, we fail Line 18, while in the latter case, we satisfy Line 18. Despite this uncertainty, observe that we are nonetheless guaranteed to either double the window or execute RUNDOWN. Either of these outcomes count as progress, since either wcur moves closer to GOOD by doubling, or RUNDOWN is executed on a window of size ϑ(n ↓ C) (in contrast, halving wcur would be counterproductive). The intuition behind UNCERTAIN-HIGH is similar. If wcur ⇓ HIGH, then we can show that the number of successes fails Line 17 (see Lemma 13) and that, ultimately, we halve wcur. However, between GOOD and HIGH, this cannot be shown w.h.p.; it may hold if wcur is close to the lower end of HIGH, but not hold if wcur is close to the upper end of GOOD. So, instead, we argue that we either halve wcur or execute RUNDOWN. Either of these actions counts as progress, since either wcur moves closer to GOOD, or RUNDOWN is executed on a window of size ϑ(n ↓ C). Ultimately, we are able to show the following key lemma (in Section A. 3 of our appendix): Lemma 19. The executions of COLLECT-SAMPLE and DIAGNOSIS guarantee that w.h.p.: (i) RUNDOWN is executed within O( ↓ C log 2 (n)) slots, and (ii) the total expected collision cost until that point is O
All Remaining Active Packets Succeed. The final subroutine, RUNDOWN, is executed once wcur = ϑ(n ↓ C), and it allows all active packets to succeed. In each slot of wcur, every packet sends with probability 2/wcur. Otherwise, the current window size is halved and the remaining active packets repeat this process. This continues until the window size reaches ϑ(
, where the asymptotic equality holds by recalling that C = poly(n). Once this smallest window in the run is reached, O(log n) active packets remain. To finish these packets, CAB performs an additional ϑ(ln(n
, where any remaining active packet sends in each slot with probability ϑ(1/n ↓ C). We prove the following lemmas (in Section A. 4 of our appendix): Lemma 21. When RUNDOWN is executed, w.h.p. all packets succeed within O(n ↓ C ln(n)) slots. Lemma 22. W.h.p. the expected collision cost for executing RUNDOWN is O(n ↓ C ln(n)). Finally, our upper bound in Theorem 1 follows directly from Lemmas 19, 21, and 22.
In this section, we provide an overview of our argument, which focuses on placing a lower bound on the expected collision cost. Here, we highlight the key lemmas in our argument, and our full proofs are provided in Section B of our appendix. We consider only the set of slots, S, in the execution of any algorithm where at least two active packets remain, since we cannot have a collision with a single active packet. While we do not always make this explicit, but going forward, any slot t is assumed to implicitly belong to S.
Let pi(t) denote the probability that packet i sends in slot t. Note that, if a packet has terminated, its sending probability can be viewed as 0. For any fixed slot t, the contention in slot t is Con(t) = n i=1 pi(t); that is, the sum of the sending probabilities in that slot.
When Contention is High. We start by showing that any algorithm that has even a single slot t with Con(t) > 2 must have ε(C) expected collision cost, which is one portion of our lower bound. This is done by deriving an expression for the probability of a collision in any fixed slot t as a function of Con(t), which is useful when Con(t) is "high" (see Lemmas 23,24,and 25 in Section B of our appendix).
When Contention is Low. What about an algorithm where all slots of the execution have "low" contention (i.e., Con(t) ↑ 2)? Our previous expression is hard to work with in this case. So, we derive a different expression for the probability of a collision in a fixed slot t, which can be useful for small values of Con(t): Lemma 26. Fix any slot t and let Con(t) ↑ 2. The probability of a collision in t is at least ( 1 110 ) Con(t) 2 ↔ i pi(t) 2 . However, this expression requires some additional work to be deployed in our argument, as we now describe.
For any fixed slot t ⇓ S, let pmax(t) be the maximum sending probability of any packet in slot t. Similarly, let psec(t) ↑ pmax(t) be the next-largest sending probability of any packet in slot t; note that psec(t) = pmax(t), if more than one packet sends with probability pmax(t).
Define ε(t) = psec(t)/pmax(t). Our analysis ignores any slot t where Con(t) = 0; that is, any slot where every packet has a sending probability of 0. We give such slots to any algorithm for "free"; that is, we do not include them in the cost of the execution. Thus, ϱ(t) is always well-defined, since pmax(t) > 0.
Why do we need ϱ(t)? It captures a sense of "balance". For our purposes, the situation is most "unbalanced" when exactly one packet has non-zero sending probability, while all other packets have zero sending probability; that is, when the total value of Con(t) > 0 is due to a single packet. Clearly, in such slots, there can be no collision and, correspondingly, ϱ(t) = 0. In our argument, ϱ(t) plays a key role in establishing the following: Lemma 27. For any fixed slot t, Con(t) 2 ↔ i pi(t) 2 → ϱ(t) Con(t) 2 /2. A natural extension of ϱ(t) is εmin, which is the minimum ϱ(t) over all slots t ⇓ S. As we show momentarily, our lower bound is parameterized by ϱmin. The last component of our argument addresses the sum of the contention over all slots in S: Lemma 30. Any algorithm that guarantees w.h.p. that n packets succeed must w.h.p. have t↓S Con(t) = ε(n). We can now establish a lower bound for this low-contention case: Lemma 31. Consider any algorithm A whose contention in any slot is at most 2 and guarantees w.h.p. a makespan of Õ(n ↓ C). W.h.p. the expected collision cost for A is ε(ϱminn ↓ C).
Proof. Let X be a random variable that is |S| under the execution of A. Note that, since w.h.p. the makespan is Õ(n ↓ C), it must be the case that w.h.p. X = Õ(n ↓ C). By Lemma 30, we have:
for some constant c > 0. Let Yt = 1 if slot t ⇓ S has a collision; otherwise, Yt = 0. By Lemmas 26 and 27:
where the second line follows from the definition of ϱmin. The expected collision cost is:
By Jensen's inequality for convex functions, we have:
Finally, the expected cost is at least:
by Equations 8 and 9
by Equation 7= ε ϱmin n ↓ C
where the second line follows by Equation 7, which was defined with regard to S, and so can be compared to Equation 8. The last line follows since w.h.p. X = Õ(n ↓ C).
Given our analysis of the high-and low-contention cases, we have the following lower bound:
Theorem 4. Consider any algorithm that w.h.p. guarantees Õ(n ↓ C) makespan. Then, w.h.p., the expected collision cost for A is ε(min{C, ϱminn ↓ C}).
What algorithms does our lower bound say something interesting about? We can start with our statement in Theorem 2. For a well-known lower bound with the standard cost model, Willard [35] defines and argues about fair algorithms. These are algorithms where, in a fixed slot, every active packet sends with the same probability (and the probability may change from slot to slot). Fair algorithms have ϱmin = 1, and for a sufficiently large collision cost-specifically, C = ε(n 2 )-the lower bound becomes ε(n ↓ C). Given that CAB is fair and w.h.p. guarantees Õ(n ↓ C) makespan, we thus have a lower bound that is asymptotically tight to a poly(log n)-factor with our upper bound.
Our lower bound also applies in a similar way to a generalized notion of fairness, where the sending probabilities of any two packets are within some factor ς > 0. For example, if ς = ϑ(1), then ϱmin = ϑ(1). Indeed, we only need such ς-fairness between the two packets with the largest probabilities for our lower bound to apply, although our bound weakens as ς grows larger.
Another class of algorithms that our lower bound applies to is multiplicative weights update algorithms, where in each slot every packet updates its sending probability by a multiplicative factor based on channel feedback in the slot. Many of these algorithms are fair (such as [18,11,34,33,31,7,13]), but not all are (such as [11]). Our lower bound applies in a non-trivial way to all such algorithms; that is, ϱmin > 0 given the update rules.
We considered a model for the problem contention resolution where each collision has cost C. Our algorithm, COLLISION-AVERSION BACKOFF, addresses the static case and guarantees w.h.p. that all packets succeed with makespan and expected collision cost that is Õ(n ↓ C). There are several directions for future work that are potentially interesting. First, we would like to extend this cost model to the dynamic setting (where packets may arrive over time) and design solutions. Many algorithms for the dynamic case break the packet arrivals into (mostly) disjoint batches; however, this requires periodic broadcasting that can cause collisions.
Second, for the lower bound, we believe (with some more work) that we can remove the poly(log n) factor. However, we would like to derive a more general lower bound. A significant challenge appears to be addressing algorithms that set up slots where exactly one packet has non-zero sending probability, while all others have zero sending probability. For example, an elected leader might "schedule" each packet their own exclusive slot in which to send (with probability 1). Since there can be no collisions after such a schedule is implemented, it seems a lower bound argument must demonstrate that establishing a schedule is costly.
Third, what if collisions are not fully dictated by the actions of packets? Some wireless settings are inherently "noisy", due to weather conditions, co-located networks, or faulty devices. Is there a sensible model for such settings and, if so, can we reduce the cost from collisions?
Proof. Fix a time slot t. Let pi denote the probability that packet i sends in slot t and number of packets at the beginning is m. The probability of collision in slot t is at most:
which proves the claim.
↘ ≃
In order to argue correctness for DIAGNOSIS, we give a case analysis for each of the ROCK-BOTTOM, LOW, GOOD, and HIGH ranges. In each case, we provide the necessary bounds on successes and collision per sample, which allows us to demonstrate that DIAGNOSIS correctly diagnoses the current range and performs the correct action. We start with Lemmas 2, 3, 4, and 5, which establish lower and upper bounds on the number of successes in the ranges of LOW, GOOD, and HIGH. Proof. Let Xi be an independent random variable where Xi = 1 when i-th slot in w contains a success, and Xi = 0 otherwise.
X k , then the expected number of success: Proof. Let Xi be an independent random variable where Xi = 1 when i-th slot in w contains a success, and Xi = 0 otherwise.
.
Let X k be an independent random variable where X k = 1 when k-th slot in the sample contains a success, and X k = 0 otherwise. The expected number of successes in the sample is: Xi, and note by the above that E[X] → d ln(wcur) be . By Theorem 3, with ς = 1/2, we have:
n d ↑ where d ↔ can be an arbitrarily large constant, so long as d is sufficiently large.
The next two lemmas pertain to the range of ROCK-BOTTOM. Lemma 6 shows that, when the window size is O(n/ log n), the entire sample will consist of collisions. Unlike many of our other arguments, we cannot employ a Chernoff to establish this fact. Lemma 7 handles the remainder of the ROCK-BOTTOM range, showing that much of the sample will consist of collisions.
Lemma 6. Suppose that 1 ↑ wcur ↑ n c ln n and n is sufficiently large and c → 1 is a constant. Then, with probability at least 1 ↔ 1/n d ↑ , the entire sample consists of collisions, where d ↔ depends on sufficiently large c.
Proof. For any fixed slot, the probability of a collision is at least 1 minus the probability of a success, minus the probability of that the slot is empty. In other words, the probability of a collision is at least:
for n sufficiently large which yields the claim.
↘ ≃ Lemma 7. Suppose n c ln n < wcur ↑ n, where c → 1 is any constant. Then, with probability at least 1↔1/n d ↑ , the sample contains at least d ↓ C ln(wcur)/(8e 2 ) slots consists of collisions, where d ↔ is an arbitrarily large constant depending on sufficiently large d.
Proof. Let the indicator random variable Xi = 1 if the i-th slot of the d ↓ C ln(wcur) slots contains a collision; otherwise, let Xi = 0. The probability of a collision is lower bounded as follows.
cur e →2n/wcur by Fact 1(c)
Xi. The expected number of collisions in the sample of d ↓ C ln(wcur) slots is:
by linearity of expectation.
We then employ Theorem 3, with ς = 1/2, to obtain:
where d ↔ can be an arbitrarily large constant, so long as d is sufficiently large.
↘ ≃ Lemma 8. Under DIAGNOSIS, all packets witness the same number of empty slots, successes, and collisions.
Proof. In each slot, a packet is either sending or listening. First, consider the case where at least one packet sends. Each such sending packet knows whether it succeeded (i.e., a success) or it failed (i.e., a collision). Each non-sending packet listens and hears the success (i.e., a success) or the failure (i.e., a collision). Second, if no packet sends, then every packet is listening and hears the same thing: silence. Therefore, in all cases, each packet witnesses the same outcome of the slot.
Lemma 8 guarantees that all packets are always in the same window (or have the same sending probability) when executing DIAGNOSIS, and they always take the same action in an execution of DIAGNOSIS. The following lemmas establish that DIAGNOSIS takes the correct action in each execution. ), if wcur ⇓ ROCK-BOTTOM, then all packets double their window, where d ↔ is an arbitrarily large constant depending on sufficiently large d.
Proof. We do a case analysis. For the first case, consider that wcur ⇓ [1, n/(c ln n)) for some sufficient large constant c → 1. By Lemma 6, with probability at least 1 ↔ n →d ↑ , all slots in the sample contain a collision. Therefore, w.h.p., the if-statement on Line 17 is not entered and, instead, the matching else-statement on Line 25 is entered. Since all sample slots are collisions, the if-statement on Line 26 is entered, and the window doubles.
For the second case, consider wcur ⇓ [n/(c ln n), n). Either we (a) enter the first if-statement on Line 17, or we (b) enter the matching else-statement on Line 25.
• Subcase (a). If the second if-statement on Line 18 is entered, then we note by Lemma 7, w.h.p., that we have at least
C ln(wcur)/(8e 2 ) collisions, which means we double the window, as desired. Otherwise, we execute Line 23, and the window doubles.
• Subcase (b). By Lemma 7 w.h.p. we have at least d ↓ C ln(wcur)/(8e 2 ) collisions, which means we enter the ifstatement on Line 26 and double the window.
In both cases, the packet doubles its window.
↘ ≃
), if wcur ⇓ LOW, then all packets double their window, where d ↔ is an arbitrarily large constant depending on sufficiently large d.
Proof. By Lemma 5 with b = 10, for w such that n ↑ w < 10n ↓ C, with probability at least 1 ↔ n →d ↑ the number of successes exceeds d 20e ln(wcur). Therefore, the first if-statement on Line 17 is entered, but the next if-statement on Line 18 is not. Thus, Line 23 will be executed and so the window will double, as claimed.
The following lemma places an upper bound on the number of collisions when the window is at least 200n ↓ C. This allows us to argue that when we are in the GOOD and HIGH ranges, we avoid executing the lines in DIAGNOSIS that would double the window.
We note that the next lemma gives a very loose upper bound on the number of collisions. In fact, if we expected even a single collision in this range, our claimed upper bound would not hold. The careful reader will note that (in our proof) the expected number of collisions is Õ(1/ ↓ C); however, a loose upper bound that holds with high probability is sufficient to construct the rules for DIAGNOSIS. Proof. By Lemma 1, the probability of a collision in a slot is at most 2n 2 p 2 (1→np) , where p ↑ 1/(200n ↓ C). Plugging in, we obtain that the probability of collision is upper bounded by:
Xi. The expected number of collisions in the sample of d ↓ C ln wcur slots is: , so Line 17 will be true. For the remaining lines that may be executed-Lines 18 to 24-we either double the window (due to many collisions) or execute RUNDOWN, as claimed.
↘ ≃ Lemma 15. With probability at least 1 ↔ O(1/n d ↑ ), if wcur ⇓ UNCERTAIN-HIGH, then either the window halves or RUNDOWN is executed, where d ↔ is an arbitrarily large constant depending on sufficiently large d.
Proof. We prove this by ruling out all the ways in which wcur could (incorrectly) double.
Unlike our argument for wcur ⇓ GOOD, we cannot guarantee that Line 17 will be executed, since our window might be large, say just shy of 10 5 n ↓ C, (recall that UNCERTAIN-HIGH = [10 3 n ↓ C, 10 5 n ↓ C)), and we cannot prove a sufficient number of successes. However, if we proceed to Line 25, then by Lemma 11, the number of collisions is at most (d/90) ln(wcur), which means there are not enough collisions to meet the if-statement condition on 26, and thus the window will not be doubled here.
Another way in which the window can (incorrectly) double is via Line 23. However, we only execute Line 23 if Line 18 fails to hold; that is, in the case that the sample contains more than than d ln(wcur) 20e successes. However, by Lemma 4 with a = 10 3 (the part of UNCERTAIN-HIGH where successes are most likely), the sample contains at most 2d ln(wcur) 10 3
< d ln(wcur) 20e successes, and so Line 18 will indeed execute. Finally, in the case that Line 18 executes, we do not have enough collisions to satisfy Line 26, again by Lemma 11. Thus, the window cannot double via Line 20 We have shown that, when wcur ⇓ UNCERTAIN-HIGH, either the window must halve, or RUNDOWN is executed, as claimed.
↘ ≃
The next lemmas establish bounds on the expected collision cost for executing COLLECT-SAMPLE. To this end, we employ the results established above, which hold with probability at least 1 ↔ 1/n d ↑ for as large a constant d ↔ → 1 as we wish, depending only on sufficiently large d. Thus, the results in this section also hold with this high probability, and for ease of presentation, we omit this from our technical lemma statements and arguments. Proof. We prove this using a case analysis.
Case 1: C → 2n. This captures all of ROCK-BOTTOM and the left endpoint of LOW. Here, even if the entire sample consists of collisions, then the cost is at most:
Case 2: C > 2n. With high probability, wcur ⇓ LOW only if the initial window lies in LOW. (With high probability, we cannot have started in ROCK-BOTTOM and moved up, since we start at a window of size C > n in this case.)
The probability of a collision is maximized when the window is smallest; that is, when the window has size C (which is the initial window size), since w.h.p. the window only increases (given that we are in LOW). By Lemma 1, the probability of a collision is at most:
where the equation from Lemma 1 is applicable, since p = 1/C < 1/(2n). Thus, expected cost is at most: C , the probability of a collision is at most:
Xi. The expected number of collisions in the sample of d ↓ C ln(wcur) slots is:
Thus, the expected collision cost is at most:
Proof. For HIGH, by using Lemma 1, we plug in the value m = n (number of packets) and p ↑ 1 10 5 n ↑ C (sending probability). The probability of a collision is at most:
since this value is largest for p = Xi. The expected number of collisions in the sample of d ↓ C ln(wcur) slots is:
Thus, multiplying by C, we obtain that the expected collision cost is at most O( ↓ C ln(n)). ↘ ≃ Lemma 19. The executions of COLLECT-SAMPLE and DIAGNOSIS guarantee that: (i) RUNDOWN is executed within O( ↓ C log 2 (n)) slots, and (ii) the total expected collision cost until that point is O n ↓ C log 2 (n) . Proof. We first bound the number of slots, and then we bound the expected collision cost. (i) Bound on Number of Slots. By Lemmas 9, 10, and 14, DIAGNOSIS correctly doubles the window or executes RUN-DOWN. Similarly, by Lemmas 13 and 15, DIAGNOSIS correctly halves the window or executes RUNDOWN. Therefore, DIAGNOSIS is always making progress towards reaching GOOD. How many window halvings or doublings are required to reach GOOD? We start at an initial window of size C, and either GOOD is smaller-in which case, we must perform O(log(C)) = O(log(n)) samples-or larger-in which case, we must again perform O(log(n ↓ C)) = O(log(n)) samples. Thus, the number of slots until GOOD is reached is at most the sample size multiplied by this number of samples, which is O( ↓ C log 2 (n)). Then, by Lemma 12, RUNDOWN is executed. (ii) Bound on Expected Collision Cost. Let Si denote the collision cost for sample i when executing DIAGNOSIS, where i = 1, ..., h, where h = O(log(n)) is the number of samples. Denote the total cost from collisions by S = h i=1 Si. By Lemmas 16, 17, and 18, we have:
A single execution of lines 33 to 35 in RUNDOWN of COLLISION-AVERSION BACKOFF is called a run. In any run, all packets operate over a window of size wcur and send themselves in each slot with probability 2/wcur. At the end of the window, those packets that succeeded will terminate, while the remaining packets will carry on into the next window, which has size wcur/2.
Our overall goal is to show that (roughly) a logarithmic in n runs are sufficient for all packets to succeed. To this end, our next lemma (below) argues that in each run at least half of the remaining packets succeed. Again, throughout this section, our results hold with a tunable probability of error that is polynomially small in n, and we omit this in our lemma statements. Lemma 20. Suppose m packets execute a window of RUNDOWN (wcur), where φ ln n ↑ m ↑ n, φ → 1 is a positive constant, and wcur → 8m ↓ C. Then, at least m/2 packets succeed.
Proof. Fix a packet and calculate the probability of failing over the entire window of size 8m ↓ C. To do so, note that the probability that this packet succeeds in a fixed slot is: (i) the probability that the packet sends in this slot, multiplied by (ii) the probability that all other m ↔ 1 packets remain silent. That is:
Thus, the probability of failure in the slot is:
It follows that the probability of failing over all wcur slots is:
For i = 1, ..., m, let the indicator random variable Xi = 1 if packet i fails over the entire window; otherwise, let Xi = 0.
We let X = m i=1 Xi, and note that: . This implies that, over these j windows in the run, n packets will be reduced to no more than n/2 j = O(log n) packets by the final window. Therefore, we have the following corollary. For the remainder of this section, all of the lemmas that we invoke hold with high probability in n, and thus we omit this from most of our lemmas statements and arguments. We are now able to prove correctness and an upper bound on the number of slots incurred by RUNDOWN. Repeating this c ln(w0) ↑ c ln(n) times guarantees that all remaining packets succeed with an error bound of at most: . By Lemma 20, in each window of a run, the number of packets is reduced by at least a factor of 2, and then the window size halves. That is, at the start of the i-th run, the number of packets is mi ↑ n/2 i and the window size is wi = w0/2 i , for i → 0.
We employ Lemma 1, where pi = 2/wi. We have that the expected number of collisions over a window of size wi in the run is at most:
We wrap up our analysis of CAB by calling on our main lemmas from the previous sections.
Theorem 1 W.h.p. COLLISION-AVERSION BACKOFF guarantees that all packets succeed, the makespan is O(n ↓ C log(n)), and the expected collision cost is O(n ↓ C log 2 (n)). Proof. By Lemma 19, over the course of executing COLLECT-SAMPLE and DIAGNOSIS, w.h.p. CAB executes over O( ↓ C log 2 (n)) slots and the expected collision cost is O(n ↓ C log 2 (n)). By Lemmas 21 and 22,w.h.p. when RUNDOWN is executed in CAB, all packets succeed within O(n ↓ C ln(n)) slots and the expected collision cost is O(n ↓ C ln(n)). Therefore, CAB guarantees that all packets succeed, the makespan is O(n ↓ C log(n)), and the expected collision cost is O(n ↓ C log 2 (n)). ↘ ≃
We consider only the set of slots, S, in the execution of any algorithm where at least two active packets remain, since we cannot have a collision with a single active packet. While we do not always make this explicit, but going forward, any slot t is assumed to implicitly belong to S. Let pi(t) denote the probability that packet i sends in slot t. Note that, if a packet has terminated, its sending probability can be viewed as 0. For any fixed slot t, the contention in slot t is Con(t) = n i=1 pi(t); that is, the sum of the sending probabilities in that slot.
We begin by arguing that any algorithm with contention exceeding 2 in any slot must incur an expected collision cost of ε(C). We do this by deriving an upper bound on the probability of (i) a success and (ii) an empty slot, as a function of contention. In turn, this provides a lower bound on the probability of a collision that is useful when contention exceeds 2, allowing us to show ε(C) expected cost in Lemma 25.
Lemma 23. Fix any slot t. The probability of a success is at most e•Con (t) e Con(t) .
We may also view C as an upper bound on the cost of a collision if there is some variance.
Note that knowing C and ω implies only a lower (not upper) bound on n.
Empty slots do not seem to warrant such consideration since, by definition, nothing is happening in such slots, and so a per-cost of 1 makes sense.