An example simulation run with some configs (5 nodes, 2 proposers, 10% drop rate, 33% delay rate of messages) The proposer event trace logs capture some cool Paxos behaviors, e.g. round preemption after seeing a higher ballot (also notice the retries).

But the most interesting one is the last one: where a proposer, node 0, abandoned its own proposed value because it saw a value previously accepted by another node, and had to pick it up.

Paxos

An implementation of classical single-decree Paxos algorithm.

The core node logic is deliberately separated from runtime concerns, this helps with fancy testing/verification which is currently a WIP.

Architecture

Everything revolves around a Paxos node (protocol_node.go) that:

• receives explicit events (proposal triggered from the outside world, message received from the outside world.. etc)
• updates protocol state (for example, storing a promisedBallot when receiving a Prepare request)
• and outputs actions (or traces for observability), for example, the output of a node when it receives a valid Prepare request is simply the following action: sendMessage{to: the_proposer_that_sent_me_a_Prepare, msg: Promise}.

It's mostly a dumb deterministic state machine with no side effects.

CLI

Now, there is an upper layer (node_driver.go) which is really just a wrapper that decides how to run the actions and their side effects, and handles timers and network/transport concerns.. it's the 'alive' Paxos node that is a single goroutine wrapping the protocol logic engine.

This node driver is there for the CLI (as opposed to the testing harness, the WIP).

Those 'alive' nodes communicate over local_network.go, which tries to simulate real world networks (with caveats, more on that later), with configurable injected faults: it asks fault_injector.go for each delivery whether to forward the message, or delay/duplicate/drop it..

This is assuming that the receiver or sender nodes are not crashed, the fault injector can 'crash' nodes (and by crash we really mean isolating them by blocking delivery. When they come back, it's like they restored stuff from their persistent memory). It also schedules faults, so you can express "crash node 2 after 300ms".

This is all orchestrated by simulation.go which just sets up those node drivers, with configurable faults (haven't added scheduled faults there yet), plumbs them into the local network, then kickstarts their loop that:

• waits for events, then dispatches them into the protocol logic that will return actions to be performed
• inspects & applies reported actions and records traces to be shown in the CLI

Caveat: 'Learning' is still not fully implemented, it's currently modeled through decided-message reliable broadcast (rather than a full learner gossip mechanism I guess)

Examples

This is an interesting example with some weird proposer contention, under an unrealistically perfect network. (5 nodes, all of which are proposers):

go run ./cmd/paxos -n 5 -p 5 -max-jitter=1ms

Run
  nodes      5
  proposers  5
  timeout    5s

Environment
  retry      100ms -> 5s, max 5
  jitter     <= 1ms
  faults     drop 0.00, duplicate 0.00, delay 0.00 up to 0s

..................
...long trace...
.................

  - node 2 preempted round (c1195,p2) after seeing higher ballot (c1196,p1)
  - node 2 started round (c1197,p2) with client value "val-6659"
  - node 2 preempted round (c1197,p2) after seeing higher ballot (c1198,p0)
  - node 2 started round (c1199,p2) with client value "val-6659"

Result
All nodes agreed on "val-6659"