Reliable Broadcast: Overview and Algorithms

This lecture covers the concept of reliable broadcast in distributed systems, comparing it with best-effort broadcast and uniform reliable broadcast. It explains the properties and events associated with each type of broadcast, providing specifications and algorithms for reliable broadcast. The lecture also presents detailed algorithms for implementing best-effort broadcast, along with proofs for their validity, no duplication, and no creation properties. Additionally, it discusses the agreement property in reliable broadcast and the importance of uniform agreement in uniform reliable broadcast.

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.

Related lectures (20)

Related concepts (41)

CS-451: Distributed algorithms

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machin

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.

Prim's algorithm

In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list.

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Total Order Broadcast: Basics and Consensus Equivalences CS-451: Distributed algorithms

Explores total order broadcast and its equivalence to consensus in reliable systems.

Algorithms & Growth of Functions CS-101: Advanced information, computation, communication I

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Introduction to Algorithms CS-119(c): Information, Computation, Communication

Introduces algorithms, covering their formalization, basic components, control structures, and the challenge of ensuring correctness.

Optimization Algorithms: Greedy Approach CS-101: Advanced information, computation, communication I

Explores optimization problems and greedy algorithms for efficient decision-making.

Algorithmic Complexity: Definition and Examples CS-119(d): Information, Computation, Communication

Explores algorithm correctness, worst-case complexity analysis, and efficiency comparison based on input size.