Contention Resolution with a Fast-but-Fickle Channel

Contention Resolution with a Fast-but-Fickle Channel Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young

arXiv:2611.12843v1 [cs.DC] 9 Nov 2026

Mississippi State University Mississippi State, Mississippi, USA ucb5@msstate.edu, vchaudhary@cse.msstate.edu sh2924@msstate.edu, myoung@cse.msstate.edu

Abstract The contention-resolution problem studies how n devices share a communication channel without centralized coordination. Classical models typically assume a single continuously available channel and focus on minimizing total completion time. However, modern wireless systems increasingly rely on shared spectrum, where access may be abruptly revoked by incumbent users. Motivated by this setting, we study contention resolution with two channels: a reliable slow channel and a faster channel that can be intermittently disabled by unpredictable eviction periods. Moving a batch of packets from the slow channel to the fast channel incurs a unit cost, while evictions from the fast channel impose a larger per-packet penalty. Our goal is to achieve asymptotically optimal latency while minimizing switching overhead relative to an optimal offline algorithm that knows the eviction schedule. We present Randomized Adaptive Channel Exploitation (RACE), a randomized algorithm that exploits the fast channel when available while maintaining progress  √ on the slow channel during disruptions. When the fast channel has rate ρ ∈ Ω(log n), O( n) and a sufficiently large constant-factor resource augmentation, RACE achieves an O(1) competitive ratio for expected latency. RACE’s expected switching-cost competitive ratio relative to p any optimal-latency offline algorithm OPT is O(ρ + n/m), where m ≥ 1 is the number of fast-channel availability intervals√used by OPT. We also prove a worst-case Ω( n) switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate Ω(ρ) switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

Keywords: Contention resolution, online algorithms, multiple access channel, resource augmentation, distributed algorithms.

1

Introduction

Dynamic spectrum sharing offers a way to increase wireless capacity. Rather than assigning spectrum exclusively, underutilized government-licensed spectrum can be shared with commercial and industrial users [17, 50, 20]. These secondary users may access spectrum opportunistically, but must avoid interference with incumbents, who have priority access rights. For example, the U.S. Citizens Broadband Radio Service (CBRS) framework allows secondary access while protecting incumbents [35]. Current Spectrum Access System (SAS) deployments are centralized, though decentralized architectures have been proposed to improve scalability and robustness [53]. A central algorithmic difficulty is that secondary access can be revoked. When an incumbent becomes active, secondary users may be forced to vacate the high-capacity spectrum; that is, they are evicted from the fast channel. Such evictions can be difficult to detect, predict, or coordinate around [41, 22]. Thus, dynamic spectrum sharing provides high throughput but unpredictable availability. 1

Here, we address contention resolution in this setting. Contention resolution asks how packets, or the devices sending them, share a communication channel without centralized scheduling (see surveys [9, 25]). A packet succeeds only when it transmits alone in a slot; if multiple packets transmit, a collision occurs and none succeeds. Classical models typically assume one continuously available channel, and the primary goal is to minimize latency, the time until all packets have successfully transmitted. Dynamic spectrum sharing changes this picture. A secondary system may have access to a “fast-but-fickle” channel with high capacity, together with a slower fallback channel that remains continuously available. Algorithms must decide not only when packets transmit but also when they move between channels. These transitions incur overhead from re-association, reconfiguration, and service disruption. Excessive switching is therefore costly even when latency is low. The challenge is to exploit the fast channel when available, tolerate evictions, and avoid unnecessary switching. Our work extends classical contention resolution to a two-channel model with a reliable slow channel and a faster channel subject to unpredictable evictions. We ask whether decentralized algorithms can achieve near-optimal latency while controlling the switching costs of moving packets between channels. Our Problem Statement. Initially, n packets share a reliable slow channel, each requiring one collision-free transmission to succeed. Packets may also use a faster channel subject to unpredictable evictions. We compare against an optimal offline algorithm, OPT, that knows the eviction schedule and can schedule packet transmissions without collisions to minimize latency. Our goal is to design an online, decentralized algorithm whose expected latency is within a constant factor of OPT’s while achieving a low switching-cost competitive ratio relative to OPT.

1.1

Model

There are n ≥ 2 devices, each initially holding one packet. The population is the number of packets not yet successfully transmitted; initially, it is n. Packets are anonymous and must transmit without centralized coordination. There are no later arrivals, and the algorithm does not initially know n. We describe actions as taken by packets rather than devices. Communication Channels. Packets communicate over two multiple-access channels: the slow channel and the fast channel. Time is divided into slots. On the slow channel, each packet may perform at most one action—either transmit or listen—per slot. On the fast channel, each slot consists of ρ mini-slots, where ρ ≥ 2 is an integer, and a packet attached to the fast channel may transmit or listen in each mini-slot. Unless otherwise specified, “slot” refers to a slow-channel slot. Each packet is attached to exactly one channel at a time, and all packets are initially attached to the slow channel. A packet may voluntarily switch from the slow channel to the fast channel only at a slow-slot boundary. In contrast, a packet may switch from the fast channel to the slow channel at any time, either voluntarily or as a result of an eviction. In either case, the packet becomes attached to the slow channel immediately but cannot act there until the next permitted slow-slot boundary. In a slot, or in a fast mini-slot, no transmission produces an empty outcome; exactly one produces a success; and two or more produce a collision, in which no transmission succeeds. Every packet participating on the relevant channel receives ternary feedback indicating which of these three possible outcomes actually occurred. A transmitting packet immediately learns whether it succeeded and immediately terminates. A packet is active until it succeeds, and ncur denotes the current active population. Measurement and reporting transmissions also carry data: their successful senders terminate. Evictions. As the online component of the model, the fast channel is subject to eviction periods, during which packets cannot access it. An eviction period may begin at time zero and 2

may last indefinitely. All packets on the fast channel when such a period begins are evicted. At slot boundaries, packets on the slow channel can observe whether the fast channel is currently available. This observation requires no slow-channel action and reveals only whether the fast channel is available at that boundary. The eviction schedule is fixed independently of the algorithm’s random choices. Eviction periods may begin and end at arbitrary fast mini-slot boundaries; if an eviction begins exactly when a transmission ends, that transmission is completed before the eviction takes effect. An iteration is a maximal interval of fast-channel availability. Every iteration that occurs contains at least Cavail full slow slots, for a sufficiently large fixed constant specified in Section A.1. We impose this restriction because very brief periods of fast-channel availability would offer little opportunity for meaningful performance gains, and rapid alternation between availability and eviction seems unlikely in practice. However, an eviction period may last indefinitely, so the fast channel is not guaranteed to become available again. Metrics. We consider two cost measures: • Latency: The number of slots until all packets succeed, rounded up to a slow-slot boundary. • Switching cost: A batch of packets attempting to move from slow to fast incurs unit cost, even if the fast channel is unavailable. Moving k packets from fast to slow costs k, whether voluntarily or by eviction. Latency is the traditional performance measure for contention resolution [9, 25]. Switching cost captures a separate concern: the overhead of changing channel assignments. Motivated by coordinated or group association in wireless systems [49, 21, 8], our asymmetric model charges unit cost to move a batch onto the fast channel. Returning packets to the slow channel incurs a per-packet cost, reflecting the greater disruption and reconfiguration overhead of reassignment; for voluntary returns, this cost also captures the foregone opportunity to complete those packets’ transmissions on the fast channel. We compare our algorithm to an optimal offline algorithm, OPT, that knows the eviction schedule and schedules transmissions perfectly, without empty slots or collisions when usable service and pending packets are available. Let L(A, I) and Cost(A, I) denote latency and switching cost on instance I; expectations are written explicitly for randomized algorithms. The minimum achievable latency under the same attachment and boundary rules is L(OPT, I). Fix a schedule attaining it, and let m be the number of iterations in which that schedule successfully transmits on the fast channel. Our upper bound holds for every such choice; the multiplicative switching comparison is asserted for m ≥ 1. For the lower-bound denominator, we may choose a minimum-switching schedule among the minimum-latency schedules. In the spirit of resource augmentation [51], we assume our algorithm has λ = O(1) logical subchannels on the physical fast channel, for a sufficiently large fixed λ. Each is a noninterfering transmission resource providing one opportunity per mini-slot, with its own collisions and feedback. Thus our algorithm has aggregate capacity λρ opportunities per slow slot, compared with ρ for OPT. An eviction affects all subchannels. There is no slow-channel augmentation: both algorithms have one slow opportunity per slot.

1.2

Main Results

√ Our results apply when ρ = Ω(log n) and ρ = O( n), where the constant implicit in the lower bound is sufficiently large. Our decentralized algorithm Randomized Adaptive Channel Exploitation (RACE) achieves the following guarantee. Theorem 1. On every fixed instance I, RACE guarantees E[L(RACE, I)] = O(1). L(OPT, I) 3

Moreover, if OPT uses m ≥ 1 fast-channel iterations, then E[Cost(RACE, I)] =O ρ+ Cost(OPT, I) 

r

n . m 

The latency bound also applies when m = 0, and in this case, RACE incurs zero switching cost with high probability and O(1) expected switching cost. The switching-cost bound improves when OPT uses more fast-channel iterations. For example, when ρ = Θ(log n) and m = Θ(n/poly(log n)), the ratio is O(poly(log n)). Our upper bound is complemented by lower bounds: Theorem 2. Let A be any randomized online algorithm that is constant-competitive in expected latency. Then: (A) There is a fixed eviction schedule on which A incurs expected switching-cost competitive √ ratio Ω( n). (B) There is a fixed schedule in which a single eviction permanently disables the fast channel and A incurs expected switching-cost competitive ratio Ω(ρ). The first construction shows that our switching-cost competitive ratio is asymptotically tight √ when OPT uses a constant number of fast-channel iterations: our upper bound becomes O( n), √ matching the Ω( n) lower bound. The second shows that even a single eviction can force an Ω(ρ) switching-cost competitive ratio: exploiting the fast channel requires exposing sufficiently many packets to eviction, while OPT can avoid this cost by knowing the eviction time.

2

Related Work

We review related work on dynamic spectrum sharing, contention resolution, online scheduling, and resource augmentation. Dynamic Spectrum Sharing. Bhattarai et al. [17] survey tiered-access architectures and database-driven coordination frameworks such as Spectrum Access Systems (SAS), which enable coexistence between incumbents and secondary users. AWS-3 and CBRS illustrate this approach [41]. Reliable incumbent detection using sensing and learning has also been studied [22], along with the regulatory and economic mechanisms underlying dynamic access [50, 20]. This literature largely emphasizes systems, experiments, regulation, and optimization. We complement it with a formal contention-resolution model and upper and lower bounds under unpredictable evictions. Static Contention Resolution. Classical contention resolution often studies the static or batched-arrival setting, in which all n packets are initially present. The standard objective is makespan, the time until all packets succeed. Randomized and deterministic protocols have bounds ranging from O(n log n) for classical backoff approaches to optimal O(n) makespan in suitable models [12, 38, 39, 44, 45]. Extensions consider adversarial arrivals [19, 27, 26, 3, 2], energy efficiency [43, 16], multiple slow channels [28], and robustness to jamming [15, 7, 48, 24, 5, 4, 14, 13]. These models generally assume fixed communication resources, even under jamming. We instead study fast-channel availability interrupted by incumbent evictions, with switching cost as a second objective. Scheduling, Reallocation, and Shared Channels. Our model is also related to online scheduling, where packets correspond to jobs and channels to machines. A close classical analogue is scheduling on heterogeneous machines, including uniform or related machines with different speeds [52, 46, 32]. Related directions include semi-online models with partial information [31, 29, 54] and job rejection, migration, or reassignment [33, 30, 47]. 4

Several scheduling problems involve channels more explicitly: contention resolution with deadlines [1], window scheduling and station assignment [10, 11, 40], dynamic client reallocation across channels [23, 34], and fault-tolerant packet scheduling [42, 6, 18, 36]. Related work also studies distributed scheduling in message-passing models [37]. Our setting differs because packets contend through randomized transmissions on shared multiple-access channels rather than being assigned to machines or scheduled centrally on links. Fast-channel evictions also require controlling switching costs between the fast channel and a reliable slow channel.

3

Algorithm Specification

We describe Randomized Adaptive Channel Exploitation (RACE) and the intuition behind its design.

3.1

Preliminaries

We use separate procedures for population estimation, contention resolution, and channel selection. Number of active packet estimates. RACE calls a decentralized subroutine Estimate when b of n; all surviving packets are on the slow channel. Its initial call returns a common estimate n b cur of the active population, ncur . With high probability, later calls return a common estimate n b = O(log2 n b) both are within a constant factor of the population. Each later call takes τest (n) slots. Population-size approximation is standard [43]; Appendix C specifies the guarantees used by RACE. TSTB contention primitive. RACE uses Truncated Sawtooth-Backoff (TSTB) as its contention-resolution subroutine [16]. A fresh execution with size parameter z follows a predetermined sequence of contention windows. In each window, every remaining participant chooses one transmission opportunity uniformly and independently. Successful packets leave. The prescribed completion window contains L(z) = O(z) opportunities, including 2z in the first window, so its duration at rate ν ∈ {1, ρ} is Tν (z) = Θ(z/ν) when z ≥ ν. We rely on the following properties of TSTB. For a population within a fixed constant factor of an appropriate size parameter, a constant fraction succeeds except with probability exp(−Ω(z)). If at most z packets participate in a fresh execution with size parameter z, all succeed except with probability O(z −d ), for a fixed d ≥ 2. Executions can be paused by stopping their common logical clock; permanent departures do not delay the remaining packets under the fixed schedule. Further details of the execution and its analysis appear in Appendix A.1.

3.2

Algorithm Specification and Intuition

RACE seeks constant-competitive latency while limiting switching cost. The slow channel provides progress during evictions; gradually increasing fast batches exploit availability without exposing too many packets to eviction. Shared State and Specification. Figure 1 gives the pseudocode, and Figure 2 provides a high-level illustration for RACE. All surviving packets maintain the same fast-batch index b, b cur , and completed-work counter W . Following the initial call current population estimate n b cur = n b and b = W = 0. to Estimate (lines 1–2), n The counter W tracks progress since the most recent estimate and determines when to update it. It is not an exact count of successful packets: slow-channel TSTB successes are counted directly, while progress on the fast channel is credited using intended batch sizes, as specified b cur . below. A sufficiently small fixed constant δ > 0 sets the update threshold W ≥ δ n 5

Run the initial Estimate call to obtain n b; set n bcur ← n b, b ← 0, and τpop , τtime as in Equation (1); Begin an estimation epoch: set W ← 0 and initialize a paused slow TSTB instance with parameter s ← 2b ncur ; 3 while this packet remains active do 4 if t ≥ τtime then 5 Enter permanent slow-channel cleanup with guess n b; 6 else if n bcur ≤ max{τpop , 2λρ} then 7 Enter permanent slow-channel cleanup with guess n bcur ; 8 else if W ≥ δb ncur then 9 Run Estimate with bound n b, checking τtime at every slow boundary; 10 If the call finishes first, update n bcur and begin a new estimation epoch, retaining b; 11 else if fast availability is observed then 12 Set x ← min{ρ + b, ⌊b ncur /λ⌋}; choose a fast subchannel or remain on the slow channel using the Subchannel Assignment rule (described below); Execute TSTB on each fast subchannel for D(x) slots; any packets evicted before the end 13 that have not succeeded return to the slow channel and wait; 14 Return survivors at the deadline; use one settling slot and one reporting slot; 15 if the report is nonempty then 16 Set b ← 0; 17 else 18 Set b ← b + 1 and W ← W + λx; 19 else 20 Execute the next slot of the slow-channel TSTB execution; if a packet succeeds, set W ← W + 1; 21 If its completion window ends, start a fresh instance with parameter 2b ncur , retaining W ; 1 2

Figure 1: Randomized Adaptive Channel Exploitation (RACE) RACE uses two fixed cutoffs to determine when it enters permanent slow-channel cleanup, a final stage in which it no longer admits fast batches: b /ρ⌉ , τpop = ⌈cpop n

b /64⌋}. τtime = max{1, ⌊n

(1)

The population cutoff τpop causes RACE to stop using the fast channel once its estimate of the remaining population is sufficiently small. The test in lines 6–7 also includes the safeguard 2λρ, b cur ≤ max{τpop , 2λρ}. The time cutoff τtime stops new fast-channel so cleanup begins when n admissions once that many slow slots have elapsed, regardless of the remaining population (lines 4–5). Time is measured from the beginning of execution, including the initial estimation call. A fast round already underway finishes before cleanup begins. With high probability, b ≤ 32n, so τpop = Θ(n/ρ) and n/128 ≤ τtime ≤ n/2 for sufficiently large n. The constant n≤n cpop is chosen sufficiently large relative to the augmentation and estimation constants. How Cleanup Works. During cleanup, all remaining packets run TSTB on the slow channel, doubling the size parameter after each unsuccessful execution until all packets succeed. The b cur for the population cutoff and n b for the time cutoff, with a fixed initial parameter is based on n minimum if the estimate is too small. Appendix A.1 specifies the procedure; Lemma 10 bounds its expected completion time. After each population estimate, RACE resets W = 0 and initializes a slow-channel TSTB b cur (line 2, and lines 8–10 for later estimates). An estimation execution with parameter 2n epoch begins when a population estimate is obtained and ends when the next call to Estimate begins or permanent slow-channel cleanup starts. Updating the estimate does not reset b. When the fast channel is available, RACE admits one batch of packets (lines 11–18). It partitions this batch among the λ logical subchannels, with an intended number of x packets per subchannel, where: b cur /λ⌋}. x = min{ρ + b, ⌊n 6

Figure 2: High-level illustration of RACE. On the fast channel, each box represents ρ minislots. Teal boxes, on the fast-channel and slow channel, indicate activity, which may include successful transmissions, collisions, and empty mini-slots. Gray boxes represent idle slots, dark-red boxes represent fast-channel eviction periods, and blue boxes represent executions of Estimate, each spanning multiple slow-channel slots. Upward arrows indicate batches moving onto the fast channel, while downward arrows indicate packets returning to the slow channel b , and subsequent estimates are denoted by after eviction. The initial population estimate is n b cur ; each becomes available when its estimation finishes. An iteration is a maximal interval of n fast-channel availability. Each fast round includes TSTB execution, a settling slot (Si ), and a reporting slot (Ri ). An estimation epoch begins when a population estimate is obtained and ends when the next estimation begins or permanent slow-channel cleanup starts. The slow-channel TSTB execution is paused during fast rounds and resumes afterward. Once a cutoff is reached, RACE finishes the remaining packets on the slow channel. The intended total batch size is λx; although, since packets independently choose whether to join and which subchannel to use, the actual number selected may differ. Each subgroup executes a fresh TSTB instance with parameter 2x at rate ρ. All surviving packets use the same scheduled duration: D(x) = ⌈L(2x)/ρ⌉ = Θ(x/ρ). We call the operation of admitting and processing this batch, followed by two slots to check for an eviction, a fast round, or simply a round. Even if every selected packet succeeds early, RACE waits until the D(x) slots have elapsed. Any packets still on the fast channel then return to the slow channel. During the first of the two additional slow slots, no packet transmits. During the second, packets that were evicted before the scheduled end and have not yet succeeded transmit to report the eviction (lines 13–18). If that slot is nonempty, whether a success or a collision, makes the round aborted: RACE resets b = 0 and leaves W unchanged, although some fast transmissions may have succeeded. Otherwise the round is certified: RACE increments b and adds λx to W . Thus, apart from the cap in the definition of x, the intended number of packets per subchannel rises from ρ to ρ + 1, ρ + 2, and so on, until a reported abort resets it to ρ. RACE admits no new batch until the round is over. When the fast channel is unavailable, RACE runs the next slot of slow-channel TSTB (lines 19–21), adding one to W for each success. This execution pauses during fast rounds and resumes afterward. If it reaches the end of its prescribed windows while packets remain, a new b cur , retaining W . The algorithm checks its conditions again execution begins with parameter 2n at the next slow-slot boundary. At each slow-slot boundary or after a fast round, RACE checks the cutoffs, then the estimation b cur , it runs Estimate on the slow channel. If estimation threshold (lines 4–10). When W ≥ δ n 7

Figure 3: Illustrating the need for fast-channel augmentation. During an initial Θ(n/ρ)-slot interval, OPT can complete all n packets on the fast channel, while an unaugmented algorithm, ALG, may complete only a constant fraction. If the fast channel then becomes permanently unavailable, ALG requires Ω(n) additional slots to finish on the slow channel. finishes, it resets W = 0 and begins a new estimation epoch without resetting b. Fast-channel availability does not interrupt estimation, but reaching the time cutoff sends the algorithm to cleanup. Role of the Two Cutoffs. The cutoffs preserve constant-competitive latency while ensuring that RACE stops admitting fast batches by the time OPT finishes, with high probability. The population cutoff triggers cleanup when only O(n/ρ) packets remain; these can finish on the slow channel in expected O(n/ρ) time. The time cutoff handles later completion by OPT: when OPT needs Ω(n) slots, slow-channel cleanup from any remaining population is affordable. If OPT finishes earlier, our analysis shows that augmented fast-channel capacity forces RACE to reach the population cutoff in time. Thus neither case requires additional fast admissions after OPT finishes. Subchannel Assignment. In each fast round, every active packet independently chooses b cur for each j ∈ {1, . . . , λ}, or remains on the slow channel subchannel j with probability x/n otherwise. This determines both batch membership and subchannel assignment; the numbers selected need not be equal. All selected packets enter as one batch and use only their assigned subchannel. Packets remaining on the slow channel pause TSTB until the round ends, and unsuccessful packets returning from the fast channel resume their previous slow-channel execution. Motivation for Gradually Increasing Batch Sizes. Each fast batch costs one admission, while an eviction can return many unfinished packets. Small batches limit eviction cost but increase admissions; large batches do the reverse. RACE raises the intended size per subchannel by one after a certified round and resets it to ρ after an abort. Reaching size x > 2ρ requires certifying sizes ρ, ρ + 1, . . . , x − 1, which complete Ω(x2 ) packets with high probability. The next eviction exposes only O(x) packets per subchannel. Thus, larger risks follow substantial progress. Resource Augmentation. OPT knows future evictions and schedules without collisions. The extra fast-channel capacity of RACE compensates for these advantages. A wireless interpretation 8

is additional bandwidth divided into the logical subchannels described in Section 1.1. Figure 3 shows the difficulty without augmentation: in an initial interval of n/ρ slots, OPT can finish all packets, while an unaugmented contention-resolution algorithm may leave Θ(n) unfinished. If the fast channel then becomes unavailable indefinitely, slow-channel completion takes Ω(n) further slots, a factor of Θ(ρ) more than OPT. Sufficient constant-factor augmentation on the fast channel prevents this loss. The slow channel guarantees eventual delivery, but need not match OPT’s throughput at every moment. The time cutoff limits fast admissions and the population cutoff makes earlier slow-channel cleanup affordable. Together they remove the need for slow-channel augmentation.

4

Technical Overview

We outline the main technical challenges; full proofs appear in the appendix. Latency and switching cost pull in opposite directions: RACE must exploit fast-channel availability without knowing the next eviction, but larger batches expose more packets to costly returns. Gradually increasing batch sizes balance these demands. The analysis must also maintain accurate population estimates and prove that fast admissions stop by the time OPT finishes. Otherwise, later fast-channel availability could lead to further switching costs even after OPT has finished. Throughout this overview, let G denote the good event that the initial and subsequent population estimates satisfy their guarantees and that the packet-assignment and progress guarantees of Lemma 2 hold whenever its assumptions are met. Lemma 7 gives probability 1 − O(n−D ) for any desired fixed D, by choosing constants appropriately. Cleanup and cutoff safeguards separately control the contribution of the complementary event. Batch-Level Estimates. Each fast subchannel has intended batch size x; a packet joins it b cur . When this estimate is within a constant factor of ncur , the expected with probability x/n subgroup size is Θ(x). Since x ≥ ρ = Ω(log n), Chernoff bounds give Θ(x) participants except with probability exp(−Ω(x)). Fresh TSTB then yields Ω(x) successes with the same exponential failure bound. Lemma 2 establishes this simultaneously across subchannels: every certified round of target x completes at least αλx packets on G, for a constant α > 0 independent of λ. When a fast-channel batch completes its scheduled TSTB execution without interruption, the expected number of unsuccessful packets returning to the slow channel is O(1) per subchannel, by the TSTB guarantee and the concentration bound on subgroup sizes. Lemma 1 therefore establishes an expected return cost of O(λ) = O(1) for the entire batch. Tracking Progress Across Channels. The analysis of the counter W requires two properties: (i) the population estimate must remain accurate until W triggers an update, and (ii) each update must correspond to a substantial decrease in the active number of packets. The counter can differ from the actual progress in either direction: a certified round credits λx even if fewer packets succeed, while an aborted round may complete packets without increasing W . Maintaining Estimate Accuracy. The main challenge is that aborted rounds may have completed many packets without increasing W . We charge those possible departures to preceding certified work. An aborted round with intended size ρ + t, t ≥ 1, follows certified rounds of intended sizes ρ, . . . , ρ + t − 1 since the last reset of b. Since: ρ+t≤2

t−1 X

(ρ + i),

i=0

the number of packets that could have succeeded during the aborted round is at most a constant multiple of the total intended size of the preceding certified batches. A complication arises when a round with x = ρ is aborted, since there may be no preceding certified rounds to account for it. However, the minimum-availability condition (recall Cavail from Section 1.1) prevents two such rounds from both being aborted without an intervening 9

certified round or population estimate. Moreover, an aborted round with x = ρ that follows an aborted round with x > ρ can be charged to the earlier abort. Lemma 4 shows that the sum of x over aborted rounds is at most a constant multiple of the sum of x over certified rounds, with an additional O(ρ) for initialization and each population estimate. For a prefix of estimation epoch j, let Cs count slow-channel TSTB successes, and let Vj and Ij be the sums of the intended batch sizes x on the fast channel over certified and aborted rounds, respectively. Then W = Cs + λVj . On G, every intended per-subchannel batch size is at most:   q √ F = O ρ + n/λ = O( n). Within the epoch, Lemma 4 gives Ij ≤ 4Vj + 4F . The additive term accounts for an aborted round whose preceding certified rounds may belong to an earlier estimation epoch. On event G, each fast round contains at most 2λx packets, regardless of whether it is certified or aborted. Using Lemma 4, we can therefore bound the number of packets that have succeeded since the last population estimate by: Cs + 2λ(Vj + Ij ) + 2λF ≤ 10W + 10λF. b cur,j denote the estimate at the beginning of estimation epoch j, and let Nj be the actual Let n number of active packets at that time. The bound above, together with the rule for updating W , shows that sufficiently small δ and sufficiently large cpop ensure that only a small fraction of these packets can succeed before the next estimate is obtained. Consequently, the estimate remains within a constant factor of the actual number of active packets throughout the epoch, as established in Lemma 5. b cur,j , RACE specifies that a new population Ensuring Substantial Progress. When W reaches δ n estimate is performed. Every slow-channel TSTB success contributes one to W , while each certified fast round completes at least an α fraction of the number credited to W . Consequently, the number of packets that have succeeded since the beginning of the epoch is at least αW ≥ αδNj . Hence, if another estimation epoch follows, the number of active packets satisfies Nj+1 ≤ (1 − αδ)Nj . Since αδ > 0 is a constant, the number of active packets decreases by a constant factor between successive epochs, so RACE invokes the estimator only O(log n) times. Moreover, because each estimate is within a constant factor of the actual number of active packets, the sum of these estimates over all epochs is O(n).

Progress on the Fast-Channel. On event G, RACE invokes Estimate at most O(log n) times, and each invocation takes O(log2 n) slots. Including the initial estimate, the total time spent estimating is therefore O(log3 n). During these slots, RACE does not use the fast channel, even if it is available. Since OPT can transmit at most ρ packets per slot on the fast channel, RACE misses at most O(ρ log3 n) = o(n) fast-channel transmission opportunities due to estimation. Thus, the total loss from estimation is small, even if some fast-channel availability intervals are spent entirely on estimating the number of active packets. Let Servicef ([0, t)) denote the total number of fast-channel mini-slots during which the fast channel is available before time t. Since OPT can transmit at most one packet per mini-slot on the fast channel and one packet per slow-channel slot, the total number of packets OPT can complete by time t is at most: Service([0, t)) = t + Servicef ([0, t)). This bound may count some fast-channel mini-slots that OPT cannot use because packets can switch channels only at slow-slot boundaries, but this only makes the upper bound larger. Lemma 8 shows that, while RACE has not completed or entered cleanup and t < τtime , we have: √ Service([0, t)) ≤ t + O(n/λ) + O(ρ log3 n + n). (2) 10

This holds on event G, where the constant implicit in O(n/λ) is independent of λ. We establish this bound by accounting for three situations in which the fast channel may be available to OPT: while RACE executes fast rounds, while RACE estimates the number of active packets, and when the fast channel becomes available partway through a slow-channel slot. During fast rounds. To bound the number of fast-channel transmission opportunities available to OPT during RACE’s fast rounds, we first bound the sum of the intended per-subchannel batch sizes x over those rounds. Let V and I be the sums of the intended per-subchannel batch sizes x over certified and aborted rounds, respectively, completed by time t. Since certified rounds n complete at least αλV packets on event G, we have V ≤ αλ . Let h be the number of population estimates initiated by time t. Lemma 4 establishes that I ≤ 4V + ρ(h + 1). Accounting also for a round that may still be in progress at time t, whose intended per-subchannel batch size is at most F , we obtain: X

x

≤V +I +F ≤

rounds started by t

5n + ρ(h + 1) + F. αλ

Recall from specification of RACE (Section 3.2) that each fast round lasts D(x) + 2 = O(x/ρ) slow slots, including the two additional slots used to determine whether an eviction occurred. During this time, OPT has at most O(x) fast-channel transmission opportunities. Thus, the bound on the sum of x above shows that the total number of such opportunities during RACE’s fast rounds is at most: O(n/λ) + O(ρh + F ). The factor 1/λ arises because RACE makes progress on λ logical subchannels simultaneously, whereas OPT has only one fast channel. During population estimation. As established above, RACE spends a total of O(log3 n) slots estimating the number of active packets, including the initial estimate. RACE does not use the fast channel during these slots, even if it is available. Consequently, OPT has at most O(ρ log3 n) fast-channel transmission opportunities during these periods. When the fast channel becomes available during a slow-channel slot. RACE checks whether the fast channel is available only at slow-slot boundaries. If the channel becomes available partway through a slot, RACE may therefore miss up to ρ fast-channel transmission opportunities before it can respond. The minimum-availability condition ensures that the fast channel remains available at the next boundary, when RACE begins either a fast round or a population estimate. We can account for at most one such delay before each of these operations. For fast rounds, this additional cost is absorbed into the bound above because x ≥ ρ. The delays preceding population estimates contribute at most O(ρ(h + 1)) additional opportunities. √ Combining these three bounds, using h = O(log n) and F = O( n), gives the fast-channel contribution in Equation 2. Why RACE stops using the fast channel when OPT finishes early. Finally, OPT can complete at most t packets on the slow channel by time t, regardless of RACE’s progress on that channel. Our analysis does not require RACE to match OPT’s slow-channel throughput. By choosing the fast-channel augmentation factor λ sufficiently large, the O(n/λ) term can be made at most √ n/8. Since ρ = O( n), the remaining lower-order terms contribute at most another n/8 for sufficiently large n. Consequently, as long as RACE has not completed or entered cleanup and t < τtime , we have: Service([0, t)) ≤ t + n/4. Combining the Bounds. We now use the bound on OPT’s available service to establish our latency guarantee and show that RACE stops admitting new fast batches by the time OPT finishes. Let T ∗ = L(OPT, I) denote OPT’s completion time. We consider two cases, depending 11

on whether OPT finishes before or after RACE’s time cutoff. RACE itself does not need to distinguish between these cases. Case 1: OPT finishes before the time cutoff. Suppose T ∗ < τtime ≤ n/2. Since OPT completes all n packets by time T ∗ , we must have n ≤ Service([0, T ∗ )). However, if RACE had neither completed nor entered cleanup by T ∗ , the preceding bound would imply: n ≤ Service([0, T ∗ )) ≤ T ∗ + n/4 < n, which is a contradiction. Therefore, RACE must have completed or entered permanent slowchannel cleanup by the time OPT finishes. Since the time cutoff has not been reached, this cleanup is triggered by the population cutoff, leaving only O(n/ρ) packets to finish. Their expected completion time is O(n/ρ) = O(T ∗ ). Moreover, RACE admits no further fast batches after OPT finishes, even if the fast channel subsequently becomes available. Case 2: OPT finishes at or after the time cutoff. If T ∗ ≥ τtime , then T ∗ ≥ n/128 = Ω(n) on the initialization good event. The time cutoff prevents further fast admissions, and even slow-only cleanup from all n packets costs expected O(n) = O(T ∗ ). A round already admitted before τtime finishes normally and adds at most O(n) time; its return cost is charged below. Thus this case requires no slow-channel progress advantage. This explains why a larger fixed population threshold is not an interchangeable substitute for τtime . Cleaning up Θ(n) packets could be too slow when OPT finishes in Θ(n/ρ) time, whereas it is affordable in the second case. The population cutoff handles the first case, and the time cutoff handles the second. Lemma 9 formalizes the absence of new fast admissions after OPT, and Proposition 1 establishes expected constant-competitive latency, including exceptional estimates. Switching Cost. For the switching-cost comparison, assume m ≥ 1. Let J be the number of reported aborts, and let t1 , . . . , tJ+1 count the certified rounds before the first abort, between successive aborts, and after the last abort. Each abort resets b, whereas a new population estimate does not. Thus, the certified rounds counted by ti have intended per-subchannel batch sizes ρ, ρ + 1, . . . , ρ + ti − 1. On event G, each certified round with intended size x completes at least αλx packets. Since each packet succeeds only once, we have: X αλ J+1 t2 ≤ n. 2 i=1 i

On event G, RACE begins no new fast rounds after OPT finishes. Each reported abort results from an eviction, so two aborted rounds cannot have begun during the same period of fast-channel availability. Lemma 12 bounds the number of such periods before OPT finishes by m + 2. Hence J ≤ m + 2, and Cauchy–Schwarz gives: J+1 X

v u J+1 u X √ t ≤ t(J + 1) t2 = O( mn).

i=1

i=1

i

i

There are at most i ti + J + 1 fast rounds, each incurring one batch-admission cost. An aborted round following ti certified rounds has intended per-subchannel size ρ + ti and, on G, can return at most 2λ(ρ + ti ) packets through eviction. Thus, the total cost of admissions and returns caused by evictions is: P

O (J + 1)ρ +

J+1 X

!

ti

= O(mρ +

√ mn),

i=1

as established in Lemma 13. We must also account for packets that return to the slow channel because they have not succeeded by the scheduled end of a fast round. Lemma 1 shows that the expected number of 12

such packets is O(λ) = O(1) per round, provided the estimate of the number of active packets is √ sufficiently accurate. Since RACE begins at most O(mρ + mn) rounds on event G, Lemma 14 √ shows that these returns contribute at most O(mρ + mn) to the expected switching cost. This includes packets returning after OPT finishes, provided their fast round began before OPT’s completion. The contribution from executions outside event G is negligible, as established using the time cutoff and the guarantees of Estimate. Combining all switching costs gives: √ E[Cost(RACE, I)] = O(mρ + mn). Since OPT incurs at least one switching cost in each of the mpfast-channel availability intervals it uses, the expected switching-cost competitive ratio is O(ρ + n/m). Together with the latency bound, this proves Theorem 1. Lower Bounds. For Theorem 2(A), we choose no eviction with probability 1/2, or otherwise introduce a one-mini-slot eviction at a uniformly random fast mini-slot boundary strictly inside a slow-channel slot, after the required initial availability period. OPT finishes in O(n/ρ) slots with constant switching cost. Even a one-mini-slot eviction can force the algorithm to wait until the next slow-slot boundary before returning to the fast channel. By Markov’s inequality, with constant probability over the algorithm’s random choices, it finishes the no-eviction instance quickly. Fix any such choice of randomness and consider the resulting execution. Slow-channel successes and fast-channel successes in the first constant number of slow slots total only o(n), so Ω(n) packets succeed on the fast channel thereafter, before the algorithm finishes. We group those packets by their last move onto the fast channel before success. If there are many groups, batch admissions already incur substantial switching cost. Otherwise, packets remain on the fast channel long enough that a randomly chosen eviction incurs substantial cost. For group sizes si , the total time spent by packets on the fast channel, P summed over packets and mini-slots, is Ω( i s2i ) after accounting for constant-size groups and excluding mini-slot boundaries that coincide with slow-slot boundaries. Cauchy–Schwarz gives us the tradeoff: √ Ω(g) + Ω(n/g) = Ω( n), where g is the number of groups. Averaging over the algorithm’s random choices and the distribution of eviction schedules shows that some fixed eviction schedule yields the claimed expected switching-cost lower bound. The second lower bound considers an eviction that begins immediately after the first mini-slot of a slow-channel slot and leaves the fast channel permanently unavailable. The key observation is that, to achieve latency within a constant factor of OPT, an online algorithm must have Ω(ρ) packets on the fast channel during a constant fraction of the relevant slow slots, with constant probability. By choosing the eviction time uniformly at random from these slots, independently of the algorithm’s random choices, we obtain expected eviction cost Ω(ρ). Averaging gives a fixed schedule with expected switching-cost ratio Ω(ρ), since OPT attains minimum latency with unit switching cost.

5

Conclusion and Future Work

We introduced an online model for contention resolution under dynamic spectrum sharing, where a high-rate fast channel may be interrupted by evictions. This extends contention resolution to a setting where packets must balance latency against the cost of moving between channels. For √ Ω(log n) ≤ ρ ≤ O( n), RACE achieves expectedplatency within a constant factor of OPT and, when m ≥ 1, expected switching-cost ratio O(ρ + n/m), using constant-factor augmentation on the fast channel alone. A small population cutoff and an early time cutoff allow the slow channel √ to remain unaugmented. Our lower bounds establish worst-case Ω( n) ratio and a separate Ω(ρ) 13

competitive-ratio lower bound; tight dependence on both ρ and m remains open. Two further interesting directions are to extend the rate range and to allow dynamic arrivals. Acknowledgments and Generative AI Disclosure. This work was supported by the National Science Foundation (NSF) under Grant CNS-2210300. The research problem, model, algorithm design, and overall proof strategy are original contributions of the authors. ChatGPT was used to assist in simplifying and refining parts of the mathematical analysis, as well as improving the clarity and readability of the manuscript. The technical contributions and highlevel exposition remain the work of the authors, who have reviewed all AI-assisted content and take full responsibility for the correctness of the results and any remaining errors.

References [1] Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. Contention resolution with message deadlines. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, page 23–35, New York, NY, USA, 2020. Association for Computing Machinery. [2] B. A. Aldawsari, B. S. Chlebus, and D. R. Kowalski. Broadcasting on adversarial multiple access channels. In Proceedings of the IEEE 18th International Symposium on Network Computing and Applications (NCA), pages 1–4, 2019. [3] Lakshmi Anantharamu, Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. Deterministic broadcast on multiple access channels. In Proceedings IEEE INFOCOM, pages 1–5. IEEE, 2010. [4] Lakshmi Anantharamu, Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. Medium access control for adversarial channels with jamming. In Proceedings of the International Colloquium on Structural Information and Communication Complexity, pages 89–100. Springer, 2011. [5] Lakshmi Anantharamu, Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. Packet latency of deterministic broadcasting in adversarial multiple access channels. Journal of Computer and System Sciences, 99:27–52, 2019. [6] Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, and Elli Zavou. Competitive analysis of fundamental scheduling algorithms on a fault-prone machine and the impact of resource augmentation. Future Generation Computer Systems, 78:245–256, 2018. [7] Baruch Awerbuch, Andrea Richa, and Christian Scheideler. A jamming-resistant MAC protocol for single-hop wireless networks. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 45–54, 2008. [8] Yucel Aydin, Gunes Karabulut Kurt, Enver Ozdemir, and Halim Yanikomeroglu. Group handover for drone base stations. IEEE Internet of Things Journal, 8(18):13876–13887, 2021. [9] Ioana Banicescu, Trisha Chakraborty, Seth Gilbert, and Maxwell Young. A survey on adversarial contention resolution. ACM Computing Surveys, 57(11), June 2025. [10] Amotz Bar-Noy and Richard E Ladner. Windows scheduling problems for broadcast systems. SIAM Journal on Computing, 32(4):1091–1113, 2003. [11] Amotz Bar-Noy, Richard E Ladner, and Tami Tamir. Windows scheduling as a restricted version of bin packing. ACM Transactions on Algorithms (TALG), 3(3):28–es, 2007. 14

[12] Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. Adversarial contention resolution for simple channels. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325–332, 2005. [13] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, John Kuszmaul, and Maxwell Young. Fully energy-efficient randomized backoff: Slow feedback loops yield fast contention resolution. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 231–242. ACM, 2024. [14] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, John Kuszmaul, and Maxwell Young. Jamming-resistant backoff with polylogarithmic sending and listening cost. SIAM Journal on Computing, 54(5):1335–1385, 2025. [15] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 636–654, 2016. [16] Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. Contention resolution with log-logstar channel accesses. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 499–508, 2016. [17] Sudeep Bhattarai, Jung-Min Jerry Park, Bo Gao, Kaigui Bian, and William Lehr. An overview of dynamic spectrum sharing: Ongoing initiatives, challenges, and a roadmap for future research. IEEE Transactions on Cognitive Communications and Networking, 2(2):110–128, 2016. [18] Martin Böhm, Łukasz Jeż, Jiří Sgall, and Pavel Veselỳ. On packet scheduling with adversarial jamming and speedup. Annals of Operations Research, 298(1):7–42, 2021. [19] Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P Williamson. Adversarial queuing theory. Journal of the ACM (JACM), 48(1):13–38, 2001. [20] Michael A. Calabrese. Use it or share it: A new default policy for spectrum management. Technical report, Open Technology Institute at New America, February 2021. Presented at the 48th Research Conference on Communication, Information and Internet Policy (TPRC48). [21] Jin Cao, Maode Ma, Hui Li, Yulong Fu, and Xuefeng Liu. Eghr: Efficient group-based handover authentication protocols for mmtc in 5g wireless networks. Journal of Network and Computer Applications, 102:1–16, 2018. [22] Raied Caromi and Michael Souryal. Detection of incumbent radar in the 3.5 ghz cbrs band using support vector machines. In 2019 Sensor Signal Processing for Defence Conference (SSPD), pages 1–5, 2019. [23] Wun-Tat Chan and Prudence WH Wong. On-line windows scheduling of temporary items. In International Symposium on Algorithms and Computation, pages 259–270. Springer, 2004. [24] Haimin Chen, Yonggang Jiang, and Chaodong Zheng. Tight trade-off in contention resolution without collision detection. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 139–149, 2021. [25] Bogdan S. Chlebus. Randomized communication in radio networks. Handbook of Randomized Computing, 1:401–456, 2001. 15

[26] Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. Stability of the multipleaccess channel under maximum broadcast loads. In Proceedings of the Symposium on Self-Stabilizing Systems (SSS), pages 124–138. Springer, 2007. [27] Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. Maximum throughput of multiple access channels in adversarial environments. Distributed Computing, 22(2):93–116, 2009. [28] George Christodoulou, Themistoklis Melissourgos, and Paul G. Spirakis. Strategic contention resolution in multiple channels. In Proceedings of the International Workshop on Approximation and Online Algorithms, pages 165–180, 2018. [29] György Dósa, Armin Fügenschuh, Zhiyi Tan, Zsolt Tuza, and Krzysztof Węsek. Tight lower bounds for semi-online scheduling on two uniform machines with known optimum. Central European journal of operations research, 27(4):1107–1130, 2019. [30] György Dósa, Armin Fügenschuh, Zsolt Tan, Zsolt Tuza, and Krzysztof Węsek. Tight upper bounds for semi-online scheduling on two uniform machines with known optimum. Central European Journal of Operations Research, 26(1):161–180, 2018. [31] György Dósa, Yuxin Wang, Xin Han, and He Guo. Online scheduling with rearrangement on two related machines. Theoretical Computer Science, 412(8):642–653, 2011. [32] Matthias Englert, David Mezlaf, and Matthias Westermann. Online makespan scheduling with job migration on uniform machines. Algorithmica, 83(12):3537–3566, 2021. [33] Leah Epstein and Hanan Zebedat-Haider. Preemptive online scheduling with rejection of unit jobs on two uniformly related machines. Journal of Scheduling, 17(1):87–93, feb 2014. [34] Martín Farach-Colton, Katia Leal, Miguel A Mosteiro, and Christopher Thraves Caro. Dynamic windows scheduling with reallocation. Journal of Experimental Algorithmics (JEA), 26:1–19, 2021. [35] Federal Communications Commission. 3.5 GHz band overview: Spectrum access system (SAS), 2024. Available on the FCC website. [36] Paweł Garncarek, Tomasz Jurdziński, and Krzysztof Loryś. Fault-tolerant online packet scheduling on parallel channels. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 347–356. IEEE, 2017. [37] Chryssis Georgiou and Dariusz R. Kowalski. On the competitiveness of scheduling dynamically injected tasks on processes prone to crashes and restarts. Journal of Parallel and Distributed Computing, 84:94–107, 2015. [38] Mihály Geréb-Graus and Thanasis Tsantilas. Efficient optical communication in parallel computers. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 41–48, 1992. [39] Ronald I. Greenberg and Charles E. Leiserson. Randomized routing on fat-trees. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science (FOCS), pages 241–249, 1985. [40] Austin Halper, Miguel A. Mosteiro, Yulia Rossikova, and Prudence W. H. Wong. Station assignment with reallocation. Algorithmica, 81:1096–1125, 2018. [41] Institute for Defense Analyses. Federal spectrum sharing: An assessment of the technology and opportunities. Technical Report P-5186, Institute for Defense Analyses (IDA), 2015. Accessed: 2026-02-13. 16

[42] Tomasz Jurdziński, Dariusz R. Kowalski, and Krzysztof Loryś. Online packet scheduling under adversarial jamming. In Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11–12, 2014, Revised Selected Papers, volume 8952 of Lecture Notes in Computer Science, pages 193–206. Springer, 2015. [43] Tomasz Jurdziński, Mirosław Kutyłowski, and Jan Zatopiański. Energy-efficient size approximation of radio networks with no collision detection. In Proceedings of the 8th Annual International Conference (COCOON), pages 279–289, 2002. [44] J. Komlos and A. Greenberg. An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Transactions on Information Theory, 31(2):302– 306, 1985. [45] Dariusz R. Kowalski. On selection problem in radio networks. In Proceedings of the TwentyFourth Annual ACM Symposium on Principles of Distributed Computing, PODC ’05, page 158–166, New York, NY, USA, 2005. Association for Computing Machinery. [46] P. Liu and Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 5(1):95–102, 2009. [47] Marten Maack. Online load balancing on uniform machines with limited migration. Operations Research Letters, 51(3):220–225, 2023. [48] Adrian Ogierman, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Competitive MAC under adversarial SINR. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), pages 2751–2759, 2014. [49] Olusegun O Omitola and Viranjay M Srivastava. Group handover strategy for mobile relays in lte-a networks. Journal of Communications, 13(9):505–511, 2018. [50] Jon M. Peha. Spectrum management policy options. IEEE Communications Surveys, 1(1):2–8, 1998. [51] Tim Roughgarden. Resource augmentation. CoRR, abs/2007.13234, 2020. [52] Jianjun Wen and Donglei Du. Preemptive on-line scheduling for two uniform processors. Operations Research Letters, 23(3):113–116, 1998. [53] Yang Xiao, Shanghao Shi, Wenjing Lou, Chonggang Wang, Xu Li, Ning Zhang, Y Thomas Hou, and Jeffrey H Reed. Decentralized spectrum access system: Vision, challenges, and a blockchain solution. IEEE Wireless Communications, 29(1):220–228, 2022. [54] Zheng, Feifeng, Chen, Yuhong, and Liu, Ming. Semi-online scheduling on two uniform parallel machines with initial lookahead. RAIRO-Oper. Res., 58(3):2621–2630, 2024.

17

A

Supporting Analysis

This appendix provides execution details and full proofs supporting the main results.

A.1

Execution Details

TSTB Execution Windows. We describe how RACE uses Truncated Sawtooth-Backoff (TSTB) [16]. For an integer parameter z, a TSTB execution consists of a predetermined sequence of contention windows containing a total of L(z) = O(z) slots. The first window contains 2z slots. On the fast channel, each such slot corresponds to one fast-channel mini-slot. Each active packet independently selects one slot uniformly at random in each window, and successful packets depart. A fresh TSTB execution with z packets leaves at least one packet unfinished with probability O(z −d ), for some fixed d ≥ 2. If necessary, this guarantee can be obtained through a constant number of repetitions without changing the execution length L(z) = O(z). A TSTB execution can be paused and later resumed from where it stopped, without restarting its sequence of contention windows. Each TSTB slot corresponds to one slow-channel slot when executed on the slow channel, or one fast-channel mini-slot when executed on a logical fast subchannel. Reporting Evictions. Every fast round lasts for its scheduled D(x) slots, even if all selected packets succeed earlier. Packets evicted before the scheduled end return to the slow channel and wait. At the end of the scheduled execution, any packets still on the fast channel also return to the slow channel. The next slow-channel slot is left idle to allow all remaining packets to return. During the following slot, packets that were evicted before the scheduled end and have not yet succeeded transmit to report the eviction. All other packets listen. An empty report certifies the round, while a nonempty report aborts it. If exactly one packet reports, its transmission succeeds, but W is not incremented. Thus, every remaining packet learns whether the round was certified or aborted, even if the fast channel is no longer available. Cleanup. When either cutoff is reached, RACE permanently stops using the fast channel. A fast round already in progress finishes before cleanup begins, whereas an ongoing call to Estimate is stopped if the time cutoff is reached. If the initial estimation finishes after the time cutoff, RACE enters cleanup immediately. During cleanup, the remaining packets execute TSTB on the slow channel with successively doubled size parameters s0 , 2s0 , 4s0 , . . ., until all packets succeed. The initial parameter is b cur when cleanup s0 = max{v, smin }, where smin is a sufficiently large fixed constant. Here v = n b when triggered by the time cutoff. Lemma 10 is triggered by the population cutoff, and v = n establishes that, starting with r active packets, the expected cleanup time is O(r + v). Minimum Fast-Channel Availability. The analysis requires each interval of fast-channel availability to contain sufficiently many slots to accommodate consecutive rounds of intended per-subchannel size ρ, including their reporting slots. Specifically, it suffices to require Cavail ≥ 2D(ρ) + 8. Since D(ρ) = O(1), this requires only a fixed constant number of slots. This assumption is used in Lemma 3 to bound the number of aborted rounds.

A.2

Fresh-Window Estimates

We begin with two properties of fast-channel batches: a bound on the expected number of packets that remain unsuccessful after an uninterrupted TSTB execution, and a high-probability guarantee on the number of packets that succeed. b cur active packets. For any one logical Lemma 1. Consider a fast round that begins with r ≤ n fast subchannel, let Z be the number of packets that would remain unsuccessful after its full

18

scheduled TSTB execution, assuming no eviction occurs. Then E[Z] = O(1), where the expectation is over the random choices made during the round. Proof. Let Y be the number of packets assigned to the subchannel. Since each active packet b cur , we have: independently selects it with probability x/n rx ≤ x. E[Y ] = b cur n First, suppose Y ≤ 2x. Compare the TSTB execution with one containing exactly 2x packets by adding imaginary packets. Each real packet makes the same random choices in both executions. Adding packets cannot help a real packet succeed earlier, so the number of unfinished real packets is at most the number left unfinished in the larger execution. Since TSTB runs with parameter 2x, its completion guarantee implies that the larger execution leaves any packet unfinished with probability O(x−d ), where d ≥ 2. Consequently, the contribution to E[Z] from Y ≤ 2x is at most: 2x · O(x−d ) = O(1). Now suppose Y > 2x. By a standard Chernoff bound: Pr(Y > 2x) ≤ exp(−Ω(x)). Since Y is binomial, Var(Y ) ≤ E[Y ] ≤ x. By the definition of variance: Var(Y ) = E[(Y − E[Y ])2 ] = E[Y 2 ] − (E[Y ])2 . Rearranging gives:

E[Y 2 ] = Var(Y ) + (E[Y ])2 ≤ x + x2 .

We now use Cauchy–Schwarz to bound the contribution to E[Y ] from the event Y > 2x. Applied to the conditional distribution given this event, Cauchy–Schwarz gives: (E[Y | Y > 2x])2 ≤ E[Y 2 | Y > 2x]. Multiplying by Pr(Y > 2x)2 and taking square roots, we obtain: E[Y | Y > 2x] Pr(Y > 2x) ≤

q

E[Y 2 | Y > 2x] Pr(Y > 2x)2 .

Since the event Y > 2x contributes at most E[Y 2 ] to the second moment, we also have: E[Y 2 | Y > 2x] Pr(Y > 2x) ≤ E[Y 2 ]. Combining these inequalities gives: E[Y | Y > 2x] Pr(Y > 2x) ≤

q

E[Y 2 ] Pr(Y > 2x) ≤

q

(x + x2 ) exp(−Ω(x)) = O(1).

Since Z ≤ Y , this also bounds the contribution to E[Z] from Y > 2x. Finally, combining the two cases gives E[Z] = O(1). Lemma 2. Let K = 64. Consider a fast-channel round that begins with r active packets satisfying: b cur n b cur . ≤r≤n 2K With probability at least 1 − O(λe−Ω(x) ), each logical fast subchannel receives between x/(4K) and 2x packets. Moreover, if the scheduled TSTB execution on each subchannel runs to completion without interruption, at least αx of its packets succeed, where α > 0 is a fixed constant independent of λ. 19

Proof. Consider one logical fast subchannel, and let Y be the number of packets assigned to b cur . it. Each of the r active packets independently chooses this subchannel with probability x/n Consequently, Y is a binomial random variable with expectation: E[Y ] = By the assumption on r, we have:

rx . b cur n

b cur n b cur . ≤r≤n 2K

b cur gives: Multiplying by x/n

x ≤ E[Y ] ≤ x. 2K We first show that the number of packets assigned to the subchannel is between x/(4K) and 2x with high probability. Since E[Y ] ≥ x/(2K), a standard Chernoff lower-tail bound gives: x Pr Y < 4K





≤ exp(−Ω(x)).

Similarly, since E[Y ] ≤ x, a Chernoff upper-tail bound gives: Pr(Y > 2x) ≤ exp(−Ω(x)). Thus, with probability at least 1 − exp(−Ω(x)), the number of packets assigned to the subchannel satisfies: x ≤ Y ≤ 2x. 4K We now show that a constant fraction of these packets succeed during an uninterrupted TSTB execution. Suppose exactly y packets have been assigned to the subchannel, where: x ≤ y ≤ 2x. 4K The TSTB execution uses parameter 2x, so its first contention window contains 4x mini-slots. Each of the y packets independently chooses one of these mini-slots uniformly at random. Let Z be the number of packets that choose a mini-slot not chosen by any other packet. Each such packet transmits successfully during the first window. For any particular packet, the probability that none of the other y − 1 packets chooses its mini-slot is: 

1 4x

y−1



1 4x

1−

By linearity of expectation: E[Z] = y 1 −

.

y−1

.

For any particular packet, a union bound implies that the probability of at least one other packet choosing the same mini-slot is at most (y − 1)/(4x). Since y ≤ 2x, the probability that no other packet chooses its mini-slot is therefore at least: 1−

1 y−1 ≥ , 4x 2

and consequently E[Z] ≥ y/2. We next show that Z is unlikely to be much smaller than its expectation. We use McDiarmid’s bounded-differences inequality, which applies to functions of independent random variables. The y independently chosen mini-slots determine Z. Suppose we change the mini-slot selected by one packet while keeping all other packets’ choices fixed. This can affect the number of successful 20

transmissions in at most two mini-slots: the one originally selected and the new one. In each, the number of successes can change by at most one. Thus, Z can change by at most two. Thus, the bounded-differences inequality gives, for any u > 0: 2u2 Pr(Z ≤ E[Z] − u) ≤ exp − 4y

!

.

Since E[Z] ≥ y/2, choosing u = y/4 yields: 

Pr Z <

y 4





≤ exp −

y . 32 

Because y ≥ x/(4K), this probability is exp(−Ω(x)). Hence, except with this probability, at least: y x ≥ 4 16K packets succeed during the first TSTB window. Combining this result with the Chernoff bounds, we conclude that a particular logical fast subchannel receives between x/(4K) and 2x packets and completes at least αx packets during an uninterrupted execution, except with probability exp(−Ω(x)), for some fixed constant α > 0 independent of λ. Finally, RACE uses λ logical fast subchannels. Applying a union bound over these subchannels, the probability that any subchannel fails either guarantee is at most O(λe−Ω(x) ), which completes the argument. Consequences of Lemma 2 for Fast Rounds. Let G denote the event that all population estimates satisfy their accuracy guarantees and that the packet-assignment and progress guarantees of Lemma 2 hold for every fast round to which that lemma applies. Later on, Lemmas 5 and 7 establish that, on G, the lemma applies to every fast round and that G occurs with high probability. The preceding lemma therefore implies that, on event G, each certified round completes at least αλx packets. This follows because either the round was not interrupted by an eviction, or an eviction occurred after all selected packets had already succeeded. Otherwise, an unfinished packet would have reported the eviction, causing the round to be aborted. On G, the lemma also guarantees that at most 2λx packets are selected for any round, whether certified or aborted.

A.3

Charging Aborted Rounds

Recall that D(ρ) = O(1) and that Cavail was chosen to satisfy Cavail ≥ 2D(ρ) + 8 for every integer ρ ≥ 2. A necessary portion of our argument is that the minimum duration of fast-channel availability guarantees that, after an aborted round, RACE has enough time to complete its next round with x = ρ without another eviction, unless it invokes the population estimator in between. Lemma 3. Consider two fast rounds, each with an intended batch size of x = ρ packets per logical subchannel. If no certified round or invocation of Estimate occurs between them, then the two rounds cannot both be aborted. Proof. Suppose two fast rounds with x = ρ occur without a certified round or an invocation of Estimate between them. We show that if the first round is aborted, the second cannot be aborted. The key observation is that the first round may begin near the end of an interval of fastchannel availability, leaving insufficient time to finish before an eviction. However, after this eviction, the next round with x = ρ begins sufficiently early in a new interval of availability to finish without interruption. 21

Let the first round begin at slow-slot boundary t. Since it is aborted, an eviction must have occurred before its scheduled D(ρ) slots of TSTB execution finished. Nevertheless, RACE waits until the scheduled execution ends and then uses two additional slots to determine whether an eviction occurred. Thus, the first round ends at time t + D(ρ) + 2, and RACE cannot begin another fast round before then. We consider two cases, depending on when the fast channel becomes available again after the eviction that interrupted the first round. Case 1: After the eviction, the fast channel becomes available again before the first round ends. The new interval of fast-channel availability begins no earlier than t, so at most D(ρ) + 2 slow slots have elapsed between the beginning of that interval and the end of the first round. Since every interval of fast-channel availability contains at least Cavail ≥ 2D(ρ) + 8 complete slow slots, enough time remains for RACE to execute another D(ρ) slots of TSTB without interruption. Thus, if RACE begins the second round, it completes its scheduled TSTB execution before another eviction can occur. Case 2: After the eviction, the fast channel becomes available again at or after the first round ends. RACE observes that the fast channel is available at the next slow-slot boundary. Because no population estimate or certified round intervenes, RACE begins its next fast round at that boundary, provided it has not entered cleanup. At most one slow slot is lost between the beginning of the new interval of availability and the start of this round. The minimum-availability condition therefore guarantees that the fast channel remains available throughout its scheduled D(ρ) slots of TSTB execution. In either case, the second round completes its scheduled TSTB execution without eviction and therefore cannot be aborted. If the fast channel never becomes available again, or RACE enters cleanup, no second round occurs. This completes the argument. Recall that an estimation epoch begins when RACE obtains a new estimate of the number of active packets and ends when RACE next invokes Estimate or enters permanent slow-channel cleanup. At the beginning of each epoch, W is reset to zero. In the following lemma, F denotes an upper bound on the intended number of packets per subchannel during the fast rounds being considered. We will specify a suitable value of F later in the analysis. Lemma 4. Consider RACE’s execution up to any time t before cleanup. Suppose every fast round has intended per-subchannel batch size x = ρ + b ≤ F . Let h be the number of calls to Estimate that have started after the initial estimate and by time t, including any call still in progress. Let V and I be the sums of x over certified and aborted rounds, respectively, whose reporting slots have finished by time t. Then: I ≤ 4V + ρ(h + 1). Within any single estimation epoch j, the corresponding sums satisfy: Ij ≤ 4Vj + 4F. Proof. We first establish the bound over the entire execution and we consider three cases. Case 1. Consider an aborted round with intended per-subchannel batch size x = ρ + t, where t ≥ 1. Since an abort resets b to zero, RACE must have previously completed t certified rounds with intended per-subchannel batch sizes ρ, ρ + 1, . . . , ρ + t − 1 since the preceding abort. The sum of these sizes is at least tρ. Moreover, since ρ ≥ 1 and t ≥ 1, we have: ρ + t ≤ 2tρ ≤ 2 22

t−1 X i=0

(ρ + i).

Thus, the intended size of the aborted round is at most twice the sum of the intended sizes of these preceding certified rounds. Since the certified rounds used in this argument are different for each aborted round, the total intended size of all aborted rounds with x > ρ is at most 2V . Case 2. We must also account for aborted rounds with x = ρ. Consider such a round that follows an earlier aborted round with x > ρ, without any certified round between them. Its intended size ρ is at most that of the earlier aborted round, so the total contribution from these rounds is bounded by the contribution already established above in Case 1. Case 3. The remaining possibility is an aborted round with x = ρ that either occurs first or follows another aborted round with x = ρ. By Lemma 3, the latter situation requires an intervening call to Estimate. Hence, there can be at most one such additional aborted round for each call to Estimate, plus one at the beginning of the execution. Their combined intended size is at most ρ(h + 1). Combining these bounds gives:

I ≤ 4V + ρ(h + 1).

We next establish the bound within a single estimation epoch j. The argument is similar, except that the first aborted round with x > ρ may have been preceded by certified rounds belonging to an earlier epoch. We therefore account for this round separately, using the assumption that its intended per-subchannel batch size is at most F . For every subsequent aborted round with x > ρ, the preceding certified rounds needed to reach its batch size belong to the current epoch. As before, their intended sizes account for at most twice their sum in aborted rounds. Consequently, the sum of the intended sizes of aborted rounds with x > ρ during epoch j is at most 2Vj + F . Finally, each aborted round with x = ρ can be accounted for by an earlier aborted round with x > ρ, with at most one exception per epoch by Lemma 3. Thus, the total intended size of aborted rounds with x = ρ is at most 2Vj + F + ρ. Combining these contributions, and using ρ ≤ F , gives: Ij ≤ 4Vj + 2F + ρ ≤ 4Vj + 4F, which completes the proof.

A.4

Accuracy and Measurement Frequency

We now establish that RACE maintains an accurate estimate of the number of active packets throughout its execution, and that only O(log n) population estimates are needed. We also show that the intended fast-batch sizes remain sufficiently small that the limit imposed by the current population estimate does not affect the increasing sequence of batch sizes. Let G0 denote the event that the initial call to Estimate returns an estimate satisfying b ≤ 32n and finishes in O(log2 n) slots. We establish that this event occurs with high n ≤ n probability in Appendix C. p For the analysis, let F be a sufficiently large constant multiple of ρ + n/λ, where the constant is independent of λ. Thus: 

F = CF ρ +

q

√ n/λ = O( n). 

where CF > 0 is a sufficiently large fixed constant independent of λ. We will show that F bounds the intended number of packets per subchannel in every fast round. This bound is used only in the analysis and does not affect the algorithm. As in Lemma 2, we use K = 64 as a fixed constant in our bounds on the accuracy of the population estimates. Recall that δ > 0 determines when RACE requests a new estimate, 23

b cur , and the constant cpop > 0 determines the population cutoff τpop = ⌈cpop n b /ρ⌉. To W ≥ δn make the requirements on these constants clear, we choose δ sufficiently small and cpop sufficiently large so that: 1 τpop 10δ ≤ , 20λF + 20 ≤ , τpop ≥ 2λρ. (3) 8K 8K These conditions ensure that the number of packets completing between population estimates b) ≤ remains small enough for the current estimate to stay accurate. On G0 , we also have τest (n τpop /(4K) for sufficiently large n. We justify these choices of constants later on in this analysis. Finally, let G denote the event that the initial estimate satisfies the guarantees above, every subsequent completed call to Estimate satisfies its accuracy guarantee, and the packetassignment and TSTB progress guarantees of Lemma 2 hold whenever a fast round begins with r active packets satisfying: b cur n b cur . ≤r≤n 2K Here, the TSTB progress guarantee concerns the packets that would succeed if the scheduled execution were not interrupted by an eviction. The next lemma establishes that, on event G, RACE maintains a sufficiently accurate estimate of the number of active packets throughout its execution before cleanup. It also shows that the intended number of packets per subchannel remains below F and follows x = ρ + b, without being restricted by the current population estimate. Together, these properties allow us to apply the fast-channel progress guarantees of Lemma 2 throughout RACE’s execution. b cur,j denote the actual number of active packets and Lemma 5. On event G, let Nj and n RACE’s estimate of that number, respectively, at the beginning of estimation epoch j. Then: b cur,j ≤ KNj . Nj ≤ n

Moreover, whenever RACE begins a fast round with r active packets, we have: b cur n b cur . ≤r≤n 2K

Finally, the intended number of packets per subchannel satisfies x = ρ + b < F , where F is the upper bound defined above. Consequently, whenever RACE begins a fast round, the intended b cur /λ⌋ in the batch-size formula number of packets per subchannel is x = ρ + b: the upper limit ⌊n never restricts x before cleanup. Proof. We prove the claims simultaneously by induction over successive fast rounds and population-estimate updates. The base case follows from the initial population-estimation guarantee described in Section 3.1, whose proof appears in Appendix C. For the induction, we assume the claims hold for all preceding rounds and estimates. In particular, the estimates were sufficiently accurate for Lemma 2 to apply to those earlier rounds. We show that their progress and the bounds on their sizes preserve the required guarantees when RACE begins another fast round or obtains a new population estimate. b ≤ 32n. Since the initial call to Estimate On event G0 , the initial estimate satisfies n ≤ n takes O(log2 n) slots, at least n/2 packets remain active when it finishes, for sufficiently large n. Thus, if N0 is the number of active packets at the beginning of the first estimation epoch, then: b ≤ KN0 , N0 ≤ n

where K = 64. Bounding fast-channel batch sizes. Suppose the claims have held for all preceding fast rounds and population estimates. If the current batch index is b, then RACE has certified b rounds since the last reported abort. In these rounds, the intended number of packets per subchannel 24

increases through the sequence ρ, ρ + 1, . . . , ρ + b − 1. On event G, Lemma 2 guarantees that these rounds complete at least: b−1 X αλb2 αλ (ρ + i) ≥ 2 i=0 distinct packets. Since there are only n packets, we obtain: r

b≤

2n . αλ

b cur > τpop , and our choice of Thus ρ + b < F , by our choice of F . Furthermore, before cleanup, n constants in (3) guarantees:   b cur n > F. λ Consequently, whenever RACE begins another fast round, its intended number of packets per subchannel is x = ρ + b < F .

Maintaining accurate population estimates. Consider estimation epoch j, beginning with Nj b cur,j ≤ KNj . active packets and an estimate satisfying Nj ≤ n Let Cs count slow-channel TSTB successes during this epoch, and let Vj and Ij be the sums of the intended per-subchannel batch sizes over certified and aborted rounds, respectively. Recall that W = Cs + λVj . By the induction hypothesis, preceding fast rounds began with sufficiently accurate population estimates. Thus, on event G, Lemma 2 guarantees that at most 2λx packets participated in each of those rounds. Since Vj + Ij sums their intended per-subchannel batch sizes, at most 2λ(Vj + Ij ) packets could have succeeded during these rounds. We must also account for a round that may still be underway, whose successful packets are not yet included in these sums. Since its intended per-subchannel batch size is at most F , it can contribute at most another 2λF successful packets on G. Including the Cs slow-channel TSTB successes, and using Ij ≤ 4Vj + 4F from Lemma 4 together with W = Cs + λVj , we obtain: Cs + 2λ(Vj + Ij ) + 2λF ≤ 10W + 10λF.

(4)

b cur,j . Because each increase in W is at RACE requests a new estimate when W reaches δ n most λF + 1, the preceding bound implies that, before the next estimate begins, at most: b cur,j + 20λF + 20 ≤ 10δ n

b cur,j n 4K

packets have succeeded, where the final inequality follows from (3). b cur,j /K packets were active at the beginning of the epoch, the number r of Since at least n active packets before the next estimate satisfies: b cur,j n b cur,j . ≤r≤n 2K

Thus the estimate remains sufficiently accurate for Lemma 2 to apply whenever RACE begins another fast round. Finally, when RACE requests a new estimate, at least: b cur,j n τpop b) ≥ ≥ 2τest (n 2K 2K

packets remain active. Lemma 18 therefore guarantees that, unless all remaining packets succeed during estimation, the new estimate is within a factor of 16 of the actual number of active packets when the estimator finishes. Since K = 64, the required accuracy guarantee holds at the beginning of the next epoch. If the time cutoff interrupts the estimator, RACE enters cleanup instead. This completes the induction argument and establishes all three claims. 25

Lemma 6. On event G, RACE invokes Estimate at most O(log n) times after the initial b cur,j denotes the estimate at the beginning of estimation epoch j, then: estimate. Moreover, if n X

b cur,j = O(n). n

j

Proof. Consider an estimation epoch j that ends when RACE invokes Estimate. At that point, the counter satisfies: b cur,j , W = Cs + λVj ≥ δ n where Cs counts successful slow-channel TSTB transmissions and Vj is the sum of the intended per-subchannel batch sizes over certified rounds during the epoch. On event G, each certified round completes at least an α fraction of the number of packets credited to W . Therefore, the number of packets that have succeeded during epoch j is at least: b cur,j ≥ αδNj , Cs + αλVj ≥ αW ≥ αδ n

where Nj is the number of active packets at the beginning of the epoch. Any additional successful transmissions can only decrease the number of active packets further. Consequently, if another estimation epoch follows, its initial number of active packets satisfies: Nj+1 ≤ (1 − αδ)Nj , and thus the number of active packets decreases by a constant factor between successive estimation epochs. Consequently, RACE invokes Estimate at most O(log n) times after the initial estimate. b cur,j ≤ KNj on event G. Since the values Nj decrease Finally, Lemma 5 guarantees that n geometrically and N0 ≤ n, we have: X j

b cur,j ≤ K n

X

Nj ≤

j

Kn = O(n). αδ

This establishes both claims. Lemma 7. For any fixed D ≥ 10, by choosing sufficiently large constants in the running time of Estimate and in the assumption ρ = Ω(log n), we obtain: Pr(¬G) = O(n−D ). Proof. We bound the probability that RACE obtains an inaccurate population estimate or that a fast round fails the guarantees of Lemma 2. Recall that G0 is the event that the initial call to Estimate returns an estimate satisfying b ≤ 32n and finishes in O(log2 n) slots. On event G0 , the initial estimate satisfies n ≤ n b ≤ 32n. Since RACE begins no new fast rounds or calls to Estimate after the time cutoff n≤n b ) = O(n), at most O(n) fast rounds and subsequent calls to Estimate can begin. τtime = O(n Consider any fast round that begins with r active packets satisfying: b cur n b cur . ≤r≤n 2K

By Lemma 2, the probability that any subchannel receives too many or too few packets, or that too few packets succeed during an uninterrupted TSTB execution, is at most O(λe−Ω(x) ) ≤ O(λe−Ω(ρ) ), since x ≥ ρ. Because each fast round uses fresh independent random choices, this probability bound holds regardless of the outcomes of preceding rounds. The analysis of Estimate in Appendix C establishes that each subsequent call returns an accurate estimate with failure probability smaller than any prescribed inverse polynomial in 26

n, provided sufficiently many packets remain active. This guarantee holds regardless of the outcomes of earlier calls. On event G0 , RACE begins at most O(n) fast rounds and calls to Estimate before cleanup. For each fast round satisfying the assumptions of Lemma 2, the probability that its guarantees fail is at most O(λe−Ω(ρ) ). Similarly, the analysis of Estimate in Appendix C shows that the failure probability of each population estimate can be made smaller than any prescribed inverse polynomial in n. Since these guarantees hold regardless of the outcomes of preceding rounds and estimates, we can apply a union bound over all O(n) operations. By choosing the constants in the estimator and in ρ = Ω(log n) sufficiently large, the probability that any of these guarantees fails, given G0 , is O(n−D ). It remains to justify applying Lemma 2 throughout RACE’s execution. Lemma 5 establishes that, as long as preceding rounds and population estimates satisfy their guarantees, the number of active packets remains within the range required by Lemma 2. Thus, the assumptions of that lemma continue to hold unless one of the failures already accounted for in the union bound occurs. Finally, the initial population-estimation guarantee established in Appendix C gives Pr(¬G0 ) = O(n−D ), and combining this with the preceding bound yields the claimed upper bound.

A.5

Early Cutoff and Fast-Service Accounting

For any slow-slot boundary t, let Servicef ([0, t)) denote the number of fast-channel mini-slots during which the fast channel is available before time t. Since OPT can transmit at most one packet per fast-channel mini-slot and one packet per slow-channel slot, the total number of packets OPT can complete by time t is at most: Service([0, t)) = t + Servicef ([0, t)). This bound may include fast-channel mini-slots that OPT cannot use because packets can switch channels only at slow-slot boundaries. Nevertheless, since OPT completes all n packets by time T ∗ = L(OPT, I), we must have: Service([0, T ∗ )) ≥ n. We next establish an upper bound on Service([0, t)) for times when RACE has neither completed all packets nor entered permanent slow-channel cleanup. This bound will allow us to show that RACE stops admitting new fast-channel batches by the time OPT finishes. Lemma 8. On event G, consider any slow-slot boundary t < τtime at which RACE has neither completed all packets nor entered permanent slow-channel cleanup. Then: Service([0, t)) ≤ t + O(n/λ) + O ρ log3 (n + 2) + F .

(5)

The constant implicit in O(n/λ) is independent of λ and the constants used by Estimate. Proof. Let A be the number of fast rounds that begin by time t, and let h be the number of calls to Estimate that begin after the initial estimate and by time t. Let M be the total number of slots spent executing Estimate before time t, including the initial call and any call still in progress. We first bound the number of fast-channel transmission opportunities available to OPT while RACE executes fast rounds. A round with intended per-subchannel batch size x lasts: D(x) + 2 = O(x/ρ) slow slots, since x ≥ ρ. During these slots, OPT has at most O(x) fast-channel transmission opportunities. Since RACE executes only one fast round at a time, summing over all rounds that 27

begin by time t shows that OPT has at most O( x) fast-channel transmission opportunities during these rounds. Similarly, the slots spent executing Estimate contribute at most ρM fast-channel transmission opportunities. We must also account for times when RACE is executing TSTB on the slow channel and the fast channel becomes available partway through a slot. Since RACE checks fast-channel availability only at slow-slot boundaries, it may miss up to ρ fast-channel mini-slots before responding. The minimum-availability condition ensures that the fast channel remains available at the next boundary, when RACE begins a fast round or invokes Estimate. Each fast round or call to Estimate can therefore be preceded by at most one slow-channel slot during which RACE misses fast-channel availability. Since A fast rounds and h subsequent calls to Estimate have begun by time t, these delays account for at most ρ(A + h) additional fast-channel mini-slots. Allowing another 2ρ for the beginning and end of the interval being analyzed, we obtain: P

Servicef ([0, t)) ≤ O

X 

x + ρM + ρ(A + h + 2).

Since every fast round has x ≥ ρ, we have ρA ≤ Servicef ([0, t)) ≤ O

P

x. Thus, the bound simplifies to:

X 

x + ρM + O(ρ(h + 1)).

It remains to bound the sum of the intended per-subchannel batch sizes. Let V be the sum of x over certified rounds whose reporting slots have finished by time t. On event G, these rounds complete at least αλV packets. Since there are only n packets, we have: V ≤

n . αλ

Lemma 4 bounds the corresponding sum over aborted rounds by 4V + ρ(h + 1). We also include at most one fast round that has begun but whose outcome has not yet been determined. Its intended per-subchannel batch size is at most F . Consequently: X

x ≤ 5V + ρ(h + 1) + F ≤

5n + ρ(h + 1) + F. αλ

By Lemma 6, RACE invokes Estimate at most O(log n) times after the initial estimate, so h = O(log n). Including initialization, the total time spent estimating is M = O(log3 (n + 2)) on event G. Substituting these bounds into the preceding inequalities gives: Servicef ([0, t)) ≤ O(n/λ) + O ρ log3 (n + 2) + F .

Finally, OPT can complete at most t packets on the slow channel by time t. Therefore: Service([0, t)) ≤ t + O(n/λ) + O ρ log3 (n + 2) + F ,

which proves Equation 5. Justifying Our Choice of Constants. We now show that the constants required by our analysis can be chosen consistently. First, we choose δ > 0 sufficiently small to satisfy the requirements of Lemma 5. We then choose the fixed fast-channel augmentation factor λ sufficiently large so that the O(n/λ) term inpEquation 5 is at most n/8. √ Next, recall that F = O(ρ + n/λ). Since ρ = O( n) and λ is fixed, we have λF = O(n/ρ). Thus, by choosing cpop sufficiently large, the population cutoff τpop = Θ(n/ρ) can satisfy all the requirements in (3). We also choose the minimum duration of fast-channel availability sufficiently large for Lemma 3 to apply. Finally, the constants governing the running time of Estimate and the lower bound ρ = Ω(log n) are chosen sufficiently large to establish the probability guarantee in Lemma 7. Since 28

√ ρ = O( n), the remaining terms in (5) are at most n/8 for sufficiently large n. Consequently, under the conditions of Lemma 8, we obtain: Service([0, t)) ≤ t + n/4.

(6)

We now show that RACE stops admitting new fast-channel batches by the time OPT finishes, with high probability. This is important for bounding switching cost, since otherwise RACE could continue using the fast channel and incurring switching costs after OPT has completed all its packets. Lemma 9. Let T ∗ = L(OPT, I) denote OPT’s completion time. On event G, RACE begins no fast round at or after time T ∗ . If T ∗ < τtime , RACE has either completed all packets or entered permanent slow-channel cleanup because the population cutoff was reached by time T ∗ . If T ∗ ≥ τtime , the time cutoff prevents RACE from beginning any further fast rounds. Proof. On G0 , for n ≥ 2: b /64⌋} ≤ n/2. n/128 ≤ τtime = max{1, ⌊n

If T ∗ ≥ τtime , the protocol’s cutoff proves the assertion directly, whether or not a round is currently running. Suppose T ∗ < τtime and RACE has neither completed all packets nor entered permanent slow-channel cleanup by time T ∗ . Initialization takes O(log2 n) = o(n/ρ) slots on G0 , while T ∗ ≥ n/(ρ + 1), so the initial call to Estimate has already finished for sufficiently large n. Since T ∗ < τtime ≤ n/2, Lemma 8 and Equation 6 imply: n ≤ Service([0, T ∗ )) ≤ T ∗ + n/4 < n. This contradiction shows that RACE cannot still be executing before cleanup at time T ∗ . Therefore, RACE must have completed all packets or entered permanent slow-channel cleanup by the time OPT finishes. Because the time cutoff has not yet been reached, any cleanup must have been triggered by the population cutoff, based on RACE’s estimate of the remaining active packets. Once cleanup begins, RACE never uses the fast channel again.

A.6

Cleanup and Worst-Case Bounds

Lemma 10. Suppose RACE enters permanent slow-channel cleanup with r active packets and uses an estimate v to determine the initial TSTB size parameter. Then, regardless of the accuracy of v, the expected time until all remaining packets succeed is O(r + v). Cleanup incurs no switching cost. Proof. RACE begins cleanup with a TSTB execution using size parameter s0 = max{v, smin }, where smin is a sufficiently large fixed constant. If packets remain unsuccessful after this execution, RACE begins another with twice the size parameter. This continues until all packets succeed. First, consider the executions whose size parameters are smaller than r, the number of active packets when cleanup begins. Since the parameters double after each execution and TSTB with parameter s takes O(s) slow-channel slots, the total time spent on these executions is O(r). Once the size parameter s reaches or exceeds r, there are at most s active packets. The TSTB completion guarantee implies that all remaining packets succeed with probability at least 1 − O(s−d ). This guarantee applies even when fewer than s packets participate, because removing competing packets cannot prevent a successful transmission. By choosing smin sufficiently large, the probability that any packets remain unsuccessful after such an execution is at most 1/8. Let s now denote the size parameter of the first execution for which s ≥ r. Since the parameters double, we have s = O(r + v). Each subsequent execution also doubles the parameter, 29

but occurs only if the preceding execution fails to finish all remaining packets. Thus, the expected time spent on these executions is at most: O(s)

X

2j (1/8)j = O(s) = O(r + v).

j≥0

Combining this with the time spent on earlier executions gives expected cleanup time O(r + v). Finally, all transmissions during cleanup occur on the slow channel, so no switching cost is incurred. The preceding analysis relies on high-probability guarantees for population estimation and fast-channel progress. To establish our expected performance bounds, we must also account for executions in which these guarantees fail. The following lemma provides upper bounds that hold regardless of whether those guarantees are satisfied. Lemma 11. Let τ0 be the time spent obtaining the initial population estimate. On every execution, b ) slots, and its RACE either finishes or enters permanent slow-channel cleanup within τ0 + O(n b ). switching cost is O(nn b ), Once cleanup begins, the expected time needed to finish the remaining packets is O(n + n regardless of the accuracy of the population estimates. b ). Since Proof. RACE does not begin any new fast rounds at or after the time cutoff τtime = O(n b ) fast at most one fast round can begin in any slow-channel slot, RACE begins at most O(n rounds before this cutoff. b /λ and lasts: Each fast round has intended per-subchannel batch size x ≤ n b /ρ + 1) = O(n b) D(x) + 2 = O(n

slow slots, including the two slots used to determine whether an eviction occurred. If a round is still underway when the time cutoff is reached, RACE finishes that round before entering permanent slow-channel cleanup. When RACE is executing TSTB on the slow channel or running Estimate, it checks the time cutoff at every slow-slot boundary. If the initial call to Estimate finishes after the cutoff, RACE enters cleanup immediately. Consequently, regardless of the accuracy of its population estimates, RACE either completes b ) slots. all packets or enters cleanup within τ0 + O(n We next bound switching cost. Each fast round moves at most one batch onto the fast channel, incurring one unit of cost. At most n packets can return to the slow channel during that round, and each packet returns at most once, whether because of an eviction or because it b ) fast has not succeeded by the scheduled end of the round. Since RACE begins at most O(n rounds, its total switching cost is: b ). O(nn Finally, when RACE enters cleanup, the initial TSTB size parameter is determined by either b cur , if the population cutoff is reached, or n b , if the time cutoff is reached. Both are at most n b. n Since at most n packets remain active, Lemma 10 guarantees that their expected completion time is: b ). O(n + n This establishes all three bounds. Proposition 1. For every fixed instance I, RACE achieves expected latency: E[L(RACE, I)] = O(L(OPT, I)).

30

Proof. Let T ∗ = L(OPT, I) denote OPT’s completion time. We first establish the bound on event G, when the population estimates and fast-channel executions satisfy their high-probability guarantees. We consider two cases, depending on when OPT finishes. Case 1: OPT finishes before the time cutoff. Suppose T ∗ < τtime . By Lemma 9, RACE has either completed all packets or entered permanent slow-channel cleanup by time T ∗ . Since the time cutoff has not been reached, cleanup must have been triggered by the population cutoff. On event G, the number r of remaining active packets satisfies: b cur ≤ τpop = O(n/ρ). r≤n

By Lemma 10, the expected time needed to finish these packets on the slow channel is O(n/ρ). Since OPT requires at least Ω(n/ρ) slots to transmit all n packets, RACE’s expected latency in this case is O(T ∗ ). Case 2: OPT finishes at or after the time cutoff. Suppose T ∗ ≥ τtime . On event G, the initial b ≤ 32n, so: estimate satisfies n ≤ n T ∗ ≥ τtime ≥ n/128. Thus T ∗ = Ω(n). Lemma 11 guarantees that RACE completes all packets or enters permanent slow-channel cleanup within O(n) slots. By Lemma 10, finishing any remaining packets takes another O(n) expected slots. Therefore, RACE’s expected latency is again O(T ∗ ). Executions in which the guarantees fail. It remains to account for executions outside event G. Recall that G0 concerns the accuracy and running time of the initial population estimate, while G also includes the guarantees for subsequent estimates and fast rounds. If G0 holds but G fails, Lemmas 7 and 11 show that this event has probability O(n−D ) and that RACE’s expected latency is bounded by O(n), even when these guarantees fail. Its contribution to the overall expectation is therefore O(n1−D ). b ). By Lemma 17, If G0 fails, Lemma 11 bounds the expected latency by τ0 + O(n + n −D b from these executions are each O(n ), while the fixed n term the contributions of τ0 and n contributes O(n Pr(¬G0 )) = O(n1−D ). Thus, these executions also contribute at most O(n1−D ) to expected latency. These contributions are negligible compared with T ∗ = Ω(n/ρ). Combining them with the bounds established on G gives E[L(RACE, I)] = O(T ∗ ), as claimed.

A.7

Switching Cost

On event G, RACE begins no new fast rounds after OPT finishes at time T ∗ . However, a round that began before T ∗ may finish afterward, potentially incurring additional costs when unsuccessful packets return to the slow channel. Our analysis needs to include these costs. The following lemma establishes that OPT cannot ignore more than two iterations in which it could have used the fast channel before finishing. This allows us to bound the number of iterations in which RACE may incur eviction costs in terms of the number of iterations actually used by OPT. Lemma 12. Let M be the number of iterations containing a slow-slot boundary before T ∗ at which packets could enter the fast channel. If OPT successfully transmits packets on the fast channel in m iterations, then M ≤ m + 2. Proof. For each integer t, let C(t) denote the total number of transmission opportunities available to OPT before time t. This includes one opportunity per slow-channel slot, even during eviction periods, and one per fast mini-slot beginning at the first slow-slot boundary in each iteration when packets can enter the fast channel. Since all packets are present initially, OPT can use 31

these opportunities to transmit distinct packets without collisions, assigning packets to the fast channel at the first permitted boundary of each iteration. Consequently, T ∗ is the smallest integer t for which C(t) ≥ n. Since C(T ∗ − 1) ≤ n − 1 and one slow slot adds at most ρ + 1 opportunities, 0 ≤ C(T ∗ ) − n ≤ ρ. Every iteration that ends before T ∗ provides at least ρ usable fast-channel transmission opportunities. Since OPT can leave at most ρ opportunities unused by time T ∗ , it cannot ignore two such iterations without contradicting the preceding bound. At most one additional iteration can still be underway at T ∗ . Consequently, M ≤ m + 2 for any minimum-latency schedule. √ Lemma 13. On event G, for m ≥ 1, RACE executes at most O(mρ + mn) fast rounds. The total switching cost from admitting these batches and returning packets evicted before their √ scheduled deadlines is also O(mρ + mn). Proof. Recall that M counts the iterations in which packets could enter the fast channel before T ∗ . By Lemma 9, every fast round begins before T ∗ . Each aborted round begins during an iteration that ends with the eviction responsible for its abort. No two aborted rounds can begin in the same iteration, since the eviction interrupting the first round ends that iteration before another round can begin. This remains true even if the eviction or its report occurs after T ∗ . Thus, the number J of aborted rounds satisfies J ≤ M ≤ m + 2. Each reported abort resets b to zero, whereas a new population estimate leaves b unchanged. Let t1 , . . . , tJ+1 denote the numbers of certified rounds before the first reported abort, between successive reported aborts, and after the last reported abort, respectively. Since the population cap is inactive on G, the intended number of packets per subchannel in each such sequence increases through ρ, ρ + 1, . . . , ρ + ti − 1. On G, these certified rounds complete at least αλx packets each, where x is the intended number of packets per subchannel. Since J aborted rounds divide the execution into at most J + 1 sequences of certified rounds, Cauchy–Schwarz gives the following bound on their total number: s X αλ X 2 2(J + 1)n ti ≤ ti ≤ n, . 2 i αλ i There are at most i ti + J + 1 fast rounds in total, including a possible final round in which all remaining packets succeed before its outcome is recorded. Each round incurs one batch-admission cost. An aborted round ending the i-th sequence has intended per-subchannel batch size ρ + ti . On G, at most 2λ(ρ + ti ) packets participate in that round and can therefore be returned by its eviction. A round in which the last packet succeeds during reporting is included among the aborted rounds. P The total cost of moving batches onto the fast channel is at most i ti + J + 1, since each round incurs one unit of cost. The cost of returning packets evicted before their scheduled P deadlines is at most 2λJρ + 2λ i ti . Combining these bounds gives: P

!

O λ(J + 1)ρ + λ

X

ti



= O λ(J + 1)ρ +

q



λ(J + 1)n .

i

The equality follows from the preceding bound on √ m ≥ 1, the total is O(mρ + mn).

i ti . Since J ≤ m + 2, λ is constant, and

P

Lemma 14. For a fixed instance with m ≥ 1, let Cret denote the total cost of returning packets that remain on the fast channel at the scheduled end of a round’s TSTB execution. Then: √ E[Cret | G] Pr(G) = O(mρ + mn). 32

√ Proof. By Lemma 13, on event G, the number of fast rounds is at most Amax = O(mρ + mn), where Amax is a fixed upper bound. We consider the fast rounds in the order they begin. For each j ≤ Amax , let Rj denote the number of packets that return to the slow channel at the scheduled end of the j-th round, b cur active packets. Otherwise, including when the j-th provided that round begins with at most n round does not occur, we set Rj = 0. b cur active packets. By Lemma 1, the expected Consider any round that begins with at most n number of packets remaining unsuccessful after its full scheduled TSTB execution, assuming no eviction, is O(1) per logical subchannel, or O(λ) across all subchannels. If an eviction occurs before the scheduled end of the round, unfinished packets return at the time of eviction rather than at the scheduled end. Their switching costs are accounted for in Lemma 13. Otherwise, the number returning at the scheduled end is bounded by the number that would remain unsuccessful after the full TSTB execution. Consequently, the expected number of packets returning at the scheduled end of any such round is O(λ). This bound holds regardless of the outcomes of earlier rounds, since each round uses fresh independent random choices. In particular, E[Rj ] = O(λ) for every j ≤ Amax . b cur active packets, and there are at most On event G, every fast round begins with at most n Amax rounds. Therefore: E[Cret | G] Pr(G) ≤

AX max

E[Rj ]

j=1

≤ O(λAmax ) √ = O(mρ + mn), where the last equality uses the fact that λ is constant. Proposition 2. For m ≥ 1, the expected switching cost of RACE satisfies: √ E[Cost(RACE, I)] = O(mρ + mn), and its switching-cost competitive ratio is: q E[Cost(RACE, I)] = O ρ + n/m . Cost(OPT, I) 



For m = 0, RACE incurs zero switching cost on G0 . Moreover, by choosing the estimator’s confidence constant sufficiently large, its expected switching cost can be made polynomially small in n. Proof. First suppose m ≥ 1. On event G, Lemma 13 bounds the cost of moving batches onto the fast channel and returning packets evicted before their scheduled fast-channel executions finish. Lemma 14 bounds the expected cost of returning packets that remain unsuccessful at the scheduled end of these executions. Together, these lemmas account for all switching costs, including those incurred by rounds that begin before T ∗ but finish afterward. Consequently, on √ G, the expected switching cost is O(mρ + mn). We must also account for executions in which G fails. When G0 holds but G does not, b ) = O(n2 ). Lemma 7 guarantees that these Lemma 11 bounds the switching cost by O(nn executions occur with sufficiently small probability that their contribution to the expected b ), switching cost is negligible. When G0 fails, Lemma 11 again bounds the switching cost by O(nn while Lemma 17 guarantees that the expected contribution of these executions is also negligible. Since the constants in the estimator can be chosen to make these contributions polynomially √ small in n, the overall expected switching cost remains O(mρ + mn). To obtain the competitive ratio, recall that all packets are initially on the slow channel. In each of the m iterations in which OPT successfully transmits packets on the fast channel, it 33

must move at least one batch onto that channel, incurring at least one unit of switching cost. Therefore, Cost(OPT, I) ≥ m, and the claimed competitive ratio follows. Now suppose m = 0. Since OPT never successfully transmits on the fast channel, its minimum completion time is T ∗ = n, achieved by transmitting all packets on the slow channel. Moreover, the fast channel cannot be available at any slow-slot boundary t ≤ n − 2. Otherwise, OPT could complete one packet on the fast channel and the remaining n − 1 packets on the slow channel, finishing by time n − 1. This would contradict the minimum completion time T ∗ = n. b ≤ 32n, so the time cutoff satisfies τtime ≤ n/2 ≤ n − 1. On G0 , the initial estimate satisfies n Since RACE can begin a fast round only at a slow-slot boundary before this cutoff, and the fast channel is unavailable at every such boundary, no fast round can begin. Thus, RACE remains on the slow channel and incurs zero switching cost on G0 . b ), while Lemma 17 Finally, Lemma 11 bounds the switching cost on every execution by O(nn guarantees that executions outside G0 contribute a polynomially small amount to its expected value. This establishes the claimed expected switching cost when m = 0. No switching-cost competitive ratio is asserted in this case, since OPT incurs zero switching cost. If the fast channel is never available, RACE also incurs zero switching cost on every execution. Proof of Theorem 1. As described in Section 3.2, RACE is decentralized: packets use common channel feedback and synchronized slot boundaries to coordinate their actions without centralized control. Proposition 1 establishes that RACE achieves expected latency O(T ∗ ), while Proposition 2 establishes the claimed switching-cost bound. Finally, population estimation, slowchannel contention resolution, eviction reporting, and cleanup all use at most one slow-channel transmission opportunity per slot. Thus, resource augmentation is required only on the fast channel.

B

Lower Bounds

Our lower bounds hold even when the online algorithm is given constant-factor resource augmentation on both the slow and fast channels (in contrast, our upper bound assumes augmentation only on the fast channel). We establish each bound by constructing an eviction schedule that forces substantial switching cost on any randomized online algorithm achieving constant-competitive expected latency.

B.1

Switching-Cost Ratio

To prove Theorem 2(A), let c ≥ 1 be the constant in the assumed expected-latency guarantee, and let λs and λf denote the fixed augmentation factors on the slow and fast channels. We construct a distribution over eviction schedules and first establish a switching-cost lower bound for deterministic algorithms that finish the no-eviction instance quickly. We then extend the result to randomized algorithms. Let: L = ⌈n/ρ⌉ + 1, K0 = ⌈4cL⌉. Thus, K0 = Θ(n/ρ). Choose a fixed integer h0 ≥ Cavail , and consider the set of times: T = {u + j/ρ : h0 ≤ u < K0 , 1 ≤ j < ρ} . Each time in T is a fast-channel mini-slot boundary strictly inside a slow-channel slot. An eviction beginning at any such time is permitted, because the fast channel has already been available for at least Cavail slots. There are K0 − h0 slow-channel slots between h0 and K0 , each containing ρ − 1 such boundaries. Consequently: |T | = (K0 − h0 )(ρ − 1) = Θ(n/ρ) · Θ(ρ) = Θ(n). 34

We define a probability distribution µ over eviction schedules. With probability 1/2, the fast channel remains available throughout the execution; call this instance I0 . Otherwise, a time t is chosen uniformly from T , and the only eviction occupies the single fast mini-slot [t, t + 1/ρ); call this instance It . We write EI∼µ for expectation over the choice of an instance from this distribution. OPT knows the eviction schedule and can ensure that all packets assigned to the fast channel succeed before an eviction. After the one-mini-slot eviction, OPT may have to wait until the next slow-slot boundary before assigning another batch to the fast channel, losing at most one slow slot of fast-channel capacity. OPT can therefore finish within L slots, using at most two batches on the fast channel and incurring switching cost O(1). Moreover, a schedule achieving minimum latency can be chosen with this switching cost: packets are assigned to the earliest usable slow- and fast-channel transmission slots, and each fast-channel batch enters at the first permitted slow-slot boundary of its availability interval. Lemma 15. For the distribution µ defined above, every deterministic online algorithm A that completes all packets on I0 within K0 slow-channel slots satisfies: √ EI∼µ [Cost(A, I)] = Ω( n). Proof. Fix such a deterministic algorithm A. By time K0 , it can complete at most λs K0 = o(n) packets on the slow channel, and at most λf ρh0 = o(n) packets on the fast channel before time h0 . Since it finishes all n packets on I0 by K0 , at least Ω(n) packets succeed on the fast channel between times h0 and K0 . We group these packets according to their last move onto the fast channel before succeeding. Packets whose last move occurred at or before h0 form one group, which begins at time h0 . For each batch moved onto the fast channel after h0 , the packets for which that batch was their last move form another group, beginning when the batch enters the fast channel. Only packets that succeed on the fast channel during [h0 , K0 ) are included. Let s1 , . . . , sg be the sizes of the nonempty groups. Then: S=

g X

si = Ω(n).

i=1

Each group other than the possible initial group corresponds to a distinct batch moved onto the fast channel, and a nonempty initial group requires at least one earlier batch. Thus, the switching cost on I0 is at least g. If g ≥ S/(8λf ), the cost of moving these batches onto the fast channel is already Ω(n), which proves a stronger bound. Otherwise g < S/8λf . The groups with fewer than 4λf packets account for fewer than 4λf g < S/2 packets. Therefore, “larger” groups with si ≥ 4λf together contain at least S/2 = Ω(n) packets. Consider one of these larger groups. By the definition of the groups, its si packets remain on the fast channel from the group’s starting time until they succeed. The augmented fast channel can complete at most λf packets per mini-slot. Hence, during the first ⌊si /(2λf )⌋ mini-slot boundaries after the group begins, at least si /2 packets from the group remain on the fast channel. Recall that each group contains only packets that successfully transmit on the fast channel before time K0 . Consequently, the mini-slot boundaries under consideration must occur before K0 , since transmitting all si packets requires at least si /λf mini-slots. At least half of these boundaries lie strictly inside slow-channel slots and therefore belong to T . Since at least si /2 packets from the group remain on the fast channel at each of these times, the sum of the number of packets exposed to eviction over these times is at least: s2i Ω λf

!

= Ω(s2i ). 35

For each t ∈ T , let xt be the number of packets on the fast channel at time t in the execution of A on I0 , after any transmissions ending at t have completed. Summing over the larger groups gives:   X

xt ≥ Ω 

X

s2i  .

i:si ≥4λf

t∈T

Recall that the groups with si ≥ 4λf together contain at least S/2 = Ω(n) packets. By Cauchy– Schwarz, the square of the sum of their sizes is at most the number of these groups multiplied by the sum of their squared sizes. Since there are at most g such groups, we have: 2

 X

X

si  ≤ g

 i:si ≥4λf

s2i .

i:si ≥4λf

Rearranging, and using the fact that the sum on the left is Ω(n), gives: P X

s2i ≥

i:si ≥4λf

Therefore:

X

i:si ≥4λf si

g

2

= Ω(n2 /g).

xt = Ω(n2 /g).

t∈T

On instance It , the execution agrees with the execution on I0 until time t. Because t lies strictly inside a slow-channel slot, no new packet can move onto the fast channel at that time. The eviction therefore forces all xt packets then on the fast channel to return to the slow channel. The distribution µ assigns probability 1/2 to I0 and probability 1/(2|T |) to each It . Combining the cost of moving batches onto the fast channel on I0 with the expected eviction cost gives: EI∼µ [Cost(A, I)] ≥

g 1 X + xt 2 2|T | t∈T

≥ Ω(g) + Ω(n/g) √ = Ω( n), where |T | = Θ(n). If g ≥ S/(8λf ), the same conclusion follows directly from the switching cost on I0 . Thus the lemma holds in both cases. The preceding argument resembles Yao’s minimax principle, but requires an additional step because we consider randomized algorithms that are constant-competitive in expected latency. A randomized algorithm can be viewed as a distribution over deterministic algorithms, some of which may not be latency-competitive even when the randomized algorithm is competitive in expected latency. Consequently, a switching-cost lower bound proved only for latencycompetitive deterministic algorithms would not necessarily extend to randomized algorithms whose distributions include deterministic algorithms that are not latency-competitive. To avoid this difficulty, our deterministic lower bound requires only that the algorithm finish the no-eviction instance I0 within K0 = O(n/ρ) slots. As we show next, Markov’s inequality guarantees that, for any randomized algorithm satisfying our expected-latency requirement, a constant fraction of its probability distribution is over deterministic algorithms that finish I0 within K0 slots. We can then apply the deterministic lower bound to those algorithms and average to obtain the desired result. Lemma 16. For the distribution µ, every randomized online algorithm R that is c-competitive √ in expected latency incurs expected switching cost Ω( n), where the expectation is over both the algorithm’s random choices and the eviction schedule drawn from µ. 36

Proof. Since OPT finishes the no-eviction instance I0 within L slow-channel slots and R is c-competitive in expected latency, we have: E[L(R, I0 )] ≤ cL(OPT, I0 ) ≤ cL. Recall that K0 = ⌈4cL⌉. By Markov’s inequality, the probability that R takes more than K0 slots to finish I0 is at most: Pr L(R, I0 ) > K0 ≤

cL E[L(R, I0 )] 1 ≤ = . K0 4cL 4

Therefore, with probability at least 3/4 over the random choices of R, the algorithm finishes I0 within K0 slots. Recall that a randomized algorithm can be viewed as a distribution over deterministic algorithms. For each choice of randomness that results in completion within K0 slots, Lemma 15 √ guarantees expected switching cost Ω( n) when the eviction schedule is drawn from µ. These choices account for at least 3/4 of the probability distribution over deterministic algorithms. Since switching costs are nonnegative for all other choices, averaging over the random √ choices of R and the eviction schedules drawn from µ gives expected switching cost Ω( n), as claimed. Proof of Theorem 2(A). By Lemma 16, the average expected switching cost of R over the finitely √ many instances in µ is Ω( n). Thus, some fixed instance in this distribution gives expected √ switching cost Ω( n). As established above, OPT achieves minimum latency with switching cost O(1) on every instance in the distribution. Hence this fixed instance gives an expected √ switching-cost competitive ratio Ω( n), as claimed.

B.2

A Rate-Dependent Switching-Cost Lower Bound

The key idea behind the proof below is that an algorithm with constant-competitive expected latency must finish in O(n/ρ) slots with constant probability when the fast channel is continuously available. Since the slow channel can complete only o(n) packets in that time, most packets must finish on the fast channel. Because packets can enter the fast channel only at slow-slot boundaries, this requires Ω(ρ) packets to remain on the fast channel after the first mini-slot in a constant fraction of slow slots. An eviction at a randomly chosen such time therefore incurs expected cost Ω(ρ). Since OPT can achieve minimum latency with unit switching cost on every instance in the construction, an averaging argument yields a fixed eviction schedule with expected switching-cost competitive ratio Ω(ρ). Proof of Theorem 2(B). Fix a randomized online algorithm R that is c-competitive in expected latency. Let λs and λf be its fixed augmentation factors on the slow and fast channels, respectively. Choose a fixed integer h0 ≥ Cavail , and let: L = ⌈n/(ρ + 1)⌉,

K0 = ⌈4cL⌉.

On the instance I0 , where the fast channel is always available, OPT finishes within L slots. As in the preceding lower bound, Markov’s inequality implies that R finishes I0 within K0 slots with probability at least 3/4. We fix any choice of the algorithm’s random decisions for which this occurs and consider the resulting deterministic execution. For each integer u ∈ {h0 , . . . , K0 −1}, consider an eviction beginning at time u+1/ρ, just after the first mini-slot of slow-channel slot u ends. The fast channel remains unavailable thereafter. Let Iu denote the resulting instance. Each such eviction is permitted because the fast channel has been available for at least Cavail slots. On every instance Iu , OPT can achieve minimum latency with switching cost exactly one. Indeed, any minimum-latency schedule can be modified so that all packets that succeed on the 37

fast channel enter it together at time zero, while all other packets remain on the slow channel. Keeping only the original successful transmissions preserves their feasibility and completion times: all packets are present initially, and the fast channel is continuously available until the sole eviction. All fast-channel packets succeed before the eviction takes effect, including any transmission ending at the eviction boundary, so no packet returns to the slow channel. Furthermore, a schedule using only the slow channel requires n slots, whereas sending one packet in the first fast mini-slot and the other n − 1 packets on the slow channel finishes by time n − 1. Thus, every minimum-latency schedule uses the fast channel. Choosing a minimum-switching schedule among the minimum-latency schedules therefore gives Cost(OPT, Iu ) = 1. Let qu be the number of packets remaining on the fast channel immediately after that first mini-slot in the execution on I0 . We will show that qu = Ω(ρ) for a constant fraction of the slow-channel slots under consideration. Let H denote the set of slow-channel slots in which at least aρ packets remain on the fast channel immediately after the first mini-slot, where a > 0 is a sufficiently small fixed constant. That is: H = {u ∈ {h0 , . . . , K0 − 1} : qu ≥ aρ}. Consider a slow-channel slot u ∈ / H with u ≥ h0 . At most λf packets can succeed during its first fast mini-slot. Since packets can move onto the fast channel only at slow-slot boundaries, no additional packets can enter the fast channel during the remainder of that slot. Since qu < aρ, at most another aρ packets can succeed on the fast channel during this slot. Thus, such a slot contributes at most λf + aρ fast-channel successes. For slots in H, we use the upper bound of λf ρ successful fast-channel transmissions. We now count the successful transmissions by time K0 . The slow channel completes at most λs K0 packets. On the fast channel, the first h0 slots contribute at most h0 λf ρ successes, the |H| slots in H contribute at most |H|λf ρ, and the remaining K0 − h0 − |H| slots contribute at most (K0 − h0 − |H|)(λf + aρ). Since all n packets succeed by K0 , we obtain: n ≤ λs K0 + h0 λf ρ + |H|λf ρ + (K0 − h0 − |H|)(λf + aρ). In particular:

n ≤ λs K0 + h0 λf ρ + |H|λf ρ + K0 (λf + aρ). √ Recall that K0 = Θ(n/ρ). Since ρ = Ω(log n) and ρ = O( n), and since h0 , λs , and λf are constants, the terms λs K0 , h0 λf ρ, and λf K0 are all o(n). We choose a sufficiently small that K0 aρ ≤ n/4 for sufficiently large n. Therefore, |H|λf ρ = Ω(n), which implies: |H| = Ω(n/ρ) = Ω(K0 ). Thus, during a constant fraction of the slow-channel slots between h0 and K0 , at least aρ packets remain on the fast channel immediately after the first mini-slot. Now consider the execution on Iu for some u ∈ H. Since the eviction occurs immediately after the first fast mini-slot, the execution on Iu agrees with that on I0 up to that time. In particular, the same packets are on the fast channel when the eviction occurs. Since qu ≥ aρ, the eviction forces at least aρ packets to return to the slow channel. Suppose we choose u uniformly at random from {h0 , . . . , K0 − 1}. Because H contains a constant fraction of these choices, the expected eviction cost is Ω(ρ) for every fixed choice of the algorithm’s random decisions that finishes I0 within K0 slots. As established above, such choices of the algorithm’s randomness occur with probability at least 3/4. Averaging over all random choices therefore gives expected eviction cost Ω(ρ), where the expectation is over both the algorithm’s randomness and the uniformly chosen eviction time. Since the average expected eviction cost over the candidate schedules is Ω(ρ), at least one fixed schedule Iu must incur expected eviction cost Ω(ρ), and hence expected switching cost 38

Ω(ρ), where the expectation is only over the random choices of R. Since Cost(OPT, Iu ) = 1, this fixed instance satisfies: E[Cost(R, Iu )] = Ω(ρ), Cost(OPT, Iu ) which proves the claimed competitive-ratio lower bound.

C

Estimation of n

We treat population estimation as a modular subroutine: the analysis of RACE relies only on the properties established in Lemmas 17 and 18, rather than on a particular estimation procedure. This section establishes these properties for our estimator. Although geometric techniques for estimating population size are well established [43], our analysis must also account for packet departures and the effect of rare estimation failures on expected costs.

C.1

Population Estimation in RACE

Whenever RACE invokes Estimate, all active packets participate simultaneously on the slow channel, using independent random choices. Packets that successfully transmit during estimation complete their transmissions and leave the system. The packets remaining when estimation finishes receive the same estimate at a common slow-slot boundary. The initial estimation requires no prior bound on the population and terminates almost surely. b to determine the range of population sizes to Subsequent estimations use the initial estimate n consider. Estimation proceeds on the slow channel even when the fast channel becomes available. However, if RACE reaches its time cutoff during a subsequent estimation, the procedure is interrupted and cleanup begins.

C.2

Estimation Procedure and Guarantees

The estimator determines the approximate number of active packets by observing how frequently the slow channel is empty. When packets transmit with relatively high probability, most slots are nonempty. As their transmission probability decreases, empty slots become more frequent. The estimator uses this relationship to identify an approximate population size. Specifically, the estimator tests a sequence of possible population sizes, called scales. At scale v, each active packet independently transmits with probability 1/v in each of a prescribed number of slow-channel slots, called test slots. A scale passes if at least half of its test slots are empty. Since all active packets observe the same ternary feedback, those remaining agree on which scale first passes and therefore on the resulting estimate. Initial estimation. The estimator tests scales vj = 2j , for j = 0, 1, . . .. At each scale j, it uses: hj = 2 ⌈C(j + 1)/2⌉ test slots, where C is a sufficiently large constant. The estimator accepts the first passing scale b = 4vj , setting n b cur = n b. and returns n If all packets finish during estimation, no estimate is needed. For purposes of analysis, we treat the remaining test slots at that scale as empty, so that an estimate is defined even if all packets have finished. b ≤ 32n and is Recall that G0 is the event that the initial population estimate satisfies n ≤ n obtained in O(log2 n) slow slots. Lemma 17. The initial call to Estimate terminates almost surely.1 Let τ0 be its duration measured in slow slots. For any fixed D > 0, a sufficiently large choice of C gives an event 1 This means termination occurs with probability one, even though there is no deterministic upper bound on its running time.

39

b ≤ 32n in G0 with probability at least 1 − O(n−D ) on which the call returns an estimate n ≤ n O(log2 n) slow slots. Since at most one packet succeeds per slow slot, this running-time bound implies that at least n/2 packets remain active on G0 , for sufficiently large n. The estimate is therefore also within a factor of 64 of the number of packets remaining. Executions outside G0 contribute negligibly to the expected estimate and the expected running b | ¬G0 ] Pr(¬G0 ) = O(n−D ) and E[τ0 | ¬G0 ] Pr(¬G0 ) = O(n−D ). time; specifically, E[n

Proof. We first bound the probability that the estimator accepts a scale that is too small. The total number of test slots at scales v ≤ 8n is O(log2 n) = o(n). Since at most one packet succeeds per test slot, at least n/2 packets remain active throughout these scales, for sufficiently large n. At a scale v = 2j < n/4, the probability that a test slot is empty is at most e−n/(2v) , regardless of the preceding test outcomes. For the scale to pass, at least hj /2 test slots must be empty. Taking a union bound over the possible choices of these slots gives: Pr(scale j passes | scale j is reached) ≤ 2hj e−hj n/(4v) ≤ e−hj n/(16v) . The last inequality holds because n/v ≥ 4. Since hj ≥ C(j + 1) and (j + 1)n/2j = Ω(log n) throughout this range, choosing C sufficiently large makes the probability that any such scale passes smaller than any prescribed inverse polynomial in n. We next bound the probability that the estimator continues testing scales that are too large. Let j∗ be the first index satisfying 2j∗ ≥ 4n. At any scale j ≥ j∗ , at most n packets remain active, so the probability that a test slot is nonempty is at most n/2j ≤ 1/4. This bound holds regardless of the preceding test outcomes. Thus, the number of nonempty slots satisfies the same Chernoff upper bound as hj independent tests, each nonempty with probability 1/4. A scale fails only if more than half its test slots are nonempty, so its failure probability is e−Ω(hj ) . Applying these bounds successively, without assuming independence between scales, gives: Pr(reach scale j∗ + t) ≤ exp −Ω(C(t log n + t2 ))

for t ≥ 1. The implicit constant in the exponent is independent of C. Since this bound tends to zero as t increases, the initial estimation procedure terminates almost surely. Let G0 be the event that the first passing scale is at least n/4 and has index at most j∗ . The preceding bounds give Pr(¬G0 ) = O(n−D ) for sufficiently large C. On G0 , the returned estimate b ≤ 32n, and estimation takes O(log2 n) slow slots. At most this many packets can satisfies n ≤ n succeed during estimation. Hence, for sufficiently large n, at least n/2 packets remain active, b is between the remaining population and 64 times that population. and n It remains to bound the contributions from executions outside G0 . If the first passing scale b < n and τ0 = O(log2 n). The probability of this event can be made satisfies v < n/4, then n sufficiently small that its contribution to both the expected estimate and expected running time is O(n−D ). The remaining possibility is that the first passing scale has index j∗ + t for some t ≥ 1. The corresponding estimate and running time satisfy: b = O(n2t ), n

τ0 = O((log n + t)2 ).

The probability that this scale is the first to pass is at most the probability of reaching it. Therefore, the contributions from these executions to the expected estimate and running time are bounded, respectively, by: X

O(n2t ) exp −Ω(C(t log n + t2 )) = O(n−D ),

t≥1

X t≥1

O((log n + t)2 ) exp −Ω(C(t log n + t2 )) = O(n−D ).

40

These bounds hold for sufficiently large C because the probability of reaching increasingly large scales decreases rapidly enough to outweigh the growth in the estimate and running time. Together with the bounds for scales smaller than n/4, this completes the proof. Subsequent Estimations. After the initial estimation, the estimator uses the common estimate b to determine the range of scales to test: n v = 1, 2, 4, . . . , 2⌈log2 (4bn)⌉ . At each scale, it uses:

b )/2⌉ h = 2 ⌈CD log(n

test slots, where CD is a sufficiently large constant. The estimator accepts the first passing scale. If no scale passes, it selects the last scale tested. b cur is the smaller of the selected scale and n b . Thus, every In either case, the returned estimate n b , regardless of whether the initial estimate completed estimation returns a value between 1 and n was accurate. b) b ≥ 4, each subsequent estimation procedure uses at most τest (n b ) = O(log2 n Lemma 18. For n slow slots. If it finishes before the time cutoff and packets remain active, they all receive the same b . These guarantees hold even if the initial estimate is inaccurate. integer estimate between 1 and n b ≥ n and at least 2τest (n b ) packets are active when estimation begins. For any Suppose n b −D , any fixed D > 0, a sufficiently large choice of CD ensures that, except with probability n b cur ≤ 16s, where s is the number of packets estimate returned before the time cutoff satisfies s ≤ n remaining active when estimation finishes. b ) scales, each using O(log n b ) test slots, giving the stated Proof. The estimator tests O(log n running-time bound. All packets that remain active observe the same test outcomes and therefore b guarantees that it lies between 1 return the same estimate. The rule limiting that estimate to n b and n, even if the initial estimate is inaccurate. b ≥ n and establish the accuracy guarantee. It suffices to analyze the We now assume n estimation procedure without interruption: any estimate returned before the time cutoff is unchanged by this assumption. Let r and s be the numbers of active packets when estimation b −D , the estimate begins and ends, respectively. We first show that, except with probability n b cur ≤ 8r. satisfies s ≤ n Consider a tested scale v. While at least v packets remain active, the probability that the next test slot is nonempty is at least 1 − 1/e > 5/8, regardless of earlier outcomes. For this probability calculation only, once fewer than v packets remain, count every remaining test slot at that scale as nonempty. The resulting sequence satisfies the same Chernoff lower-tail bound as h independent tests, each nonempty with probability 5/8. Thus, the probability that at most half of these slots are nonempty is e−Ω(h) . If s > v, the number of active packets never falls below v, so this counting rule does not change any outcome. Consequently, the probability that scale v passes even though more than v packets remain at the end is at most e−Ω(h) . Next, consider the first power of two v ≥ 4r. It satisfies v < 8r and is among the tested b ≥ n ≥ r. At most r packets are active during its test slots, so each slot is scales because n nonempty with probability at most r/v ≤ 1/4, regardless of earlier outcomes. A standard Chernoff upper-tail bound shows that, if this scale is reached, it fails to pass with probability at most e−Ω(h) . b ) scales. A union bound over scales that pass despite being smaller than s, There are O(log n together with the possible failure at the first scale at least 4r, gives total failure probability at most: b )e−Ω(h) ≤ n b −D , O(log n

41

b . Outside these failures, the first passing scale lies for sufficiently large CD , since h ≥ CD log n b preserves these bounds because n b ≥ n ≥ s. between s and 8r. Limiting the returned value to n Finally, at most one packet succeeds per test slot. Under the lemma’s assumption that b ), we therefore have: r ≥ 2τest (n b ) ≥ r/2. s ≥ r − τest (n b cur ≤ 8r ≤ 16s, as required. Combining this with the preceding accuracy bound gives s ≤ n

42

Related documents

• Static and dynamic jamming games over wireless channels with mobile strategic players#987354
• A Fundamental Inequality for Lower-bounding the Error Probability for Classical and Quantum Multiple Access Channels and Its Applications#1186286
• Information-Theoretic Foundations of Mismatched Decoding#1051929
• Transmission Strategies for Wireless Multi-user, Multiple-Input, Multiple-Output Communication Channels#640209
• Learning to Interfere in Non-Orthogonal Multiple-Access Joint Source-Channel Coding#1414517