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

DOI10.1137/0220023zbMath0722.68006OpenAlexW1974895073MaRDI QIDQ3210138

Eli Gafni, Yehuda Afek

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 algorithmsleader election algorithmscomplete networkstime-message complexities trade-off

Mathematics Subject Classification ID

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

Related Items (13)

An improved algorithm for finding the median distributively ⋮ Distributed election in complete networks ⋮ Improved deterministic leader election in diameter-two networks ⋮ Improved Tradeoffs for Leader Election ⋮ Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links ⋮ Design and analysis of dynamic leader election protocols in broadcast networks ⋮ Hundreds of impossibility results for distributed computing ⋮ Sublinear bounds for randomized leader election ⋮ The complexity of leader election in diameter-two networks ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ On the Complexity of Universal Leader Election ⋮ On a game in directed graphs.

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