Programming Language Extensions for Replicated State Machines

Printer-friendly version

In distributed systems a fundamental problem is to make a collection of nodes (machines) work as a coherent group, even in the case of failures. Often this involves the nodes reaching agreement on a certain value needed for computation. Consensus algorithms solve this exact problem and are therefore a crucial asset in developing distributed systems.

One instance of the consensus problem is the replicated state machine problem. In this context state machines that run on a collection of machines (servers) compute identical copies of the same state. The state machines can even continue to run even if some of the machines fail.

Replicated state machines are typically implemented using a replicated log.

Using a consensus algorithm on the servers it is possible to agree over a replicated log. Each server stores a copy of the log which contains a series of commands that originate from clients. The state machine on the server executes the commands from the log in order. Each log contains the same commands in the same order. Since the state machines are deterministic and execute the same commands, they compute the same state and the same sequence of outputs.

At the Software Languages Lab we have developed an advanced distributed programming language, called AmbientTalk. AmbientTalk is specifically conceived to develop peer-to-peer applications that operate in mobile ad hoc networks. Such networks suffer from many disconnections and peers frequently come and go. AmbientTalk features language constructs that automatically handle failures and that allow programmers to react to changes in connectivity of network peers. AmbientTalk features an event-driven concurrency model ,founded on the actor model. Actors communicate by asynchronously exchanging messages.

Many of the applications developed in AmbientTalk are structured as state machines and since we deal with distributed applications, consensus is often needed. However, AmbientTalk has no support for implementing state machines or integrate consensus in applications. 

Goal & Research Activities: 

The goal of the thesis is to extend AmbientTalk as follows:

1. Provide language support to naturally express state machines in AmbientTalk,
2. Integrate a consensus algorithm with AmbientTalk’s existing message passing paradigm

Initially we will start from a fixed cluster of nodes. But after competing steps 1 and 2 we will:

3. Extend the resulting model to work in the context of mobile ad hoc networks with a variable number of cluster nodes.