Precise executable Paxos pseudocode improves understanding and debugging
Specifying Paxos for System Builders: Pseudocode Made Executable
Distributed, Parallel, and Cluster Computing
Summary
Distributed computer systems need to agree on decisions reliably, but the rules for doing this, called Paxos, can be confusing and tricky to get right. This paper shows how the common Paxos instructions can be turned into a clear, step-by-step program that a computer can run directly. The authors found that doing this helped them spot small mistakes in the original instructions and understand how the system works better. Their program runs well and is about as simple as the original instructions.
What this means in practice
- •For distributed system builders: Implement Paxos consensus with clearer, directly executable code to catch subtle bugs in protocol logic during development.
- •For networked software teams: Trace and visualize consensus protocol runs using precise specifications to enhance debugging and system understanding.
Authors
Yanhong A. Liu, Rahul Sihag
Abstract
This paper presents a precise executable specification---as a faithful mapping from the pseudocode---of Paxos for System Builders, a practical protocol for replication and consensus in distributed systems. Paxos for System Builders has both a robust implementation in C and a clean pseudocode for critical protocol details. This paper shows how the protocol pseudocode can be expressed easily, essentially line-by-line, in a precise high-level language, DistAlgo, for direct execution in distributed systems. Precise specification and direct execution help significantly in understanding the protocol logic and in automatically checking, tracing, and visualizing protocol runs. They also led to discoveries and fixes of small, difficult-to-catch omissions and liveness bugs in the pseudocode though not the C code. The resulting program also has acceptable performance while having similar size as the pseudocode.