The impossibility of consensus

Abstract

This lecture introduced the importance of the famous consensus problem, before explaining how this concept is central to digital technology today. The lecture then presented the impossibility theorem of consensus and its proof in the relatively simple case of shared memory. The notion of bivalence was introduced, as was the fundamental concept of adversaries in distributed algorithms. Several corollaries of the impossibility of consensus were then presented. The lecture also emphasized the link with algebraic topology to introduce the guest seminar on ensemblistic consensus and algebraic topology.

Here are the main topics covered during this lecture :

• " Implementing a strong counter " ;
• " The consensus impossibility theorem " ;
• " Adversary, valence and execution " ;
• " Impossibility corollaries " ;
• " Consensus ensembliste ".