Exact communication costs for consensus and leader in a tree

DOI10.1016/S1570-8667(03)00024-8MaRDI QIDQ1827285zbMATH OpenOpenAlexFDO

Authors Shlomo Moran, Sergio Rajsbaum, Yefim Dinitz

Publication date 6 August 2004

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

Full work available at URL https://doi.org/10.1016/s1570-8667(03)00024-8

zbMATH Keywords

complexityDistributed computingLeader electionConsensusCommunication complexityBit complexityMessage

Mathematics Subject Classification ID

Distributed systems (68M14)

Recommendations

• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• Bit complexity of breaking and achieving symmetry in chains and rings
• Structural Information and Communication Complexity
• Two absolute bounds for distributed bit complexity
• Communication complexity of consensus in anonymous message passing systems

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1256713 (Why is no real title available?)
• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• scientific article; zbMATH DE number 1559553 (Why is no real title available?)
• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• Communication Complexity
• Decentralized extrema-finding in circular configurations of processors
• Distributed algorithms for finding centers and medians in networks
• Distributed network protocols
• Impossibility of distributed consensus with one faulty process
• Lower bounds on communication complexity in distributed computer networks
• On the total\(_k\)-diameter of connection networks

Cited in

(1)

• Two absolute bounds for distributed bit complexity

This page was built for publication: Exact communication costs for consensus and leader in a tree

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