Dynamic Wakeup under Costly Collisions Umesh Biswas and Maxwell Young
arXiv:2609.35662v1 [cs.DC] 28 Sep 2026
Department of Computer Science and Engineering, Mississippi State University, MS 39762, USA [email protected], [email protected]
Abstract. The wakeup problem captures a fundamental symmetry-breaking challenge among devices sharing a communication channel. We study the dynamic setting, where packets become active at arbitrary times on a time-slotted multiple access channel. In each slot, a transmission succeeds if and only if exactly one packet transmits; two or more simultaneous transmissions cause a collision. The goal is to obtain a successful transmission quickly. Prior work on wakeup has largely focused on the number of slots until the first success; that is, the latency. However, a collision may incur substantial additional delay, represented by a per-collision cost C. We therefore seek to control both latency and the collision cost of an execution, defined as C times its number of collisions. We design and analyze a randomized algorithm for dynamic wakeup, Lowball, without collision detection or knowledge of the number of packets, n. Fix a constant 0 < ϵ ≤ 1/2. There is a constant 1/ϵ 1/2+ϵ K > 0 such that, ln C) and expected √ when C ≥ K lg n, Lowball has expected latency O(C collision cost O( C). Below this threshold, both expectations are O(n logΘ(1/ϵ) n). These guarantees hold against an adaptive adversary, and the algorithm succeeds with probability 1. For algorithms in which each packet’s transmission probability depends only on C and the packet’s local age, with packets activated together using the same√probability schedule, we prove that the maximum of expected latency and expected collision cost is Ω( C).
Keywords: Wakeup, algorithms for wireless communication, collision cost
1
Introduction
In the wakeup problem, devices are classified as either active (awake) or inactive (asleep). Active devices have packets ready for transmission over a shared channel, whereas inactive devices only listen. The first successful transmission serves as a “wakeup call”, awakening all inactive devices and resolving the problem [3]. Traditionally, the performance of a wakeup algorithm is measured by the number of slots until this first successful transmission, referred to as the latency . Achieving small latency is nontrivial because the channel can support at most one successful sender in a slot: if two or more devices transmit simultaneously, a collision occurs and all of those transmissions fail. Moreover, the devices operate in a distributed manner, with no a priori central scheduler or coordinator to assign transmission times. In this work, we address both latency and the additional delay caused by collisions in solving the wakeup problem. The per-collision cost C represents the delay from one collision. Summing these charges separately from the slotted execution gives the execution’s collision cost. While existing algorithms give strong latency guarantees, they may incur a large number of collisions (see Section 3.1), and addressing these two metrics in tandem requires new ideas. In particular, there is a natural tension between them. An aggressive transmission strategy can improve latency by increasing the chance that some packet sends, but it can also produce many costly collisions. On the other hand, a conservative strategy can reduce the delay caused by collisions, but may postpone the first successful transmission. Thus, minimizing the number of slots to first success does not necessarily minimize the accumulated delay caused by collisions. This tension is even more pronounced in the dynamic wakeup setting. Packets may become active at arbitrary times and therefore execute according to different local clocks. Moreover, the packets do not know the number of packets n, and without collision detection they cannot determine whether the current contention is too low, too high, or already at an appropriate level. Consequently, an algorithm must regulate contention without direct feedback while remaining robust to adversarially timed packet activations. This
2
U. Biswas and M. Young
raises the central question of our work: Can we solve dynamic wakeup without collision detection while keeping both latency and collision cost small? Why Collision Cost Matters. In the standard wakeup model, a collision consumes a single slot. In practice, however, a collision can occupy the channel or trigger a recovery period that causes substantial additional delay. For example, in WiFi (IEEE 802.11), the time consumed by a transmission and recovery from a collision can grow with packet size [1,2,11,10]. An algorithm that obtains a success after few contention opportunities may therefore still incur substantial elapsed delay: even a few costly collisions can outweigh the savings from using fewer slots. This concern extends beyond short-range WiFi. On long-distance wireless links, acknowledgment timeouts must accommodate propagation delay, increasing the time spent waiting after a failed transmission [29]. In intermittently connected mobile networks [33], a collision may force the sender to wait for another communication opportunity. In such settings, treating a collision as a single slot can substantially understate its effect on the time to communicate successfully. We represent this additional delay by the per-collision cost C. We report latency and the collision cost of the execution separately, since reducing one can increase the other. Together, these metrics capture the slots through the first success and the additional delay represented by the accumulated collision charges. The per-collision cost need not remain constant as the system grows. Packet sizes may increase with the amount of control information or application data they carry, increasing the delay associated with a collision [1]. Likewise, if additional devices are accommodated by expanding the physical area served by the shared channel, longer propagation distances can require larger recovery timeouts [29]. We therefore allow C to vary with n, without assuming a specific dependence. 1.1
Model and Notation
We consider a system with n devices, for a large and unknown value of n; each device has a single packet to send on the shared channel. We consider executions in which at least one packet is activated. Packets have only local clocks, which start at activation, and they do not have identifiers. Going forward, for ease of presentation, we refer only to the packets—rather than devices—committing actions such as sending and listening. Communication. Time is divided into disjoint slots, each of which can accommodate a packet transmission. Communication occurs on a multiple access channel , which is defined as follows. In any slot, a packet can either attempt to transmit or listen to the channel. If no packet is transmitted in a given slot, it is empty . If only one packet is transmitted, the packet succeeds; we often refer to this as a success. However, if multiple packets transmit simultaneously, they all fail—this is a collision—and they may try again later. There is no scheduler or central authority a priori. No Collision Detection. There is no mechanism to distinguish between an empty slot and a collision—that is, no collision detection (no-CD). In many practical systems, collision detection (CD) is unavailable or unreliable. For example, in WiFi networks, received signal strength may offer a weak form of CD, but it is error-prone. Consequently, many prior results address the challenging no-CD setting (see the survey [3] and related discussion in Section 2). We emphasize that CD and per-collision cost are separate concerns: collisions can cause additional delay regardless of whether they are detectable. For example, in WiFi, even if devices cannot sense an ongoing collision, the channel remains unavailable for its duration. Adversarial Activations. Packet activation times are controlled by an adaptive adversary. Before each slot t, the adversary may choose which packets become active in that slot as an arbitrary function of the entire execution history through the end of slot t − 1, including all previous packet actions and channel outcomes. The adversary must commit to these activations before any random choices or transmission decisions for slot t are revealed. Thus, its activation decision for slot t may depend on the history through slot t − 1, but not on random bits or packet actions in slot t. After slot t is completed, the information revealed by that slot becomes part of the execution history and may be used by the adversary when determining future activations. This adaptive-adversary convention is consistent with prior work on dynamic wakeup, where packets may be activated at adversarially chosen times [20,22,24], and with closely-related dynamic contention-resolution models that allow adaptive arrivals without advance knowledge of fresh random choices [19,5,6,8].
Dynamic Wakeup under Costly Collisions
3
Metrics. We measure latency by the number of slots from the first packet activation through the first success. An execution with no success has infinite latency. Each collision incurs a known per-collision cost C, which is fixed throughout the execution and at least a sufficiently large constant.1 To capture worst-case performance, the adversary chooses C before execution with knowledge of n, subject to a polynomial upper bound C = O(poly(n)) whose degree is fixed but unknown to the packets. The packets know C, but are not given n or an estimate of n; their behavior may therefore depend on C. The collision cost of an execution is C times the number of collision slots before its first success, counting all collision slots if it never succeeds. Each such slot is charged once, not once per transmitting packet. Expected collision cost is the expectation of this sum; for specified slots, we sum only their charges. These charges represent additional delay but are accounted for separately: they neither insert extra slots nor provide feedback, and packet actions and activations retain their usual slot indices. We report worst-case expected latency and expected collision cost separately, over adversaries satisfying the model, with the objective of minimizing their maximum. Notation. An event holds with high probability (w.h.p.) in x if its failure probability is O(x−a ) for any fixed constant a > 0, with the constants in the algorithm chosen accordingly. We use lg for base-2 logarithms and ln for natural logarithms; in asymptotic bounds, log may use any fixed base greater than 1. We write logc y = (log y)c . Our algorithm is parameterized by a fixed constant 0 < ϵ ≤ 1/2, chosen before execution. Constants hidden in asymptotic notation may depend on ϵ. For fixed constants k ≥ 0 and k ′ > 0 independent of ϵ and ′ n, we abbreviate factors of the form logk+k /ϵ n as logΘ(1/ϵ) n. 1.2
Our Results
We design and analyze our algorithm, Lowball, in the dynamic wakeup setting. Fix a constant 0 < ϵ ≤ 1/2 and choose the chunk-size constant d sufficiently large. Our bounds separate according to the per-collision √ cost C. When C exceeds a polylogarithmic threshold in n, Lowball achieves expected collision cost O( C) and expected latency O(C 1/2+ϵ ln C). Below this threshold, both expectations are O(n logΘ(1/ϵ) n). Upper Bound. Our upper-bound result is the following. Theorem 1. Fix a constant 0 < ϵ ≤ 1/2 and choose d sufficiently large. There is a constant K > 0, depending on ϵ, such that against any adaptive adversary, Lowball solves dynamic wakeup with the following bounds. 1. Large-C regime. If C ≥ K lg1/ϵ n, then the expected latency is O(C 1/2+ϵ ln C) and the expected collision √ cost is O( C). 2. Small-C regime. If C < K lg1/ϵ n, then the expected latency and expected collision cost are both O(n logΘ(1/ϵ) n). We emphasize that Lowball does not require n as input and does not need to determine which case of the theorem applies. Classical dynamic-wakeup algorithms provide strong latency guarantees in closely related no-CD models. Jurdziński and Stachowiak [23] give an O(n/ log n) latency bound for fixed error probability when n is unknown. More recently, the DecreaseSlowly wakeup protocol analyzed by De Marco et al. [15] achieves O(k) wakeup time w.h.p., where k is the number of packets activated during the relevant activity interval, even against an adaptive adversary. These results focus on obtaining small latency rather than controlling the cost of collisions. For example, DecreaseSlowly begins with transmission probability 1/2. Thus, if two packets begin the protocol together, there is already a constant probability of collision in the first transmission round, resulting in Ω(C) expected collision cost from that round alone. Our objective is different: we aim to keep√both latency and collision cost small. In the large-C regime, Lowball achieves expected collision cost O( C) together with expected latency O(C 1/2+ϵ ln C). Lower Bound. We also establish a lower bound for age-based batch-fair algorithms: each packet transmits independently with a probability that depends only on C and its local age. In particular, packets activated 1
When C = O(1), an execution’s collision cost is at most a constant times its latency.
4
U. Biswas and M. Young
together use the same sending probability in each slot. Lowball belongs to this class. For an algorithm A, let LA (n, C) and KA (n, C) denote its worst-case expected latency and expected collision cost, respectively, over permitted adversaries activating at most n packets. Define: MA (n, C) := max {LA (n, C), KA (n, C)} . Theorem 2. For every age-based batch-fair algorithm A, every n ≥ 2, and every C, MA (n, C) ≥
√
C/2.
Consequently, when C ≥ K(lg1/ϵ n), the maximum of Lowball’s two expectations is within a factor √ O(C ϵ ln C) of the best possible for this algorithm class. √ The underlying tradeoff also shows that an O( C) worst-case expected collision-cost guarantee requires Ω( C) worst-case expected latency (Section 5). The classical Ω(n/ log n) dynamic-wakeup lower bound of Jurdziński and Stachowiak [23] requires care when applied here. When C is held constant while n grows, their construction can be adapted to give an Ω(n/ log n) expected-latency lower bound for our algorithm class. However, the hidden constant and the required threshold on n may depend on C. Because packets know C, their sending probabilities may change when C changes, even though n remains unknown. Thus, this argument does not give an Ω(n/ log n) lower bound with a hidden constant independent of C when C varies with n, and therefore does not contradict our large-C upper bound. We make this distinction explicit in Section 5.
2
Related Work
The wakeup problem has been studied extensively in both static and dynamic settings [13,3]. In the static setting, where all packets are initially active, Willard [31] gives an upper bound of lg lg n + O(1) for fair algorithms with collision detection, together with a matching lower bound. Without collision detection, Kushilevitz and Mansour [26,25] establish an Ω(log n) expected-latency lower bound, while Newport [27,28] gives Ω(log n) expected latency and Ω(log2 n) latency w.h.p. for general randomized algorithms. Bar-Yehuda et al. [4] provide matching upper bounds of O(log n) expected latency and O(log2 n) latency w.h.p.. Biswas and Young [12] study static wakeup with per-collision cost C and give an algorithm with expected latency O(C 1/2+2ϵ ) and expected collision cost O(C 1/2+ϵ ) when C is sufficiently large with respect to n; otherwise, both costs are polylogarithmic in n. The dynamic setting is substantially more challenging because packets may become active at arbitrary times and execute according to different local clocks. Gasieniec et al. [20] study wakeup under different synchronization assumptions, including settings in which processors begin their local clocks at different activation times. De Marco et al. [17,18] study deterministic wakeup in the locally synchronous model, where no global clock is available, processors may be activated at different times, and the number of processors is unknown. Jurdziński and Stachowiak [24] study dynamic wakeup on the classical multiple-access channel when stations may become active at arbitrary times and do not have access to a global clock or collision detection. They establish an Ω(log2 n) expected-latency lower bound for Las Vegas algorithms, even when stations know the exact value of n and have distinct identifiers, contrasting with the Ω(log n) lower bound when all stations begin simultaneously. They also describe a matching O(log2 n) Las Vegas upper bound under the assumption that stations know a polynomial upper bound on n. In earlier work, Jurdziński and Stachowiak [22] study the effects of global clocks, knowledge of n, and packet identifiers. Most relevant to our setting, when n is unknown and there is no global clock, collision detection, or packet identifiers, they give an algorithm with fixed constant error probability ε and latency O(n/ log n); their nearly linear lower bound also applies in this weaker-information setting. Wakeup has also been studied under substantial modifications to the standard communication model. Under the SINR model and assuming knowledge of a polynomial upper bound on n, Jurdziński and Stachowiak [24] obtain Monte Carlo and Las Vegas bounds of O(log2 n/ log log n), while a deterministic algorithm requires O(log2 n) latency [21]. Chlebus et al. [14] study dynamic wakeup over multiple channels and obtain latency O(n1/b ln(1/ε)) using b > 1 channels. Preliminary work. Closely related preliminary results appeared at MUSICAL 2026 [12] and in the DSN 2026 Doctoral Forum [11]. The MUSICAL paper studies the static setting, while the two-page DSN Doctoral
Dynamic Wakeup under Costly Collisions
5
Fig. 1. Illustration of some iterations of Lowball. Each iteration consists of a fixed-length growing phase Gk (in orange) followed by a shrinking phase Sk (in blue) containing 2k chunks. The top arrows illustrate the common growing-phase schedule, while the bottom arrows illustrate the shrinking phases across successive iterations. Thus, the growing-phase length remains fixed, while the shrinking-phase length doubles across iterations.
Forum paper reports an early approach to dynamic wakeup. The present paper substantially strengthens these results by providing a full dynamic algorithm and analysis that establish the guarantees of Theorem 1. Finally, we highlight work on the closely related problem of contention resolution, where wakeup requires only one successful transmission, whereas contention resolution requires all active packets to eventually succeed (see [13,3]). Several dynamic contention-resolution works consider models quite similar to ours, including asynchronous arrivals, no collision detection, and limited knowledge of the number of devices. Yu et al. [32] study adversarial asynchronous arrivals without a global clock or collision detection, while Bender et al. [7] and De Marco et al. [15] obtain strong throughput guarantees in dynamic settings without collision detection. Of particular relevance to wakeup, the DecreaseSlowly protocol analyzed by De Marco et al. [15] achieves O(k) wakeup time w.h.p. under adaptive activations, but does not seek to control collision cost. De Marco et al. [16] further study deterministic non-adaptive contention resolution under asynchronous activations. In the setting with nontrivial per-collision cost, Biswas et al. [9,10] solve the static contention-resolution √ problem with latency and expected collision cost Õ(n C); however, they do not address the dynamic setting. Moreover, their algorithm assumes collision detection and relies on this feedback to adjust sending probabilities, which is unavailable in our model. Anderton et al. [1] further show that collisions can significantly degrade the performance of common backoff algorithms for contention resolution.
3
Algorithm Specification ϵ
Set w0 = 2C . We call the algorithm Lowball because it deliberately “lowballs” the initial sending probaϵ bility, starting each packet at 1/w0 = 2−C to limit the risk of costly early collisions. The execution proceeds through a sequence of iterations. Each iteration k consists of two phases (as shown in Figure 1): a growing phase Gk , followed by a shrinking phase Sk . These names refer to the batch’s contribution to contention. During Gk , each packet’s sending probability increases geometrically, so the batch’s contribution to contention grows. During Sk , each packet’s sending probability decreases
6
U. Biswas and M. Young
geometrically, so the batch’s contribution to contention shrinks. The aggregate contention in the system need not be monotone, since different batches may be in different phases. More specifically, during Gk , the sending probability increases from 1/w0 to a value in (1/2, 1]. During Sk , the sending probability starts at 1 and gradually decreases. The length of the growing phase is the same in every iteration, while the length of the shrinking phase doubles √ from one iteration to the next. Each packet divides its local execution into chunks of m = ⌈d C ln C⌉ consecutive slots, where d > 0 is a sufficiently large constant. A packet uses the same sending probability throughout a chunk, making a fresh independent transmission decision in each slot. Packets activated at different times need not have aligned chunks. All phase lengths below are the full prescribed lengths; the execution stops at the first success. Growing phase. For every k ≥ 0, the growing phase Gk consists of ⌊lg w0 ⌋ + 1 = ⌊C ϵ ⌋ + 1 chunks. In chunk i, for i = 0, 1, . . . , ⌊lg w0 ⌋, each packet sends independently in every slot with probability 2i /w0 (Lines 5–8). It doubles after each chunk (Line 11), with final value 2⌊lg w0 ⌋ /w0 ∈ (1/2, 1]. Thus, every growing phase has length: |Gk | = m (⌊lg w0 ⌋ + 1) = Θ C 1/2+ϵ ln C .
Shrinking phase. For every k ≥ 0, the shrinking phase Sk consists of 2k chunks. In chunk j, for j = 0, 1, . . . , 2k − 1, each packet sends independently in every slot with probability 2−j (Lines 13–15). Thus, the sending probability begins at 1 and is halved after every chunk. The length of Sk is: √ |Sk | = m2k = Θ 2k C ln C . A packet proceeds through iterations (Gk , Sk ), for k = 0, 1, 2, . . ., until a successful transmission occurs. Batches and Contention. Packets activated at the same time form a batch. Pb Let b ≤ n be the number of batches activated during the execution, and let ni be the size of batch i. Thus, i=1 ni ≤ n; some packets may still be inactive at the first success. Packets in the same batch follow the phase sequence G0 , S0 , G1 , S1 , . . . in lockstep, beginning at the batch’s activation time. For any reached global slot t,Plet pu (t) denote the sending probability of an active packet u. The contention in slot t is Con(t) := u pu (t), where the sum is over the active packets. Let fi (t) denote the contention contributed by batch i. We Pbindex batches in order of activation, so f1 is the contribution of the first batch activated. Then Con(t) = i=1 fi (t), where a batch not yet activated contributes 0. We say that fi is in a growing or shrinking phase when its packets execute that phase of Lowball. √ Definition 1. Fix constants α ≥ 1 and β ≥ 8α, and assume C is sufficiently large that β/ C ≤ 1/2. The good contention region is: α β G= √ ,√ . C C √ A slot t has√ low contention if Con(t) < α/ C, good contention if Con(t) ∈ G, and high contention if Con(t) > β/ C. Every reached slot falls into exactly one of these categories. 3.1
Context and Overview
We now provide intuition for the design of Lowball and explain how its growing and shrinking phases control both latency and collision cost in the dynamic setting. A Baseline via Backoff. A natural approach to symmetry breaking is to “back off” by gradually decreasing each packet’s sending probability. Classical dynamic-wakeup algorithms obtain strong latency guarantees using such schedules [22,15]. For example, the DecreaseSlowly protocol analyzed by De Marco et al. [15] begins with transmission probability 1/2. If two packets begin together, the first transmission round already has a constant probability of collision and therefore incurs Ω(C) expected collision cost. Thus, a key obstacle is setting the initial sending probability suitably low. Since n is unknown, however, it is not clear how low that probability should be.
Dynamic Wakeup under Costly Collisions
7
Design Choices and Overview. We now explain the choice of initial probability, the role of the shrinking phases, and why success during the first batch’s initial growing phase is very likely in the large-C case of Theorem 1. √ Aiming for Good√Contention. Suppose a slot has contention Con(t) = Θ(1/ C). Its conditional success probability is Θ(1/ C), whereas its collision probability is O(1/C). Thus, the slot’s conditional expected √ contribution to collision cost is only O(1). More generally, Lemma 2 shows that encountering m = Θ( C ln C) good-contention slots without a success has probability at most C −αd/e . This motivates both the good contention region and the chunk length. Setting the Initial Sending Probability. For one batch of n packets sending with probability 1/w, the ϵ contention is n/w. We choose w0 = 2C , giving the two cases in Theorem 1: √ 1. Large-C regime: C ≥ K lg1/ϵ n. For sufficiently large K, this implies n/w0 ≤ 1/ C (Lemma 11). Thus, both the initial contention and the contribution of newly activated packets while they remain in their first chunks are small. 2. Small-C regime: C < K lg1/ϵ n. Here C = O(lg1/ϵ n). The general latency bound below, together with the fact that each slot contributes at most C to collision cost, gives O(n logΘ(1/ϵ) n) for both expectations. These cases are only for the analysis; Lowball executes the same schedule in both. Controlling Long Executions. In the dynamic setting, growing phases of other batches can interrupt the decrease in contention during the first batch’s shrinking phases. However, growing phases have fixed length while shrinking phases become progressively longer. Once a shrinking phase is sufficiently long, the execution must contain a long interval in which every active batch is shrinking. Lemmas 5–9 show that each such completed phase contains m consecutive good-contention slots. Consequently, completing j sufficiently late shrinking phases without a success requires surviving at least jm good-contention slots. The probability of this event decreases geometrically in j, yielding: O nC 1/2+2ϵ ln C lg3 n expected remaining latency (Lemma 10). This bound applies in both cases of the main theorem: it gives the small-C guarantee and controls rare long executions in the large-C case. Success During the First Growing Phase. Let L denote the latency. Suppose C ≥ K lg1/ϵ n, and let g be the length of the first batch’s initial growing phase. Through slot g, every activated packet remains in √ its own initial growing phase. If no success occurs, contention must eventually rise from at most 1/ C to at least 1/2. The first such crossing is preceded by m slots with contention in [1/8, 1/2). Each of these slots has a constant conditional success probability. Therefore, we can show (Lemma 11): m Pr(L > g) ≤ exp − . 8e We initially charge g = O(C 1/2+ϵ ln C) slots, while any remaining duration is incurred only on this exponentially unlikely event. Combining this probability with Lemma 10 shows that executions continuing beyond g contribute only O(1) additional slots in expectation. Hence, we have (Lemma 12): E[L] = O C 1/2+ϵ ln C . √ Handling High Contention. Lemma 13 shows that low- and good-contention slots contribute only O( C) expected collision cost in total. For high contention in the large-C case, we again split the execution at slot g. Reaching high contention by then requires surviving m good-contention slots, an event of probability at most C −αd/e . After g, the probability that the execution continues is at most exp(−m/(8e)). These probabilities are small enough to offset the possible collision cost incurred in the corresponding executions. Thus, high-contention slots contribute only O(1) expected collision cost (Lemma 14), giving expected collision cost over the execution √ O( C).
8
U. Biswas and M. Young
Lowball // Initialization ϵ w0 ← 2C √ 2 m ← ⌈d C ln C⌉ 3 k ←0 1
4
5 6 7 8 9 10 11
12 13 14 15 16 17 18 19
// Iterations while true do // Growing Phase Gk wcur ← w0 while wcur ≥ 1 do for slot i = 1 to m do Send packet with probability 1/wcur if success then Terminate wcur ← wcur /2 // Shrinking Phase Sk wcur ← 1 for s = 0 to 2k − 1 do for slot i = 1 to m do Send packet with probability 1/wcur if success then Terminate wcur ← 2wcur k ←k+1
Relation to Backoff. Our algorithm uses familiar backoff-and-backon probability updates, but the central challenge is to organize them around both latency and√collision cost. Rather than seek a constant success √ probability per slot, we target contention of order 1/ C, balancing a success probability of order 1/ C against a collision probability of only O(1/C). In the large-C regime, the low initial sending probability keeps costly contention unlikely during the first batch’s initial growing phase, while the increasingly long shrinking phases control executions that survive that phase. This gives bounds on both expected latency and expected collision cost. Role of ϵ. The parameter ϵ is a fixed constant chosen before execution, with 0 < ϵ ≤ 1/2. It controls ϵ the initial window w0 = 2C . Taking a smaller value shortens each growing phase and improves the large-C latency bound, but raises the exponent 1/ϵ in the threshold K lg1/ϵ n and the polylogarithmic exponent in the small-C bound. The upper limit ϵ ≤ 1/2 comes from controlling executions that survive the first batch’s initial growing phase. Their probability is at most exp(−m/(8e)) (Lemma 11), whereas the bound on expected remaining ϵ latency contains a factor of n (Lemma 10). In the large-C regime, our choice of K gives n ≤ 2C /2 . The survival probability must decrease √ fast enough to offset this factor and the√remaining polynomial and logarithmic factors. Since m = Θ( C ln C), the restriction ϵ ≤ 1/2 ensures C ϵ ≤ C, so the exponential decay dominates. This comparison is used in Lemmas 12 and 14. For any fixed ϵ > 1/2, however, C ϵ eventually grows faster √ than C ln C, so this comparison no longer gives the required bound.
4
Upper-Bound Analysis
In this section, we analyze the performance of Lowball for the dynamic wakeup problem.
Dynamic Wakeup under Costly Collisions
4.1
9
Preliminaries and Helper Lemmas
For our analysis to handle an adaptive adversary, we need to define the notion of a history. For each slot s, let As denote the set of packets activated in slot s, let Ts denote the set of packets that transmit in that slot, and let Ys denote the resulting channel outcome. A pre-transmission history for slot t is a tuple: ht = (A1 , T1 , Y1 , . . . , At−1 , Tt−1 , Yt−1 , At ). Thus, ht records the entire execution through the end of slot t − 1, together with the adversary’s activation decision for slot t, but not the transmission decisions in slot t. For any reachable history ht , the set of active packets and their sending probabilities in slot t are fixed. Lemma 1. (Bender et al. [5]) Fix any reachable pre-transmission history ht . Suppose that, conditioned on ht , each active packet transmits independently in slot t with probability at most 1/2. Then: Pr(success in slot t | ht ) ≥
Con(t) . e2Con(t)
Lemma 2. For every integer r ≥ 1, the probability that Lowball encounters at least r good-contention slots without a successful transmission in any of the first r such slots is at most: r α 1− √ . e C Proof. Fix any reachable pre-transmission history ht under which slot t has good contention. The active packets and their sending probabilities are fixed by ht , and their transmission decisions in slot t are independent. By Definition 1: α β 1 √ ≤ Con(t) ≤ √ ≤ . 2 C C Every sending probability is at most Con(t), so Lemma 1 gives: Pr(success in slot t | ht ) ≥
Con(t) α ≥ √ . e2Con(t) e C
√ Let p = α/(e C). For j ≥ 1, let Ej be the event that the execution encounters at least j good-contention slots and remains unsuccessful through the end of the j-th. Let E0 be the certain event. Reaching the j-th good-contention slot requires Ej−1 to occur. For every pre-transmission history leading to that slot, its conditional failure probability is at most 1 − p. Averaging over those histories gives: Pr(Ej ) ≤ (1 − p) Pr(Ej−1 ). If another success occurs first, or no further good-contention slot is reached, then Ej does not occur. Iterating the bound gives, for every integer r ≥ 1: r α Pr(Er ) ≤ (1 − p)r = 1 − √ e C as claimed. P Our collision-cost analysis uses the following fact. For a fixed total probability i pi , the sum of all products of any fixed number r of distinct probabilities is maximized when the probabilities are equal. Lemma 3. Fix an integer r ∈ {2, . . . , N } and a value λ ∈ [0, N ]. Among all choices of probabilities PN p1 , . . . , pN ∈ [0, 1] satisfying i=1 pi = λ,, the quantity: X Y pi S⊆[N ] i∈S |S|=r
is maximized when p1 = p2 = · · · = pN = λ/N .
10
U. Biswas and M. Young
Proof. Consider any two probabilities pi and pj , while holding all other probabilities fixed. For ease of presentation, define: X Y R2 = pℓ , T ⊆[N ]\{i,j} ℓ∈T |T |=r−2
X
R1 =
Y
pℓ ,
T ⊆[N ]\{i,j} ℓ∈T |T |=r−1
and X
R0 =
Y
pℓ .
T ⊆[N ]\{i,j} ℓ∈T |T |=r
Then: X Y
pℓ = pi pj R2 + (pi + pj )R1 + R0 .
S⊆[N ] ℓ∈S |S|=r
Replace pi and pj by their average: p′i = p′j =
pi + p j . 2
PN Since p′i + p′j = pi + pj , this replacement preserves the constraint ℓ=1 pℓ = λ. It also leaves the term (pi + pj )R1 unchanged. Thus, the only term that can change is pi pj R2 . Moreover: p′i p′j =
pi + p j 2
2 = pi pj +
(pi − pj )2 ≥ pi pj . 4
Since R2 ≥ 0, averaging pi and pj does not decrease the quantity being maximized. Now repeatedly apply this operation to a largest and a smallest probability among p1 , . . . , pN . Let µ = λ/N . Each averaging step decreases: N X (pi − µ)2 i=1
by exactly: (pi − pj )2 , 2 where pi and pj are the two probabilities being averaged. Since this sum is nonnegative, the difference between the largest and smallest probabilities tends to zero. Their average remains µ, so: p1 , . . . , pN −→ µ =
λ . N
The quantity being maximized never decreases during this process. Since it is a continuous function of p1 , . . . , pN , its value therefore converges to its value at p1 = · · · = pN = λ/N . Hence, the equal choice has value at least as large as the original choice and therefore maximizes the quantity. Lemma 4. Fix any reachable pre-transmission history under which slot t has low or good contention. The conditional collision probability Pcol (t) satisfies Pcol (t) = O Con(t)2 = O(1/C). Proof. Condition on the stated history, and let λ = Con(t). Suppose N packets are active, with sending probPN abilities p1 , . . . , pN , so i=1 pi = λ. These probabilities are fixed, and the packets transmit independently. All probabilities below are conditional on this history. If N < 2, no collision can occur, so assume N ≥ 2.
Dynamic Wakeup under Costly Collisions
11
Let Xt denote the number of packets that transmit in slot t. For any r ∈ {2, . . . , N }, note that: ! X Y Y Pr(Xt = r) = pi (1 − pj ) S⊆[N ] |S|=r
≤
i∈S
X Y
j ∈S /
pi
S⊆[N ] i∈S |S|=r
r N λ N r λr ≤ . r! ≤
The second-to-last line follows from Lemma 3, since the right-hand side is maximized when all sending probabilities are equal to λ/N . The last line follows from Nr ≤ N r /r!. A collision occurs when Xt ≥ 2. So: Pcol (t) = Pr(Xt ≥ 2) =
N X
Pr(Xt = r)
r=2
≤
N X λr r=2 λ
r!
≤ e − 1 − λ, where the last line follows from the Taylor expansion: eλ =
∞ X λr r=0
r!
=1+λ+
∞ X λr r=2
r!
.
√ Since t has low or good contention, we have λ = Con(t) ≤ β/ C. For sufficiently large C, this implies λ ≤ 1/2. By Taylor expansion: ∞ ∞ X X λr λj eλ − 1 − λ = = λ2 . r! (j + 2)! r=2 j=0 For λ ≤ 1/2, the remaining series is bounded by a constant, and hence: eλ − 1 − λ = O(λ2 ). Consequently: Pcol (t) = O λ2 = O Con(t)2 , √ and since Con(t) ≤ β/ C, we obtain Pcol (t) = O(1/C). 4.2
Latency Analysis
We first use the shrinking phases to bound the expected remaining latency from any history reached during or immediately after the first batch’s initial growing phase. When C ≥ K lg1/ϵ n, the probability of completing that phase without a success is at most exp(−m/(8e)). Combining these bounds gives the sharper expectedlatency guarantee for the large-C regime. Let us number the slots from the first activation (thus, we can ignore any prefix of slots where no packets are active). Recall that phase lengths refer to their full prescribed lengths, without truncation at a success. Let g denote the length of a growing phase. Since each growing phase consists of ⌊lg w0 ⌋ + 1 chunks, each of length m, we have g = m (⌊lg w0 ⌋ + 1) = Θ(C 1/2+ϵ ln C)
12
U. Biswas and M. Young
For each k ≥ 0, let Sk denote the interval prescribed for the first batch’s k-th shrinking phase, so |Sk | = m2k . Any statement concerning all of Sk applies only when the execution reaches and completes that phase. Definition 2. An interval of consecutive slots J = [τ, τ + ℓ) ⊆ Sk is a clean shrinking window if no active batch is in a growing phase in any slot of J. Such a window is maximal if it cannot be extended within Sk while retaining this property. Set:
m l √ D = lg n C/β + 1.
Thus, D= O(lg n + lg C). Lemma 5. Let I be any interval of ℓ consecutive slots that the execution reaches, with ℓ ≥ 2g. For any batch, at most lg ℓ + O(1) of its growing phases intersect I. Proof. Suppose r growing phases of the batch intersect I. The claim is immediate if r ≤ 1. Otherwise, between these phases lie r − 1 consecutive shrinking phases. Their total length is at least: m 1 + 2 + · · · + 2r−2 = m 2r−1 − 1 . The first intersecting growing phase can begin before I, but by fewer than g slots. Similarly, the last can end fewer than g slots after I. Consequently: m 2r−1 − 1 ≤ ℓ + 2g ≤ 2ℓ. It follows that: r ≤ 1 + lg(1 + 2ℓ/m) ≤ lg ℓ + O(1), where the last step uses m ≥ 1 and ℓ ≥ 1. Lemma 6. Let J = [τ, τ + ℓ) be a clean shrinking window with ℓ ≥ (D + 2)m and 1 ≤ Con(τ ) ≤ n. Then J contains m consecutive slots of good contention. Proof. No new batch can be activated during J, since it would begin in a growing phase. All active batches remain in shrinking phases, so Con(t) is nonincreasing throughout √ √ J. Since β/ C ≤ 1/2 (recall Definition 1), we have Con(τ ) > β/ C. Between slots τ and τ + (D + 1)m, each active batch crosses at least D of its own chunk boundaries. Each such boundary halves its contribution, so: Con(τ ) n β ≤ D <√ . D 2 2 C √ √ Let t be the first slot in this interval with Con(t) ≤ β/ C. The preceding slot has Con(t − 1) > β/ C. Between two consecutive slots √ of J, each batch’s contribution either stays unchanged or halves. Therefore, we have that Con(t) > β/(2 C). During the m consecutive slots beginning at t, each batch crosses at most one further chunk boundary. Thus, for every s ∈ [t, t + m): Con (τ + (D + 1)m) ≤
Con(s) ≥
Con(t) β α > √ ≥√ , 2 4 C C
where the last inequality uses β ≥ 8α. Since every active batch remains in a shrinking phase throughout J and no new √ batch is activated there, the aggregate contention is nonincreasing on J. Hence, Con(s) ≤ Con(t) ≤ β/ C. These m slots lie in J, since t ≤ τ + (D + 1)m and ℓ ≥ (D + 2)m, and hence all have good contention. Lemma 7. Let k ∗ = ⌈lg n + ϵ lg C + 3 lg lg n + c⌉, where c > 0 is a sufficiently large constant. For every k ≥ k ∗ , if the execution reaches the end of Sk , then Sk contains a maximal clean shrinking window of length at least (D + 2)m.
Dynamic Wakeup under Costly Collisions
13
Proof. Let ℓ = |Sk | = m2k . Since g/m ≤ C ϵ + 1, the choice of k ∗ ensures ℓ ≥ 2g. By Lemma 5, each batch has at most k + lg m + O(1) growing phases intersecting Sk . There are at most n batches, so the total number Q of such phases satisfies Q = O(n(k + lg m)). These growing phases cover at most Qg slots of Sk . Removing the covered slots leaves at most Q + 1 maximal clean shrinking windows. If every such window had length less than (D + 2)m, then: ℓ < Qg + (Q + 1)(D + 2)m. Dividing by m and using the bounds on Q and g/m would give, for a fixed constant c1 > 0: 2k < c1 n(k + lg m)(C ϵ + D + 2). At k = k ∗ , the left-hand side satisfies:
(1)
∗
2k ≥ 2c nC ϵ lg3 n. On the other hand, C = O(poly(n)) implies lg m = O(lg n), D = O(lg n), and k ∗ = O(lg n). Since C ϵ ≥ 1, the right-hand side of Equation (1) is: c1 n(k ∗ + lg m)(C ϵ + D + 2) = O nC ϵ lg2 n . ∗
For sufficiently large c and n, this is smaller than 2k . Moreover, 2k /(k + lg m) is increasing for k ≥ k ∗ , so Equation (1) cannot hold for any k ≥ k ∗ . Therefore, at least one maximal clean shrinking window in Sk has length at least (D + 2)m. Lemma 8. Let J = [τ, τ + ℓ) be a maximal clean shrinking window inside a completed phase Sk . Then 1 ≤ Con(τ ) ≤ n. Proof. The upper bound follows trivially because at most n packets are active, each with sending probability at most 1. If J begins at the start of Sk , then the first batch has just entered its shrinking phase. Its sending probability is 1, so Con(τ ) ≥ f1 (τ ) = n1 ≥ 1. Otherwise, τ − 1 also lies in Sk . By maximality of J, at least one batch is in a growing phase at τ − 1, whereas every active batch is in a shrinking phase at τ . Hence some batch i has just entered a shrinking phase at τ . It contributes fi (τ ) = ni ≥ 1, giving the lower bound. Lemma 9. Let k ∗ = ⌈lg n + ϵ lg C + 3 lg lg n + c⌉, where c > 0 is a sufficiently large constant. For every k ≥ k ∗ , if the first batch completes Sk , then that phase contains m consecutive slots of good contention. Proof. By Lemma 7, Sk contains a maximal clean shrinking window J = [τ, τ + ℓ) with ℓ ≥ (D + 2)m. Lemma 8 gives 1 ≤ Con(τ ) ≤ n. Lemma 6 therefore supplies the required m good-contention slots inside J ⊆ Sk . For the remaining latency arguments, let L denote the latency, with L = ∞ if no success occurs. Let Bk be the number of slots prescribed by Lowball for iterations 0 through k of the first batch, counting every phase at its full length. Thus, we have: Bk = (k + 1)g + m(2k+1 − 1) = O 2k C 1/2+ϵ ln C .
(2)
For every k ≥ 0 and every execution, the number of slots actually executed among the first batch’s iterations 0, . . . , k is min{L, Bk }. In particular, if L > Bk , then all Bk prescribed slots of these iterations are completed without a success. Lemma 10. For every reachable pre-transmission history hs with 1 ≤ s ≤ g + 1, the expected number of remaining slots, including slot s, satisfies E[L − s + 1 | hs ] = O(nC 1/2+2ϵ ln C lg3 n). Proof. Fix such a history hs . All shrinking phases Sk∗ , Sk∗ +1 , . . . begin at or after s. For j ≥ 1, the event L > Bk∗ +j−1 requires completing the first j of these phases without a success. By Lemma 9, these disjoint phases contain at least jm good-contention slots.
14
U. Biswas and M. Young
At every reached good-contention slot t, conditioned on any pre-transmission history h√t , the active packets transmit independently with fixed probabilities. Each probability is at most Con(t) ≤ β/ C ≤ 1/2. Lemma 1 therefore gives: α Con(t) Pr(success in slot t | ht ) ≥ 2Con(t) ≥ √ . e e C By Lemma 9, completing these j shrinking phases without a success requires remaining unsuccessful through at least jm good-contention slots. Conditioned √ on the pre-transmission history before any such slot, Lemma 1 gives a success probability of at least α/(e C). Thus,√each time another good-contention slot is reached, its conditional probability of failure is at most 1 − α/(e C). Define the probability q = C −αd/e , where recall d is the chunk-size constant. Conditioning successively on the history before each of the first jm good-contention slots therefore gives: jm αjm ≤ exp − √ ≤ C −jαd/e = q j , e C √ where the second inequality uses 1 − x ≤ e−x and the third uses m ≥ d C ln C. Grouping the remaining slots by the prescribed endpoints gives: X E[L − s + 1 | hs ] ≤ Bk∗ − s + 1 + (Bk∗ +j − Bk∗ +j−1 ) q j
Pr (L > Bk∗ +j−1 | hs )≤
α 1− √ e C
j≥1
X
≤ Bk∗ +
j
q Bk∗ +j .
(3)
j≥1 ∗
By the definition of k ∗ , 2k = O(nC ϵ lg3 n). Thus, Equation (2) gives, for every j ≥ 0: Bk∗ +j = O 2j nC 1/2+2ϵ ln C lg3 n . Choose d sufficiently large that q ≤ 1/4. Then O nC 1/2+2ϵ ln C lg3 n .
j j≥0 (2q) ≤ 2, so Equation (3) implies E[L − s + 1 | hs ] =
P
The preceding lemma controls the rare executions that continue for a long time. We now show that, in the large-C regime, reaching the end of the first batch’s initial growing phase without a success is exponentially unlikely. Lemma 11. Assume C ≥ K(lg1/ϵ n), where K > 0 is a sufficiently large constant depending only on ϵ. The probability that Lowball completes the first batch’s initial growing phase without a success satisfies Pr(L > g) ≤ exp (−m/(8e)). Proof. We first bound the contribution of newly activated packets. Choose K large enough that K ϵ ≥ 2 and lg C ≤ C ϵ whenever C ≥ K; such a choice is possible because ϵ > 0 is a fixed constant. Since C ≥ K(lg1/ϵ n) and n ≥ 2, we have lg n ≥ 1 and hence C ≥ K. Moreover, we have: C ϵ ≥ K ϵ lg n ≥ 2 lg n, where the last inequality uses our choice K ϵ ≥ 2; thus, lg n ≤ C ϵ /2. Using this inequality and recalling that ϵ w0 = 2C , we have: ϵ ϵ n 1 = 2lg n−C ≤ 2−C /2 ≤ 2−(lg C)/2 = √ . w0 C
(4)
Suppose L > g. Through slot g, every activated packet is still in its initial growing phase. The first batch’s sending probability in its final chunk is 2⌊lg w0 ⌋ /w0 > 1/2. Thus, there is a first slot τ ≤ g with Con(τ ) ≥ 1/2. During the first m slots, every activated packet is still in its initial chunk, so: Con(t) ≤
n 1 1 ≤√ < . w0 2 C
Dynamic Wakeup under Costly Collisions
15
Hence, it must be the case that τ > m. Fix t ∈ [τ − m, τ ). Since successive chunk boundaries of a packet are m slots apart, a packet already active at t doubles its sending probability at most once between slots t and τ . A packet activated after t is still in its first chunk at τ . Consequently: n 1 1 ≤ Con(τ ) ≤ 2Con(t) + ≤ 2Con(t) + √ , 2 w0 C where the last inequality follows from Equation 4. For sufficiently large C, this implies: Con(t) ≥
1 1 1 − √ ≥ . 4 2 C 8
Also, Con(t) < 1/2 by the choice of τ . Thus, L > g requires remaining unsuccessful through at least m slots with contention in [1/8, 1/2). For any slot t with contention in [1/8, 1/2), conditioned on the pre-transmission history ht , every active packet has sending probability at most Con(t) < 1/2. Lemma 1 therefore gives: Pr(success in slot t | ht ) ≥
1 Con(t) ≥ . 2Con(t) 8e e
Thus, whenever the execution reaches another slot in this contention range, conditioned on everything that has happened beforehand, the probability of remaining unsuccessful in that slot is at most 1 − 1/(8e). Applying this bound successively to m such slots gives: m 1 Pr(remain unsuccessful through m such slots) ≤ 1 − . 8e Since L > g implies that the execution remains unsuccessful through at least m such slots: m m 1 Pr(L > g) ≤ 1 − , ≤ exp − 8e 8e where the final inequality uses 1 − x ≤ e−x . Lemma 12. Assume C ≥ K(lg1/ϵ n), where K > 0 is a sufficiently large constant depending only on ϵ. The expected latency of Lowball is O C 1/2+ϵ ln C . Proof. Choose K large enough to satisfy the requirements of Lemma 11 and K ϵ ≥ 2. Executions ending by slot g use, of course, at most g slots. For every pre-transmission history hg+1 reached after surviving the first growing phase, Lemma 10 gives: E[L − g | hg+1 ] = O nC 1/2+2ϵ ln C lg3 n . Averaging over these histories and applying Lemma 11, we obtain: E[L] ≤ g + Pr(L > g) O nC 1/2+2ϵ ln C lg3 n m ≤ g + exp − O nC 1/2+2ϵ ln C lg3 n . 8e Since C ≥ K(lg1/ϵ n), we have: C ϵ ≥ K ϵ lg n ≥ 2 lg n. ϵ
ϵ
This implies that lg n ≤ C2 , which in turn implies n ≤ 2C /2 = exp lg3 n ≤
1 3ϵ C = O C 3ϵ . 8
ln 2 ϵ 2 C
. Similarly, observe that:
(5)
16
U. Biswas and M. Young
We then have that: m O nC 1/2+2ϵ ln C lg3 n exp − 8e m ln 2 ϵ 1/2+5ϵ = O exp − exp C C ln C 8e 2 ln 2 ϵ d√ 1/2+5ϵ = O exp C − C ln C C ln C . 2 8e √ √ where the last line follows by plugging in m ≥ d C ln C. Since 0 < ϵ ≤ 1/2, we have C ϵ ≤ C and for sufficiently large C, we have: d √ ln 2 ϵ d√ C − C ln C ≤ − C ln C. 2 8e 16e The corresponding exponentially-small term kills the C 1/2+5ϵ ln C factor, so the expected contribution after slot g in Equation 5 is O(1), and so we have shown: E[latency] ≤ E[L] ≤ g + O(1) = O C 1/2+ϵ ln C , as claimed. 4.3
Collision Cost Analysis
We first bound the collision cost contributed by low- and good-contention slots over the entire execution. For high-contention slots, we split the execution at the end of the first batch’s initial growing phase. Reaching high contention during that phase is unlikely, and the latency analysis already bounds both the probability of surviving the phase and the expected duration of any continued execution. As in the latency analysis, L denotes the slot of the first success and g = m(⌊lg w0 ⌋ + 1) is the full prescribed length of the first growing phase. √ Lemma 13. The expected collision cost contributed by slots with low or good contention is O( C). Proof. Fix any reachable pre-transmission history ht under which slot t has low or good contention. Conditioned on ht , the active packets and their sending probabilities are fixed, and their transmission decisions in slot t are independent. Let λ = Con(t). Then: 1 β 0≤λ≤ √ ≤ . 2 C Let Pcol (t | ht ) and Psuc (t | ht ) denote the conditional probabilities of a collision and a success in slot t, respectively. Lemmas 4 and 1 give: Pcol (t | ht ) = O(λ2 ) and Psuc (t | ht ) ≥ λe−2λ . The latter inequality implies: λ2 ≤ λe2λ Psuc (t | ht ). The conditional expected collision-cost contribution of slot t therefore satisfies: CPcol (t | ht ) = O(Cλ2 ) = O(Cλe2λ )Psuc (t | ht ) √ = O( C)Psuc (t | ht ), √ where the last bound uses Cλ ≤ β C and e2λ ≤ e. We now sum these contributions over histories and slots. For each slot t, let Zt = C if the execution reaches slot t, the slot has low or good contention, and a collision occurs; otherwise, let Zt = 0. Let Ft be the event that the first success occurs in slot t and that slot has low or good contention.
Dynamic Wakeup under Costly Collisions
17
Let Ht be the set of reachable pre-transmission histories under which slot t has low or good contention. Conditioning on which history in Ht occurs gives: X Pr(ht ) CPcol (t | ht ). E[Zt ] = ht ∈Ht
Applying the bound above to each term: X √ E[Zt ] = O( C) Pr(ht ) Psuc (t | ht ). ht ∈Ht
Every history in Ht reaches slot t, so no success has occurred before that slot. Hence, if a success occurs in slot t under one of these histories, it is necessarily the first success. Therefore: X Pr(ht ) Psuc (t | ht ) = Pr(Ft ). ht ∈Ht
√
It follows that E[Zt ] = O( C) Pr(F P t ). Finally, the events Ft are pairwise disjoint, since there can be only one first successful slot. Thus, t≥1 Pr(Ft ) ≤ 1. Since the variables Zt are nonnegative, summing over all slots gives: X X √ X √ E Zt = E[Zt ] = O( C) Pr(Ft ) = O( C), t≥1
t≥1
t≥1
as claimed. Lemma 14. Assume C ≥ K(lg1/ϵ n), where K > 0 is a sufficiently large constant depending only on ϵ. For sufficiently large d, the expected collision cost contributed by high-contention slots is O(1). Proof. We use the same choice of K as in Lemma 11, so K ϵ ≥ 2 and lg C ≤ C ϵ whenever C ≥ K. Since n ≥ 2, the condition C ≥ K(lg1/ϵ n) gives C ≥ K and C ϵ ≥ 2 lg n. Hence: ϵ ϵ n 1 = 2lg n−C ≤ 2−C /2 ≤ 2−(lg C)/2 = √ . w0 C
(6)
Let H≤g and H>g be the collision costs contributed by high-contention slots at or before g and after g, respectively. Each is C times the number of collisions in its specified slots. Slots at or before g. Let E be the event that the execution reaches a high-contention slot at or before g. On this event, let t1 be the first such slot. No reached slot among the first m has high contention: every packet activated by then √ is still in its first chunk, so its contribution is 1/w0 and, by Equation 6, the total is at most n/w0 ≤ 1/ C. Hence t1 > m. Fix any t ∈ [t1 − m, t1 ). Through slot g, every activated packet is still in its initial growing phase. A packet active at t doubles its probability at most once between t and t1 , since t1 − t ≤ m and its chunk boundaries are m slots apart. A packet activated after t is still in its first chunk at t1 . Thus: 1 β n √ < Con(t1 ) ≤ 2Con(t) + ≤ 2Con(t) + √ . w0 C C Since t1 is the first high-contention slot, this implies: α β−1 β √ ≤ √ < Con(t) ≤ √ , C 2 C C where the first inequality uses β ≥ 8α and α ≥ 1. Therefore, all m slots in [t1 − m, t1 ) have good contention, and they precede a reached slot, so none contains a success. Consequently, the event E requires encountering at least m good-contention slots without a success. By Lemma 2, we have: m α Pr(E) ≤ 1 − √ e C −αd/e ≤C ,
18
U. Biswas and M. Young
√ where the second inequality follows from 1−x ≤ e−x and m ≥ d C ln C. On E, at most g slots can contribute to H≤g , each contributing at most C; outside E, H≤g = 0. Choose d sufficiently large to satisfy all earlier requirements and αd/e ≥ 3. Since ϵ ≤ 1/2, we have: E[H≤g ] ≤ Cg Pr(E) = O C 3/2+ϵ−αd/e ln C ln C = O(1). =O C Slots after g. If L ≤ g, then the first success occurs during the initial growing phase, so the execution terminates by slot g and H>g = 0. It remains to consider the event L > g. Conditioned on any pre-transmission history hg+1 reached after surviving the initial growing phase, we upper-bound H>g by charging the per-collision cost C to every remaining slot, whether or not it has high contention or contains a collision. Lemma 10 gives: E[H>g | hg+1 ] ≤ C E[L − g | hg+1 ] = O nC 3/2+2ϵ ln C lg3 n . Let Hg+1 be the set of reachable pre-transmission histories for slot g + 1. Since the execution reaches slot g + 1 exactly when L > g: X Pr(hg+1 ) = Pr(L > g). hg+1 ∈Hg+1
Therefore, conditioning on the history at slot g + 1: E[H>g ] =
X
Pr(hg+1 ) E[H>g | hg+1 ]
hg+1 ∈Hg+1
≤ Pr(L > g) O nC 3/2+2ϵ ln C lg3 n m O nC 3/2+2ϵ ln C lg3 n , ≤ exp − 8e
(7)
where the last line follows by Lemma 11. √ ϵ We next bound the remaining factors in terms of C. From n/w0 ≤ 1/ C and w0 = 2C , we have n ≤ ϵ √ 2C / C, which implies that lg n ≤ C ϵ , which in turn implies lg3 n ≤ C 3ϵ . Substituting these two bounds into Equation 7 gives: m 2C ϵ E[H>g ] ≤ exp − O √ C 3/2+2ϵ ln C C 3ϵ 8e C m ϵ C 1+5ϵ = exp − O 2 C ln C 8e = O(1), √ where the last line follows from m ≥ d C ln C and the fact that the exponential decay dominates the remaining polynomial and logarithmic factors. Since E[H≤g ] = O(1) and E[H>g ] = O(1), the expected collision cost contributed by high-contention slots is O(1). Lemma 15. There is a constant K > 0, depending only on ϵ, such that the expected collision cost of Lowball in the dynamic setting satisfies the following bounds. √ 1. If C ≥ K(lg1/ϵ n), then the expected collision cost is O( C). 2. If C < K(lg1/ϵ n), then the expected collision cost is O n logΘ(1/ϵ) n .
Dynamic Wakeup under Costly Collisions
19
Proof. Choose K sufficiently large to satisfy the requirements of Lemma 14. Our analysis treats two cases. Case 1: C ≥ K(lg1/ϵ n). Every slot has low, good, or high contention. Adding the bounds from Lemmas 13 and 14 shows that the expected collision cost over the execution is: √ √ O( C) + O(1) = O( C). Case 2: C < K(lg1/ϵ n). Since K and ϵ are fixed constants, we have: C = O(lg1/ϵ n). Each slot contributes at most C, so the execution’s collision cost is at most CL. Applying Lemma 10 with s = 1 and averaging over the possible initial histories gives that the expected collision cost over the execution is upper-bounded by: C E[L] = O nC 3/2+2ϵ ln C lg3 n . The bound on C gives: C 3/2+2ϵ = O lg3/(2ϵ)+2 n . Thus, the expected collision cost over the execution is bounded by: O n lg3/(2ϵ)+2 n · lg n · lg3 n = O n lg3/(2ϵ)+6 n = O n logΘ(1/ϵ) n , since 3/(2ϵ) + 6 = Θ(1/ϵ) for 0 < ϵ ≤ 1/2. Theorem 1. Fix a constant 0 < ϵ ≤ 1/2 and choose d sufficiently large. There is a constant K > 0, depending only on ϵ, such that against any adaptive adversary satisfying our model, Lowball solves the dynamic wakeup problem with the following bounds. √ 1. If C ≥ K(lg1/ϵ n), then the expected latency is O(C 1/2+ϵ ln C) and the expected collision cost is O( C). 2. If C < K(lg1/ϵ n), then the expected latency and expected collision cost are both O(n logΘ(1/ϵ) n). Proof. Choose K sufficiently large to satisfy the requirements of Lemmas 12 and 15. 1/2+ϵ Case 1: C ≥ K(lg1/ϵ ln C). By Lemma 15, the expected √ n). By Lemma 12, the expected latency is O(C collision cost is O( C).
Case 2: C < K(lg1/ϵ n). Again, since K and ϵ are fixed constants, we have C = O(lg1/ϵ n). Applying Lemma 10 with s = 1 and averaging over the possible initial histories gives: E[L] = O nC 1/2+2ϵ ln C lg3 n . The bound on C implies: C 1/2+2ϵ = O lg1/(2ϵ)+2 n . Therefore, we have: E[L] = O n lg1/(2ϵ)+2 n · lg n · lg3 n = O n lg1/(2ϵ)+6 n = O n logΘ(1/ϵ) n , since 1/(2ϵ) + 6 = Θ(1/ϵ) for 0 < ϵ ≤ 1/2. By Lemma 15, the expected collision cost is: O(n logΘ(1/ϵ) n), which completes the argument.
20
5
U. Biswas and M. Young
Lower Bound
We first prove a tradeoff between latency and collision cost, then explain the classical dynamic-wakeup lower bound when the per-collision cost C is fixed and n grows. Algorithm class and metrics. We consider age-based batch-fair algorithms. For each value of C, such an algorithm A specifies probabilities: p1 (C), p2 (C), p3 (C), . . . . In its j-th slot after activation, a packet transmits with probability pj (C), using fresh randomness independent of the other packets. The probabilities depend only on C and local age, not on n, global time, or previous transmission outcomes. Thus, packets activated together use the same probability in each slot, which is the meaning of batch fairness here. Lowball belongs to this class for each fixed choice of its algorithm parameters. Let LA (n, C) denote the worst-case expected latency of A, and let KA (n, C) denote its worst-case expected collision cost, where the worst case is over adversaries satisfying our model and activating at most n packets. Packets need not all be activated before the first success. Define: MA (n, C) = max {LA (n, C), KA (n, C)} . An execution with no success has infinite latency. The lower bounds below use activation schedules fixed in advance, so they also apply against the adaptive adversaries allowed by our model. 5.1
Tradeoff: Latency & Expected Collision Cost
Lemma 16. For every age-based batch-fair algorithm A, every n ≥ 2, and every C, if LA (n, C) < ∞, then: LA (n, C)KA (n, C) ≥
C . 4
Proof. Consider this activation schedule: we activate two of the n packets in slot 1 and no others. Recall that L denotes the latency, with L = ∞ if no success occurs, and let X be the collision cost of the execution. For this activation schedule, we have E[L] ≤ LA (n, C) < ∞, where the finiteness ofLA (n, C) is an assumption in the lemma. Consequently, a success occurs with probability 1: otherwise, L = ∞ with positive probability, which would imply E[L] = ∞, contradicting the bound above. Let at = Pr(L ≥ t), which is the probability that the execution reaches slot t without a success in any earlier slot. Since both packets were activated in slot 1, conditioned on reaching slot t, each transmits independently with probability pt (C). Therefore: Pr(L = t) = at 2pt (C)(1 − pt (C)). Since a success occurs with probability 1, the events {L = t}, for t ≥ 1, account for all executions. Hence: X X X 1= Pr(L = t) = at 2pt (C)(1 − pt (C)) ≤ 2 at pt (C). (8) t≥1
t≥1
t≥1
We next express the expected latency and expected collision cost in terms of the probabilities at . First, since L is a positive integer-valued random variable, the tail-sum formula gives: X X E[L] = Pr(L ≥ t) = at . t≥1
t≥1
P Second, let Ct be the indicator that slot t is reached and contains a collision. Then X = C t≥1 Ct . Conditioned on reaching slot t, both packets transmit independently with probability pt (C), so the conditional probability of a collision is pt (C)2 . Therefore: Pr(Ct = 1) = Pr(L ≥ t) pt (C)2 = at pt (C)2 .
Dynamic Wakeup under Costly Collisions
21
Taking expectations and summing over the slots gives: X X E[X] = C E[Ct ] = C at pt (C)2 . t≥1
t≥1
2 Equivalently, we have E[X]/C = t≥1 P at pt (C) . If E[X] = ∞, then KA (n, C) = ∞ and the claim is immediate. Otherwise, Equation 8 gives 1/2 ≤ t≥1 at pt (C). Squaring both sides gives:
P
2 X 1 ≤ at pt (C) . 4 t≥1
Applying Cauchy–Schwarz [30] to the two sequences
√ √ at t≥1 and at pt (C) t≥1 gives:
2 1 X ≤ at pt (C) 4 t≥1
2 X√ √ = at ( at pt (C)) t≥1
X X ≤ at at pt (C)2 t≥1
=
t≥1
E[L]E[X] . C
Since LA (n, C) and KA (n, C) are the worst-case expected latency and expected collision cost, respectively, over all valid activation schedules, E[L] ≤ LA (n, C) and E[X] ≤ KA (n, C). Therefore: LA (n, C)KA (n, C) ≥ C/4, as claimed. √ Theorem 2. For every age-based batch-fair algorithm A, every n ≥ 2, and every C, MA (n, C) ≥ C/2. Proof. If MA (n, C) is not finite, the claim is trivially satisfied. Otherwise, the expected latency is finite, so Lemma 16 and the definition of MA give: C/4 ≤ LA (n, C)KA (n, C) ≤ MA (n, C)2 , and taking the square root on both sides yields the result. √ √ Comparison with Lowball. An O( C) worst-case expected collision-cost guarantee requires Ω( C) worst-case expected latency. When C ≥ K(lg1/ϵ n), Lemmas 12 and 15 give: √ KLowball (n, C) = O C , LLowball (n, C) = O C 1/2+ϵ ln C . Thus, in this regime, the maximum of Lowball’s two expectations is within a factor O(C ϵ ln C) of the best possible for this algorithm class. 5.2
The Classical Dynamic Lower Bound for Fixed Per-Collision Cost
The classical dynamic-wakeup lower bound requires some care in our setting. Theorem 6 of Jurdziński and Stachowiak [23] proves an Ω(n/ log n) bounded-error latency lower bound for dynamic wakeup when packets have no identifiers, have only local clocks, and do not know n. At first glance, this bound may appear
22
U. Biswas and M. Young
√ stronger than our Ω( C) lower bound and, in some parameter regimes, inconsistent with our upper bounds. For completeness, we record a direct adaptation of their construction to our age-based batch-fair algorithm class and make explicit how the resulting bound depends on the per-collision cost C. When C is fixed independently of n, this adaptation gives an Ω(n/ log n) expected-latency lower bound. However, the hidden constant and the required threshold on n may depend on the chosen value of C. This dependence matters because packets know C, so their transmission-probability schedules may change with it. Thus, when C is allowed to vary with n, the argument does not give an Ω(n/ log n) lower bound with a hidden constant independent of C. Consequently, it neither contradicts our large-C upper bounds nor yields √ an additional Ω(n/ log n) term that can be combined with our Ω( C) lower bound. Lemma 17. Fix an age-based batch-fair algorithm A and a per-collision cost C. There exist constants c0 > 0 and n0 , which may depend on A and C, such that for every n ≥ n0 : LA (n, C) ≥ c0
n . ln n
Proof. We adapt the batch-injection construction in the proof of Theorem 6 of Jurdziński and Stachowiak [23]. If pj (C) = 0 for every j, no packet ever transmits and latency is infinite. Otherwise, let j be the smallest index with pj (C) > 0, and write p = pj (C). Since the algorithm and C are fixed, j and p do not depend on n. For sufficiently large n, set: jnk 3 ln n , T = . r= p 2r Activate a batch of 2r packets in each of slots 1, . . . , T , with no further activations. This uses at most n packets. Partition each batch into two groups of r packets for the analysis. No success is possible before slot j, since no packet yet has positive sending probability. For each j ≤ t ≤ T , the batch activated in slot t − j + 1 has local age j. Conditioned on reaching slot t, its packets independently transmit with probability p. If each of its two groups contains a transmitter, then slot t has a collision, regardless of the other batches’ actions. Thus, for every history reaching slot t, its success probability is at most: 2 2(1 − p)r ≤ 2e−pr ≤ 3 . n Summing the probabilities of a first success in slots 1, . . . , T gives: 2T 2 ≤ 2. n3 n
Pr(L ≤ T ) ≤ On L > T , latency is at least T . Therefore:
LA (n, C) ≥ T
1−
2 n2
.
For sufficiently large n, we have r ≤ 4 ln n/p and n/(2r) ≥ 2, which imply T ≥ pn/(16 ln n). Hence: LA (n, C) ≥
pn . 32 ln n
This proves the lemma. In particular, the coefficient obtained by this construction depends on pj (C). Why holding C constant matters. The lemma first chooses a particular value of C and then takes n sufficiently large while keeping that value unchanged. It does not give a constant or a threshold on n that is independent of C. Our model supplies C to the packets, so the probability sequence can change when C changes, even though the packets do not know n. For Lowball, the first positive sending probability is p1 (C) = 1/w0 . The construction above therefore requires batches of Θ(w0 ln n) packets. In the large-C regime of Theorem 1 where, C ≥ K(lg1/ϵ n), our choice ϵ of K means C ϵ ≥ 2 lg n, and so w0 = 2C ≥ n2 . The construction above requires batches of Θ(w0 ln n) packets, which is more than the total population of n packets. Thus, the construction cannot be carried out in this regime.
Dynamic Wakeup under Costly Collisions
23
This does not contradict the lower bound established in Lemma 17. That lemma first chooses a value of C and then holds it constant as n grows. In that case, w0 is also constant, so for sufficiently large n there are enough packets to form batches of size Θ(w0 ln n), as required by the construction. However, as n grows while C remains constant, the condition C ≥ K(lg1/ϵ n) eventually fails. Thus, the fixed-C lower bound applies asymptotically outside the large-C regime in which we obtain our sharper upper bound. For a concrete example, take ϵ = 1/2 and C = K lg2 n, where K is the constant from our large-C case. Since 1/ϵ = 2, this places us exactly at the threshold in Theorem 1: C = K(lg1/ϵ n) = K lg2 n. The latency bound for this case is O(C 1/2+ϵ ln C) = O(C ln C). Substituting C = K lg2 n gives: O K(lg2 n) ln K lg2 n = O lg2 n(ln ln n) . The expected collision cost is even smaller: O
√ C = O(lg n).
Therefore: MLowball (n, C) = O (lg2 n) ln ln n , and we note that: (lg n)2 ln ln n = o
n log n
.
Thus, if the classical Ω(n/ log n) lower bound held with a constant independent of C even when C were allowed to grow with n, it would contradict this upper bound. The example therefore illustrates why that lower bound must be interpreted with C√held constant while n grows. Thus, √ the Ω(n/ log n) latency lower bound cannot be combined with our Ω( C) tradeoff to obtain a single Ω( C + n/ log n) lower bound with a hidden constant independent of C.
6
Conclusion and Future Work
We have addressed dynamic wakeup with a per-collision cost and no collision detection. Our results show that contention can be controlled even under arbitrary packet activations while keeping both latency and collision cost bounded. √ √ In the large-C regime, the O( C) expected collision-cost bound matches the scale of our Ω( C) tradeoff. For the maximum of expected latency and expected collision cost, our upper bound is within a factor O(C ϵ ln C) of this lower bound for the algorithm class we consider. It remains open whether this gap can be reduced or eliminated. It would also be interesting to extend the lower bound beyond age-based batch-fair algorithms. Acknowledgements/Generative AI Disclosure. The research problem, model, algorithmic design, and overall proof strategy presented here belong to the authors. That said, AI was very helpful in simplifying and tightening the analysis. We also used AI to polish the paper, although the presentation and high-level exposition are our own. We take full responsibility for any errors.
References 1. Anderton, W.C., Chakraborty, T., Young, M.: Windowed backoff algorithms for WiFi: Theory and performance under batched arrivals. Distributed Computing 34, 367–393 (2021) 2. Anderton, W.C., Young, M.: Is our model for contention resolution wrong?: Confronting the cost of collisions. In: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). pp. 183–194 (2017) 3. Banicescu, I., Chakraborty, T., Gilbert, S., Young, M.: A survey on adversarial contention resolution. ACM Computing Surveys (2024)
24
U. Biswas and M. Young
4. Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104–126 (1992) 5. Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, J., Young, M.: Fully energy-efficient randomized backoff: Slow feedback loops yield fast contention resolution. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). p. 231–242 (2024) 6. Bender, M.A., Fineman, J.T., Gilbert, S., Young, M.: Scaling exponential backoff: Constant throughput, polylogarithmic channel-access attempts, and robustness. Journal of the ACM 66(1), 6:1–6:33 (2019) 7. Bender, M.A., Kopelowitz, T., Kuszmaul, W., Pettie, S.: Contention resolution without collision detection. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). pp. 105–118 (2020) 8. Bender, M.A., Kopelowitz, T., Pettie, S., Young, M.: Contention resolution with constant throughput and loglogstar channel accesses. SIAM Journal on Computing 47(5), 1735–1754 (2018). https://doi.org/10.1137/ 17M1158604, https://doi.org/10.1137/17M1158604 9. Biswas, U., Chakraborty, T., Young, M.: Softening the impact of collisions in contention resolution. In: International Symposium on Stabilizing, Safety, and Security of Distributed Systems. pp. 398–416 (2024) 10. Biswas, U., Chakraborty, T., Young, M., Zhou, Q.M.: Softening the impact of collisions in contention resolution. Theoretical Computer Science p. 115907 (2026) 11. Biswas, U., Young, M.: Dynamic wakeup with collision costs. In: Doctoral Forum at the 56th Annual IEEE International Conference on Dependable Systems and Networks (DNS). pp. 230–232. IEEE (2026) 12. Biswas, U., Young, M.: A gentle wakeup call. In: Proceedings of the 5th International Workshop on Mobile Ubiquitous Systems, Infrastructures, Communications and AppLications (MUSICAL). pp. 96–101 (2026) 13. Chlebus, B.S.: Randomized communication in radio networks. Handbook of Randomized Computing 1, 401–456 (2001) 14. Chlebus, B.S., De Marco, G., Kowalski, D.R.: Scalable wake-up of multi-channel single-hop radio networks. Theoretical Computer Science 615(C), 23 – 44 (Feb 2016) 15. De Marco, G., Kowalski, D.R., Stachowiak, G.: Contention resolution without collision detection: Constant throughput and logarithmic energy. In: 36th International Symposium on Distributed Computing (DISC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022) 16. De Marco, G., Kowalski, D.R., Stachowiak, G.: Deterministic non-adaptive contention resolution on a shared channel. Journal of Computer and System Sciences 133, 1–22 (2023) 17. De Marco, G., Pellegrini, M., Sburlati, G.: Faster deterministic wakeup in multiple access channels. In: Italian Conference on Theoretical Computer Science. pp. 196–204. Springer (2005) 18. De Marco, G., Pellegrini, M., Sburlati, G.: Faster deterministic wakeup in multiple access channels. Discrete applied mathematics 155(8), 898–903 (2007) 19. De Marco, G., Stachowiak, G.: Asynchronous shared channel. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). pp. 391–400 (2017) 20. Gąsieniec, L., Pelc, A., Peleg, D.: The wakeup problem in synchronous broadcast systems. In: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing. pp. 113–121 (2000) 21. Jurdziński, T., Kowalski, D.R., Stachowiak, G.: Distributed deterministic broadcasting in wireless networks of weak devices. In: Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). pp. 632–644 (2013) 22. Jurdziński, T., Stachowiak, G.: Probabilistic algorithms for the wakeup problem in single-hop radio networks. In: Proceedings of the International Symposium on Algorithms and Computation. pp. 535–549 (2002) 23. Jurdziński, T., Stachowiak, G.: Probabilistic algorithms for the wake-up problem in single-hop radio networks. Theory of Computing Systems 38(3), 347–367 (2005) 24. Jurdziński, T., Stachowiak, G.: The cost of synchronizing multiple-access channels. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). pp. 421–430 (2015) 25. Kushilevitz, E., Mansour, Y.: An Ω(Dlog(N/D)) lower bound for broadcast in radio networks. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC). pp. 65–74 (1993) 26. Kushilevitz, E., Mansour, Y.: An Ω(Dlog(N/D)) lower bound for broadcast in radio networks. SIAM journal on Computing 27(3), 702–712 (1998) 27. Newport, C.: Radio network lower bounds made easy. In: Proceedings of the International Symposium on Distributed Computing (DISC). pp. 258–272 (2014) 28. Newport, C.: Radio network lower bounds made easy. In: Kuhn, F. (ed.) Distributed Computing. pp. 258–272 (2014) 29. Patra, R., Nedevschi, S., Surana, S., Sheth, A., Subramanian, L., Brewer, E.: WiLDNet: Design and implementation of high performance WiFi based long distance networks. In: Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI). pp. 87–100. USENIX Association (2007) 30. Steele, J.M.: The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities. Cambridge University Press (2004)
Dynamic Wakeup under Costly Collisions
25
31. Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM Journal on Computing 15(2), 468–477 (May 1986) 32. Yu, D., Hua, Q.S., Dai, W., Wang, Y., Lau, F.C.: Dynamic contention resolution in multiple-access channels. In: International Conference on Wired/Wireless Internet Communications. pp. 232–243. Springer (2012) 33. Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Communications Surveys & Tutorials 8(1), 24–37 (2006)