Design patterns in beeping algorithms: examples, emulation, and analysis

DOI10.1016/j.ic.2018.10.001zbMath1409.68039arXiv1607.02951OpenAlexW2962920082WikidataQ129043527 ScholiaQ129043527MaRDI QIDQ1633808

Akka Zemmari, John Michael Robson, Arnaud Casteigts, Yves Métivier

Publication date: 21 December 2018

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

colouringcollision detectionemulationdesign patterns2-hop colouringbeeping modelsdegree computation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Related Items (3)

Counting in one-hop beeping networks ⋮ Transmitting once to elect a leader on wireless networks ⋮ Noisy beeping networks

Cites Work

• Unnamed Item
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Leader election in ad hoc radio networks: a keen ear helps
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• An optimal bit complexity randomized distributed MIS algorithm
• About randomised distributed graph colouring and graph partition algorithms
• Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection
• Quasi-optimal energy-efficient leader election algorithms in radio networks
• Simple distributed \(\Delta+1\)-coloring of graphs
• The computational power of beeps
• Combinatorial algorithms for distributed graph coloring
• Beeping a maximal independent set
• Weighted sums of certain dependent random variables
• The Wakeup Problem in Synchronous Broadcast Systems
• Distributed graph coloring in a few rounds
• Anonymous networks
• What Is the Use of Collision Detection (in Wireless Networks)?
• Deploying Wireless Networks with Beeps
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Stone age distributed computing
• Feedback from nature
• Randomized broadcast in radio networks with collision detection
• Maximal independent sets in radio networks
• On the complexity of distributed graph coloring
• Distributed Computing
• The Wake‐Up Problem in MultiHop Radio Networks
• Models and approximation algorithms for channel assignment in radio networks

This page was built for publication: Design patterns in beeping algorithms: examples, emulation, and analysis