Communication efficient self-stabilizing leader election

DOI10.4230/LIPICS.DISC.2020.11zbMATH Open1543.68036MaRDI QIDQ6535008FDOQ6535008

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

Publication date: 2 November 2023

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

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)

Cites Work

• Self-stabilizing extensions for message-passing systems
• Self-stabilization
• Title not available (Why is that?)
• A trade-off between information and communication in broadcast protocols
• Electing a leader in a synchronous ring
• Title not available (Why is that?)
• Time optimal self-stabilizing synchronization
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Title not available (Why is that?)
• Title not available (Why is that?)
• The local detection paradigm and its applications to self-stabilization
• Memory requirements for silent stabilization
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Low communication self-stabilization through randomization
• Title not available (Why is that?)
• Self-stabilizing depth-first search
• Self-stabilizing depth-first token circulation in arbitrary rooted networks
• A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
• Self-stabilization over unreliable communication media
• Title not available (Why is that?)
• Memory space requirements for self-stabilizing leader election protocols
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Title not available (Why is that?)
• Self-stabilizing depth-first token circulation on networks
• Resource bounds for self stabilizing message driven protocols
• 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
• Proof-labeling schemes: broadcast, unicast and in between
• Introduction to Distributed Self-Stabilizing Algorithms
• The part-time parliament
• Title not available (Why is that?)
• The first fully polynomial stabilizing algorithm for BFS tree construction
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
• Reducing the number of messages in self-stabilizing protocols

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)