Optimal tradeoffs between time and bit complexity in distributed synchronous rings

DOI10.1007/BFB0020805MaRDI QIDQ4035677zbMATH OpenFDO

Authors Bernd Schmeltz

Publication date 18 May 1993

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

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

zbMATH Keywords

bit complexityleader electionlower boundsrings of processors

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved bounds for electing a leader in a synchronous ring
• Bit-optimal election in synchronous rings
• The Bit Complexity of Randomized Leader Election on a Ring
• Electing a leader in a synchronous ring
• Structural Information and Communication Complexity

Cited in

(11)

• On the bit complexity of distributed computations in a ring with a leader
• Improved bounds for electing a leader in a synchronous ring
• Tight bounds for synchronous communication of information using bits and silence
• Two absolute bounds for distributed bit complexity
• Trading bit, message, and time complexity of distributed algorithms
• Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times
• On the microscopic view of time and messages
• scientific article; zbMATH DE number 2113969 (Why is no real title available?)
• Learning a ring cheaply and fast
• Structural Information and Communication Complexity
• Bit-optimal election in synchronous rings

This page was built for publication: Optimal tradeoffs between time and bit complexity in distributed synchronous rings

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