> **Note:** This was an old example project that I had written
> and found many years later. Keep judgement light.

paxos-testing
=============

A small, runnable demonstration of single-decree Paxos, following
Lamport's paper "Paxos Made Simple" (2001).

Everything runs in one process on a simulated network, so a whole run
takes milliseconds and can be repeated exactly by reusing the same
random seed. Nothing outside the standard library is needed.

Requires Python 3.5.


Running it
----------

    python3 demo.py             (runs all four scenarios)
    python3 demo.py happy       (or just one: happy, lossy, duel, crash)

The scenarios are:

  happy   one proposer, three acceptors, no message loss.

  lossy   five acceptors and a third of the messages dropped, so the
          proposer has to retry with higher ballots before a value
          sticks.

  duel    two proposers with different values starting at the same
          time. Only one of the two values can be chosen.

  crash   five acceptors, two of them dead. A majority is still alive,
          so the run still finishes.

To run the tests:

    python3 -m unittest discover


How it fits together
--------------------

    proposer                acceptor                learner
       |  --- Prepare --->     |                       |
       |  <-- Promise ----     |                       |
       |  --- Accept ---->     |                       |
       |  <-- Accepted ---     | ---- Accepted ----->  |

  paxos/messages.py   the five message types. A ballot is a
                      (round, proposer_id) tuple, so two proposers can
                      never use the same ballot number.

  paxos/acceptor.py   promises not to accept anything older, and
                      reports the proposal it already accepted.

  paxos/proposer.py   phase 1 and phase 2. If any acceptor in the
                      quorum already accepted a value, the proposer has
                      to propose that value instead of its own. That is
                      the rule that keeps the protocol safe.

  paxos/learner.py    counts Accepted messages and declares a value
                      chosen once a majority agrees.

  paxos/network.py    the simulated network: drops messages, shuffles
                      the delivery order, and can kill nodes.

  paxos/cluster.py    scaffolding for the demo and the tests, not part
                      of the protocol itself.


Things it deliberately does not do
----------------------------------

  * Only one value is ever decided (single decree). Multi-Paxos, where
    the same machinery decides a sequence of values, is not here.

  * Acceptor state is kept in memory rather than on disk, so a node
    that "crashes" here never comes back.

  * There are no real timeouts or sockets. A retry happens when the
    simulated network goes quiet instead.

  * Only the first proposer retries. If every proposer retried they
    could keep outbidding each other forever, which is the livelock
    described in section 2.4 of the paper.