Analysis of Backoff Protocols for Multiple Access Channels

DOI10.1137/S0097539792233828zbMath0857.60064MaRDI QIDQ4895829

Leighton, Tom, Brian Rogoff, Johan T. Håstad

Publication date: 3 March 1997

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

zbMATH Keywords

Markov chains; stochastic stability; Ethernet; backoff protocols

Mathematics Subject Classification ID

90B18: Communication networks in operations research

68M10: Network design and communication in computer systems

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

Related Items

Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses, Local queuing under contention, Coordination Problems in Ad Hoc Radio Networks, Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election, Restrained medium access control on adversarial shared channels, Competitive throughput in multi-hop wireless networks despite adaptive jamming, An excursion-theoretic approach to stability of discrete-time stochastic hybrid systems, Thinning protocols for routing \(h\)-relations over shared media, Faster deterministic wakeup in multiple access channels, Analysis of practical backoff protocols for contention resolution with multiple servers, Moment conditions for a sequence with negative drift to be uniformly bounded in \(L^r\), Packet latency of deterministic broadcasting in adversarial multiple access channels, Sade: competitive MAC under adversarial SINR, Singletons for simpletons revisiting windowed backoff with Chernoff bounds, Windowed backoff algorithms for WiFi: theory and performance under batched arrivals, Broadcasting in ad hoc multiple access channels, Performing work in broadcast networks, Maximum throughput of multiple access channels in adversarial environments, Consensus and collision detectors in radio networks, Adversarial multiple access channels with individual injection rates, Analysis of randomized protocols for conflict-free distributed access, Broadcasting in Ad Hoc Multiple Access Channels, The Distributed Wireless Gathering Problem, Stochastic Contention Resolution With Short Delays