Papers for

networked software teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Precise executable Paxos pseudocode improves understanding and debugging

Specifying Paxos for System Builders: Pseudocode Made Executable

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.

Thu 10 SeptDistributed, Parallel, and Cluster Computing

The gist

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.

Open → 2609.12239v1