Stochastic Contention Resolution With Short Delays

DOI10.1137/S0097539795285333zbMath0914.68103MaRDI QIDQ4210173

Eli Upfal, Prabhakar Raghavan

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmsstochastic analysiscontention resolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Related Items (15)

Packet latency of deterministic broadcasting in adversarial multiple access channels ⋮ Performing work in broadcast networks ⋮ Sade: competitive MAC under adversarial SINR ⋮ Maximum throughput of multiple access channels in adversarial environments ⋮ Consensus and collision detectors in radio networks ⋮ Competitive throughput in multi-hop wireless networks despite adaptive jamming ⋮ Adversarial multiple access channels with individual injection rates ⋮ Thinning protocols for routing \(h\)-relations over shared media ⋮ Analysis of randomized protocols for conflict-free distributed access ⋮ Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses ⋮ Local queuing under contention ⋮ Singletons for simpletons revisiting windowed backoff with Chernoff bounds ⋮ Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel ⋮ Broadcasting in ad hoc multiple access channels ⋮ Broadcasting in Ad Hoc Multiple Access Channels

Cites Work

• Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
• Analysis of Backoff Protocols for Multiple Access Channels
• On contention resolution protocols and associated probabilistic phenomena
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Stochastic Contention Resolution With Short Delays