Two lower bounds in asynchronous distributed computation

DOI10.1016/0022-0000(91)90002-MzbMath0731.68043OpenAlexW2148349970MaRDI QIDQ808249

Zvi Galil, Pavol Ďuriš

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90002-m

zbMATH Keywords

lower boundsdistributed computationmessage complexitybidirectional ring of n anonymous processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (3)

On the bit complexity of distributed computations in a ring with a leader ⋮ Computing functions on asynchronous anonymous networks ⋮ Hundreds of impossibility results for distributed computing

Cites Work

• Unnamed Item
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Computing on an anonymous ring
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

This page was built for publication: Two lower bounds in asynchronous distributed computation