Better computing on the anonymous ring

DOI10.1016/0196-6774(91)90002-GzbMath0734.68014OpenAlexW2012809967MaRDI QIDQ3361868

Hagit Attiya, Marc Snir

Publication date: 1991

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(91)90002-g

zbMATH Keywords

lower boundaverage complexityasynchronous deterministic algorithmasynchronous probabilistic algorithmMonte-Carlo asynchronous algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Related Items

Distributed tree comparison with nodes of limited memory ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Computing functions on asynchronous anonymous networks ⋮ Assigning labels in an unknown anonymous network with a leader ⋮ Hundreds of impossibility results for distributed computing ⋮ How much memory is needed for leader election ⋮ Knowledge, level of symmetry, and time of leader election ⋮ Message terminating algorithms for anonymous rings of unknown size ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Impact of knowledge on election time in anonymous networks ⋮ Topology recognition and leader election in colored networks ⋮ Perfect broadcasting in unlabeled networks ⋮ On the round complexity of Byzantine agreement without initial set-up ⋮ Broadcasting in unlabeled hypercubes with a linear number of messages. ⋮ Anonymous meeting in networks