HP Labs Technical Reports
Click here for full text:
X-Ability: A Theory of Replication
Frolund, Svend; Guerraoui, Rachid
Keyword(s): replication; fault-tolerance; high-availability; Exactly-once
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.
Back to Index