The Paxos Algorithm

A Google TechTalk, 2/2/18, presented by Luis Quesada Torres. ABSTRACT: This Tech Talk presents the Paxos algorithm and discusses a fictional distributed storage system (i.e. simplified Megastore) based on Paxos. The Paxos algorithm is one of the most common consensus algorithms. Consensus algorithms are one of the mechanisms that allow satisfying consistency constraints in distributed systems with consistency constraints, whether they follow a leader-replica schema or a peer-to-peer schema. Leader-replica systems consist of a leader node that proposes, manages, accepts, and serializes changes, and replica nodes that propose changes to the current leader node. Given that a single entity is in charge of acception and serialization, leader-replica systems do not require consensus algorithms in order to agree on what the next state is. However, if the leader node becomes unreachable, the replica nodes need to agree on which one should become the next leader node, and they usually run consensus algorithms to reach that agreement. Peer-to-peer systems consist of nodes that can propose changes and participate in accepting changes. The nodes need to agree on what the next state is in order to establish consistency, and they usually run consensus algorithms to reach that agreement. SREs within and outside Google work with highly scalable (and therefore distributed) systems that have consistency constraints and involve consensus algorithms. About the Speaker: Luis Quesada Torres is a Senior Software Engineer in Google's Site Reliability Engineering team.