Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits

DOI10.1007/S00446-018-0330-XzbMath1451.68037arXiv1602.04419OpenAlexW4392028875WikidataQ130094425 ScholiaQ130094425MaRDI QIDQ2002052

Emanuele Natale, Amos Korman, Lucas Boczkowski

Publication date: 11 July 2019

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.04419

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (5)

Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions ⋮ Phase transition of the \(k\)-majority dynamics in biased communication models ⋮ Early adapting to trends: self-stabilizing information spread using passive communication ⋮ Phase transition of the 3-majority opinion dynamics with noisy interactions ⋮ Phase transition of the 3-majority dynamics with uniform communication noise

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple population protocol for fast robust approximate majority
• A self-stabilizing transformer for population protocols with covering
• On the runtime and robustness of randomized broadcasting
• Synchronous counting and computational algorithm design
• Efficient counting with optimal resilience
• Fast consensus for voting on general expander graphs
• Speed faults in computation by chemical reaction networks
• Self-stabilizing repeated balls-into-bins
• Computation in networks of passively mobile finite-state sensors
• Towards Optimal Synchronous Counting
• Fast self-stabilizing byzantine tolerant digital clock synchronization
• Breathe before speaking
• Self-stabilizing clock synchronization in the presence of Byzantine faults
• A Biological Solution to a Fundamental Distributed Computing Problem
• Polylogarithmic-Time Leader Election in Population Protocols
• Clock Synchronization and Estimation in Highly Dynamic Networks: An Information Theoretic Approach
• On Self-stabilizing Synchronous Actions Despite Byzantine Attacks
• Tight bounds for clock synchronization
• Rumor Spreading in Social Networks
• Self-stabilizing systems in spite of distributed control
• Time, clocks, and the ordering of events in a distributed system
• Stabilizing Consensus with Many Opinions
• Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
• Optimal Clock Synchronization under Different Delay Assumptions
• Stone age distributed computing
• Brief Announcement
• Plurality Consensus in the Gossip Model
• Global computation in a poorly connected world
• Stable leader election in population protocols requires linear time

This page was built for publication: Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits