On the automated implementation of time-based Paxos using the IOA compiler

Abstract

Paxos is a well known algorithm for achieving consensus in distributed environments with uncertain processing and communication timing. Implementations of its variants have been successfully used in the industry (eg., Chubby by Google, Autopilot cluster management in Bing by Microsoft, and many others). This paper addresses the challenge of the manual coding of complex distributed algorithms, such as Paxos, where this is an error prone process. Our approach in ensuring correct implementation is to use a verified automated translator to compile a source specification that has been proven to be itself correct. We use specification of the Paxos algorithm in the General Timed Automata (GTA) model, an extension of I/O Automata, as input to an augmented compiler for the Input/Output Automata notation (a.k.a., the IOA compiler) in order to generate executable Java code. The resulting code is interfaced with MPI for communication needs. We have extended the IOA compiler to support a version of the GTA model, which uses time-passage actions such as ν(t), to model the passage of time by t time units. A time-based version of Paxos is used to demonstrate the capabilities of our extension. In this paper we describe the process to be followed in order to compile time-based Paxos, or similar algorithms. The utility of our approach is supported by an experimental evaluation of our Paxos implementation on a collection of workstations. To the best of our knowledge, our case study constitutes the first example of a time-dependent distributed algorithm that has been specified, verified and implemented in an automated way, using a common formal methodology. © 2010 Springer-Verlag.