X-Ability: A Theory of Replication
Svend Frolund and Rachid Guerraoui
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Different replication mechanisms provide different solutions to the same
basic problem. However, there is no precise specification of the problem
itself, only of particular classes of solutions, such as active replication
and primary-backup. Having a precise specification of the problem would
help us better understand the space of possible solutions. We present a
formal definition of the problem solved by replication. We introduce x-ability
(Exactly-once-ability) as a correctness criterion for replicated services.
An x-able service has obligations to its environment and its clients. It
must update its environment under exactly-once semantics. Furthermore,
it must provide idempotent, non-blocking request processing and deliver
consistent results to clients. X-ability is a local property: replicated
services can be specified and implemented independently, and later composed
in the implementation of more complex replicated services. We illustrate
the value of x-ability through a novel replication protocol that handles
non-determinism and external side-effects.