Meeting the deadline: on the complexity of fault-tolerant continuous gossip

DOI10.1007/s00446-011-0144-6zbMath1231.68076OpenAlexW2046966237MaRDI QIDQ661066

Dariusz R. Kowalski, Chryssis Georgiou, Seth Gilbert

Publication date: 6 February 2012

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

Full work available at URL: https://doi.org/10.1007/s00446-011-0144-6

zbMATH Keywords

gossipcrashes and restartsdynamic rumor injectionrandom and expander graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Robust gossiping with an application to consensus
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Optimal adaptive broadcasting with a bounded fraction of faulty nodes
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• The diameter of random regular graphs
• Efficient gossip and robust distributed computation
• Distributed computation in dynamic networks
• On the complexity of asynchronous gossip
• On the Communication Surplus Incurred by Faulty Processors
• Time and Communication Efficient Consensus for Crash Failures
• Randomness conductors and constant-degree lossless expanders
• Collective asynchronous reading with polylogarithmic worst-case overhead
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Sorting and Selecting in Rounds
• Spreading Rumors Rapidly Despite an Adversary
• Loss-less condensers, unbalanced expanders, and extractors
• Spatial gossip and resource location protocols
• Fault-tolerant broadcasting and gossiping in communication networks

This page was built for publication: Meeting the deadline: on the complexity of fault-tolerant continuous gossip