Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses

DOI10.1137/17M1158604zbMath1400.68258OpenAlexW2895046933WikidataQ129143109 ScholiaQ129143109MaRDI QIDQ4687247

Seth Pettie, Tsvi Kopelowitz, Maxwell Young, Michael A. Bender

Publication date: 11 October 2018

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

Full work available at URL: https://doi.org/10.1137/17m1158604

zbMATH Keywords

algorithmsdistributed computingwireless networksthroughputcontention resolutionadversarial scheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Network protocols (68M12) Distributed algorithms (68W15)

Related Items (3)

Node and edge averaged complexities of local graph problems ⋮ Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks ⋮ Windowed backoff algorithms for WiFi: theory and performance under batched arrivals

Cites Work

• Unnamed Item
• Unbounded contention resolution in multiple-access channels
• Scalable wake-up of multi-channel single-hop radio networks
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Analysis of practical backoff protocols for contention resolution with multiple servers
• Sade: competitive MAC under adversarial SINR
• The computational power of beeps
• Contention resolution in a non-synchronized multiple access channel
• Adversarial multiple access channels with individual injection rates
• The Cost of Synchronizing Multiple-Access Channels
• Approximating the Size of a Radio Network in Beeping Model
• Competitive and fair throughput for co-existing networks under adversarial interference
• A jamming-resistant MAC protocol for single-hop wireless networks
• Multiple-Choice Balanced Allocation in (Almost) Parallel
• Adversarial Queuing on the Multiple Access Channel
• How asymmetry helps load balancing
• Deploying Wireless Networks with Beeps
• A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks
• Wireless Communication Is in APX
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
• Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
• Stochastic Contention Resolution With Short Delays
• Balanced Allocations
• Randomization helps to perform independent tasks reliably
• How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
• Study of the Effect of the Wireless Gateway on Incoming Self-Similar Traffic
• Analysis of Backoff Protocols for Multiple Access Channels
• Exponential separations in the energy complexity of leader election
• SINR diagrams
• Contention resolution with log-logstar channel accesses
• Contention Resolution on a Fading Channel
• Asynchronous Shared Channel
• The Wake‐Up Problem in MultiHop Radio Networks
• Contention Resolution with Heterogeneous Job Sizes
• Balanced Allocations: The Heavily Loaded Case
• Contention resolution with constant expected delay
• Radio Network Lower Bounds Made Easy
• Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel
• A better wake-up in radio networks
• Automata, Languages and Programming

This page was built for publication: Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses