Two absolute bounds for distributed bit complexity

DOI10.1007/11429647_11MaRDI QIDQ5710078zbMATH OpenOpenAlexFDO

Authors Noam Solomon, Yefim Dinitz

Publication date 30 November 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b136628

Mathematics Subject Classification ID

Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Two absolute bounds for distributed bit complexity
• Bit complexity of breaking and achieving symmetry in chains and rings
• Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
• The Bit Complexity of Randomized Leader Election on a Ring
• Optimal tradeoffs between time and bit complexity in distributed synchronous rings

Cited in

(8)

• On the bit complexity of distributed computations in a ring with a leader
• Bit complexity of order statistics on a distributed star network
• Exact communication costs for consensus and leader in a tree
• Two absolute bounds for distributed bit complexity
• Toward computability of trace distance discord
• Optimal tradeoffs between time and bit complexity in distributed synchronous rings
• Beeping a deterministic time-optimal leader election
• Communication Complexity of Wait-Free Computability in Dynamic Networks

This page was built for publication: Two absolute bounds for distributed bit complexity

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