Publication

On the Complexity of Asynchronous Gossip

Rachid Guerraoui, Seth Gilbert
2008
Conference Papers

Abstract

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. In the latter case, we present three randomized algorithms for achieving gossip, each offering a different trade-off between time and message complexity. We then show how to use these gossip algorithms to develop message-efficient asynchronous (randomized) consensus protocols.

Official source

https://infoscience.epfl.ch/entities/publication/bcb10fde-8206-4637-926f-997688de8df0

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

On the Complexity of Asynchronous Gossip

Chat with Graph Search

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Learning Dynamic Graphs under Partial Observability

Efficient Preparation of Cyclic Quantum States