Unbounded contention resolution in multiple-access channels

DOI10.1007/978-3-642-24100-0_23MaRDI QIDQ3095329zbMATH OpenOpenAlexFDO

Authors Antonio Fernández Anta, Miguel A. Mosteiro, Jorge Ramón Muñoz

Publication date 28 October 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.0234

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)

Abstract: A frequent problem in settings where a unique resource must be shared among users is how to resolve the contention that arises when all of them must use it, but the resource allows only for one user each time. The application of efficient solutions for this problem spans a myriad of settings such as radio communication networks or databases. For the case where the number of users is unknown, recent work has yielded fruitful results for local area networks and radio networks, although either a (possibly loose) upper bound on the number of users needs to be known, or the solution is suboptimal, or it is only implicit or embedded in other problems, with bounds proved only asymptotically. In this paper, under the assumption that collision detection or information on the number of contenders is not available, we present a novel protocol for contention resolution in radio networks, and we recreate a protocol previously used for other problems, tailoring the constants for our needs. In contrast with previous work, both protocols are proved to be optimal up to a small constant factor and with high probability for big enough number of contenders. Additionally, the protocols are evaluated and contrasted with the previous work by extensive simulations. The evaluation shows that the complexity bounds obtained by the analysis are rather tight, and that both protocols proposed have small and predictable complexity for many system sizes (unlike previous proposals).

Recommendations

• Unbounded contention resolution in multiple-access channels
• CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS
• Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks
• Contention resolution on multiple channels with collision detection
• Contention resolution in a non-synchronized multiple access channel

Cites work

• scientific article; zbMATH DE number 3659453 (Why is no real title available?)
• scientific article; zbMATH DE number 1857647 (Why is no real title available?)
• scientific article; zbMATH DE number 2119730 (Why is no real title available?)
• A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
• CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• On selection problem in radio networks
• Probability and Computing
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)
• Sensor Network Gossiping or How to Break the Broadcast Lower Bound
• Tree algorithms for packet broadcast channels
• Unbounded contention resolution in multiple-access channels

Cited in

(12)

• Unbounded contention resolution in multiple-access channels
• Contention resolution on a fading channel
• A unified minimum-search method for resolving contentions in multiaccess networks with ternary feedback
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• Contention resolution in a non-synchronized multiple access channel
• Deterministic non-adaptive contention resolution on a shared channel
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS
• Contention Resolution in Multiple-Access Channels: k-Selection in Radio Networks
• Information exchange with collision detection on multiple channels
• Optimal Protocols for 2-Party Contention Resolution
• Contention resolution on multiple channels with collision detection

This page was built for publication: Unbounded contention resolution in multiple-access channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095329)