Categories
Algorithm

Multi-Paxos

Last week we’ve seen how basic Paxos works. Today we’re going to extend it in order to run a distributed state machine  – a state machine with the same state on all the nodes.

The idea is to use a distributed log to run the state machine. Each entry in the log is an operation to apply to the state machine. If the log is the same on every node then the same operations are applied in the same order on all the nodes and therefore the state machines are all in the same state.

2 nodes in cluster using paxos to maintain a distributed log to replicate a state-machine
2 nodes in cluster using paxos to maintain a distributed log to replicate a state-machine

The question is :

How to make sure the log is the same on all the nodes?

The solution is to run basic-Paxos for every log entry (plus add some tweaks to solve some issues and improve performance)

Categories
Algorithm

Basic Paxos

This week subject is a classic in distributed computing: Paxos which is so popular that it almost became a synonym of consensus.

First let’s start by examining the problem faced by distributed system and why we need a consensus algorithm.