Communication efficient self-stabilizing leader election

DOI10.4230/LIPICS.DISC.2020.11MaRDI QIDQ6535008zbMATHFDO

Authors Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, Yasumasa Tamura

Publication date 2 November 2023

zbMATH Keywords

leader electionself-stabilizationcommunication overhead

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Recommendations

• Compact self-stabilizing leader election for general networks
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing leader election in polynomial steps
• Self-stabilizing weak leader election in anonymous trees using constant memory per edge
• An \(O(n)\)-time self-stabilizing leader election algorithm

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 4209563 (Why is no real title available?)
• scientific article; zbMATH DE number 1332668 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• scientific article; zbMATH DE number 2006647 (Why is no real title available?)
• scientific article; zbMATH DE number 2006653 (Why is no real title available?)
• scientific article; zbMATH DE number 2036579 (Why is no real title available?)
• scientific article; zbMATH DE number 6472584 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
• A trade-off between information and communication in broadcast protocols
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Compact self-stabilizing leader election for general networks
• Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Electing a leader in a synchronous ring
• Introduction to Distributed Self-Stabilizing Algorithms
• Low communication self-stabilization through randomization
• Memory requirements for silent stabilization
• Memory space requirements for self-stabilizing leader election protocols
• Proof-labeling schemes: broadcast, unicast and in between
• Reducing the number of messages in self-stabilizing protocols
• Resource bounds for self stabilizing message driven protocols
• Self-stabilization
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilization over unreliable communication media
• Self-stabilizing depth-first search
• Self-stabilizing depth-first token circulation in arbitrary rooted networks
• Self-stabilizing depth-first token circulation on networks
• Self-stabilizing extensions for message-passing systems
• The first fully polynomial stabilizing algorithm for BFS tree construction
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
• The local detection paradigm and its applications to self-stabilization
• The part-time parliament
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Time optimal self-stabilizing synchronization

Cited in

(2)

• Communication-efficient leader election and consensus with limited link synchrony
• Brief Announcement: Leader Election in the ADD Communication Model

This page was built for publication: Communication efficient self-stabilizing leader election

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