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


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.