Implementing an Eventually-Serializable
Data Service as a Distributed System Building Block
Oleg M. Cheiner
and
Alex A. Shvartsman
This work presents an implementation of a distributed system
building block for
the Eventually-Serializable Data Service (ESDS)
proposed by Fekete \emph{et al.}~\cite{esds}.
ESDS deals with replicated objects that allow the users of the service to relax
consistency requirements in return for improved responsiveness, while providing
guarantees of eventual consistency of the replicated data.
ESDS~\cite{esds} includes a formal service specification and an abstract algorithm for
it. The algorithm is given in terms of I/O automata of Lynch and Tuttle~\cite{Lynch}.
An important consideration in formulating ESDS was
that it could be employed in building real systems.
Starting with the abstract ESDS algorithm,
we develop an optimized implementation of ESDS
and we explore its behavior.
We combine the implementation with different data types and
clients, thus demonstrating the utility of the service as a
{\em building block\/} suitable for serving as a distributed operating
system component.
The implementation has been experimentally evaluated on a network
of workstations. Our results confirm that the designed trade-off between
{\em consistency\/} and {\em performance\/} is present in
the implemented service.
Faithful derivation of systems from abstract algorthms being an error-prone
process, we also develop and use a framework for
mapping algorithms specified using I/O automata to distributed programs.
The framework includes a methodology that guides the software development
process, and it includes a core set of
functions needed in target implementations that reduce
unnecessary software development.
Abstract
(a brief presentation in PODC'98)
Full paper
(to be available shortly)