On the bit complexity of distributed computations in a ring with a leader

DOI10.1016/0890-5401(87)90056-3zbMath0636.68038OpenAlexW1979286404MaRDI QIDQ1098291

Shmuel Zaks, Yishay Mansour

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90056-3

zbMATH Keywords

pattern recognitioncommunication complexitybit complexitynetwork of processorsdistributed ring with a leader

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Theory of software (68N99)

Related Items (3)

On the bit complexity of distributed computations in a ring with a leader ⋮ Symmetry breaking in distributed networks ⋮ Hundreds of impossibility results for distributed computing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two lower bounds in asynchronous distributed computation
• On the bit complexity of distributed computations in a ring with a leader
• Lower Bounds for Distributed Maximum-Finding Algorithms
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Computational Complexity of One-Tape Turing Machine Computations
• One-tape, off-line Turing machine computations

This page was built for publication: On the bit complexity of distributed computations in a ring with a leader