Paper talf

Distributed Fault Tolerant Controllers∗
Leonardo Mostarda, Rudi Ball, Naranker Dulay Department of Computing Imperial College London Email: {lmostard, rkb, nd}@imperial.ac.uk

Abstract
Distributed applications are often built from sets of distributed components that must be co-ordinated in order to achieve some global behaviour. The common approach is to use a centralised controller forco-ordination, or occasionally a set of distributed entities. Centralised co-ordination is simpler but introduces a single point of failure and poses problems of scalability. Distributed co-ordination offers greater scalability, reliability and applicability but is harder to reason about and requires more complex algorithms for synchronisation and consensus among components. In this paper we present asystem called GOANNA that from a state machine specification (FSM) of the global behaviour of interacting components can automatically generate a correct, scalable and fault tolerant distributed implementation. GOANNA can be used as a backend for different tools as well as an implementation platform in its own right.

1 Introduction
Programmers often face the problem of correctly coordinatingdistributed components in order to achieve a global behaviour. These problems include sense and react systems [9], military reconnaissance and rescue missions [1], autonomous control systems as found in aviation and safety critical systems. The common approach used is to build of a centralised control system that enforces the global behaviour of the distributed components. The advantages ofcentralised coordination are that implementation is much simpler [11, 17] as there is no need to implement synchronisation and consensus among components, furthermore many tools are available for the definition and implementation of centralised controllers [2]. Existing distributed solutions are typically application-specific and require that the programmer understands and implements (often subtle)algorithms for synchronisation and consensus [7, 5].
research was supported by UK EPSRC research grant EP/D076633/1 (UBIVAL).
∗ This

In this paper we present a novel approach to generate a distributed and fault-tolerant implementation from a single Finite State Machine (FSM) definition. We model the system as a set of components providing and requiring services. Co-ordination (global behaviour) isdefined by a global FSM that defines the interactions among sets of components. Sets provide support to group available components at runtime and allows the selection of an alternative instance of a component in case of failure. A global state machine is automatically translated into a collection of local ones, one for each set. A FSM Manager at each host is responsible for handling the events andinvocations for its local state machines and ensuring correct global behaviour. A Leader is responsible for the management and synchronisation of FSM Managers. This is achieved through an extension of a Paxos-based consensus protocol that implements correct, scalable and fault tolerant execution of global FSM. In particular scalability is obtained by using different optimisations that are derived fromthe FSM structure. Various approaches could benefit from having automatically generated distributed implementations provided by a centralised specification. For instance the automatic synthesis of component based applications such as [4, 10, 19] are commonly used to generate a centralised controller where global state machines are obtained through composition and can have millions of states. Suchapproaches would benefit from our distribution approach that ensures correctness and provides scalability. We have implemented our approach in a system called GOANNA [16] that takes as input, state machines and generates as output, distributed implementations in JAVA, C or nesC. The system is being used to develop distributed applications for sensor networks, unmanned vehicles and home networks...