Publication

Lower Bounds on Generic Broadcast Algorithms

André Schiper, Fernando Pedone
2004
Reports

Abstract

This paper establishes tight lower bounds on the time complexity of algorithms solving the generic broadcast problem. Generic broadcast assumes a symmetric, non-reflexive conflict relation on the set of messages, and requires ordered delivery only for conflicting messages. The lower bounds established in this paper relate the resilience of generic broadcast algorithms (i.e., the total number of failures f the algorithms can tolerate) to their time complexity in runs in which oracles are not used. The paper shows that (a) to deliver messages in one round, no failures can be tolerated, (b) to deliver messages in two rounds, at most f < n/3 failures can be tolerated, where n is the number of processes in the system, and (c) to deliver messages in three rounds, at most f < n/2 failures can be tolerated.

Official source

https://infoscience.epfl.ch/entities/publication/1ca31a68-6255-4d11-9a8a-fa23a4e69759

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.

André Schiper, Fernando Pedone
2004
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/1ca31a68-6255-4d11-9a8a-fa23a4e69759

About this result

Related concepts (31)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Related publications (2)

Lower Bounds on Generic Broadcast Algorithms

Chat with Graph Search

Overlap properties of geometric expanders

New algorithmic methods for real-time transportation problems