Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

DOI10.1137/0220023MaRDI QIDQ3210138zbMATH OpenOpenAlexFDO

Authors Yehuda Afek, Eli Gafni

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220023

zbMATH Keywords

distributed algorithmscomplete networksleader election algorithmstime-message complexities trade-off

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Applications of graph theory to circuits and networks (94C15) Network design and communication in computer systems (68M10)

Recommendations

• scientific article; zbMATH DE number 1759418
• Communication and time complexity of a distributed election protocol
• Election in asynchronous complete networks with intermittent link failures
• Message lower bounds via efficient network synchronization
• Message Lower Bounds via Efficient Network Synchronization
• The Election Problem in Asynchronous Distributed Systems with Bounded Faulty Processes
• Time-message trade-offs in distributed algorithms
• Message and time efficient consensus protocols for synchronous distributed systems
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation

Cited in

(18)

• Design and analysis of dynamic leader election protocols in broadcast networks
• Improved Tradeoffs for Leader Election
• scientific article; zbMATH DE number 4050994 (Why is no real title available?)
• An improved algorithm for finding the median distributively
• Message Lower Bounds via Efficient Network Synchronization
• Hundreds of impossibility results for distributed computing
• Communication efficient self-stabilizing leader election
• Improved deterministic leader election in diameter-two networks
• scientific article; zbMATH DE number 1759418 (Why is no real title available?)
• Communication and time complexity of a distributed election protocol
• Message lower bounds via efficient network synchronization
• On the Complexity of Universal Leader Election
• Distributed election in complete networks
• On a game in directed graphs.
• An efficient message passing election algorithm based on Mazurkiewicz's algorithm
• Singularly optimal randomized leader election
• Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links
• The complexity of leader election in diameter-two networks

This page was built for publication: Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

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