Beeping a deterministic time-optimal leader election

DOI10.4230/LIPICS.DISC.2018.20MaRDI QIDQ5090911zbMATH OpenFDO

Authors Fabien Dufoulon, J. Burman, J. Beauquier

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2018.20

zbMATH Keywords

beeping modeldeterministic algorithmsdistributed algorithmsleader electiontime complexitywireless networks

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Brief Announcement
• Brief announcement: Optimal leader election in multi-hop radio networks
• Communicating with beeps
• Deterministic leader election in O(D+ n) time with messages of size O(1)
• Exploiting spontaneous transmissions for broadcasting and leader election in radio networks

Cites work

• Analysis of fully distributed splitting and naming probabilistic procedures and applications
• Brief announcement: Optimal leader election in multi-hop radio networks
• Byzantine fireflies
• Communicating with beeps
• Deploying wireless networks with beeps
• Design patterns in beeping algorithms
• Deterministic leader election in O(D+ n) time with messages of size O(1)
• Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection
• Near optimal leader election in multi-hop radio networks
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• On the complexity of universal leader election
• Structural Information and Communication Complexity
• The computational power of beeps
• What is the use of collision detection (in wireless networks)?

Cited in

(11)

• The computational power of beeps
• Noisy beeping networks
• Optimal multi-broadcast with beeps using group testing
• Brief Announcement
• Communicating with beeps
• Beep-and-sleep: message and energy efficient set cover
• Optimal Message-Passing with Noisy Beeps
• Optimal message-passing with noisy beeps
• Brief announcement: Content-oblivious leader election on rings
• Content-oblivious leader election on rings
• Beeping deterministic congest algorithms in graphs

This page was built for publication: Beeping a deterministic time-optimal leader election

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