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

DOI10.1016/0890-5401(87)90056-3MaRDI QIDQ1098291zbMATH OpenOpenAlexFDO

Authors Yishay Mansour, Shmuel Zaks

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

bit complexitycommunication complexitydistributed ring with a leadernetwork of processorspattern recognition

Mathematics Subject Classification ID

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

Recommendations

• The Bit Complexity of Randomized Leader Election on a Ring
• New lower bound techniques for distributed leader finding and other problems on rings of processors
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• scientific article; zbMATH DE number 17531
• A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors
• scientific article; zbMATH DE number 176511
• Two absolute bounds for distributed bit complexity
• Structural Information and Communication Complexity
• Improved bounds for electing a leader in a synchronous ring
• The bit complexity of distributed sorting

Cites work

• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Computational Complexity of One-Tape Turing Machine Computations
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3319549 (Why is no real title available?)
• Lower Bounds for Distributed Maximum-Finding Algorithms
• On the bit complexity of distributed computations in a ring with a leader
• One-tape, off-line Turing machine computations
• Two lower bounds in asynchronous distributed computation

Cited in

(8)

• On the bit complexity of distributed computations in a ring with a leader
• Language complexity on the synchronous anonymous ring
• String recognition on anonymous rings
• The Bit Complexity of Randomized Leader Election on a Ring
• scientific article; zbMATH DE number 7204593 (Why is no real title available?)
• Hundreds of impossibility results for distributed computing
• On recognizing a string on an anonymous ring
• Symmetry breaking in distributed networks

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

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