Token traversal in ad hoc wireless networks via implicit carrier sensing

DOI10.1016/j.tcs.2019.09.016zbMath1437.68014MaRDI QIDQ5919418

Dariusz R. Kowalski, Tomasz Jurdziński, Michał Różański, Grzegorz Stachowiak

Publication date: 13 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.016

zbMATH Keywords

deterministic algorithms; lower bounds; randomized algorithms; wireless networks; ad hoc networks; broadcast; SINR; selectors; algorithmic carrier sensing; BTD trees; token traversal

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68M14: Distributed systems

68W20: Randomized algorithms

68W15: Distributed algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Distributed computing. 27th international symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings
• Information dissemination in unknown radio networks with large labels
• Scalable wake-up of multi-channel single-hop radio networks
• A lower bound for radio broadcast
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Broadcasting in UDG radio networks with unknown topology
• A Local Broadcast Layer for the SINR Network Model
• Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks
• Deterministic Distributed Data Aggregation under the SINR Model
• Broadcast in the Ad Hoc SINR Model
• Dynamic packet scheduling in wireless networks
• How Well Can Graphs Represent Wireless Interference?
• Beyond geometry
• On the impact of geometry on ad hoc communication in wireless networks
• Efficient Distributed Communication in Ad-Hoc Radio Networks
• Fast broadcasting and gossiping in radio networks
• The Topology of Wireless Communication
• Batched Point Location in SINR Diagrams via Algebraic Tools
• Nearly Optimal Local Broadcasting in the SINR Model with Feedback
• Distributed Contention Resolution in Wireless Networks
• Deterministic Communication in Radio Networks
• Time of Deterministic Broadcasting in Radio Networks with Local Knowledge
• Faster Deterministic Broadcasting in Ad Hoc Radio Networks
• Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks
• Distributed Online and Stochastic Queuing on a Multiple Access Channel
• Efficient Symmetry Breaking in Multi-Channel Radio Networks
• Lower bounds for the broadcast problem in mobile radio networks
• On selection problem in radio networks
• Optimal Two-Stage Algorithms for Group Testing Problems
• Distributed Deterministic Broadcasting in Wireless Networks of Weak Devices
• An Ω(D log(N/D)) lower bound for broadcast in radio networks
• On the effect of the deployment setting on broadcasting in Euclidean radio networks
• Broadcasting in undirected ad hoc radio networks