X-ability: A Theory of Replication

This paper presents x-ability (Exactly-once-ability): a correctness criteria for replicated services. X-ability provides the illusion that the actions executed by a replicated service are executed exactly-once, even if these actions have been actually executed several times and by various replicas. A client can treat a x-able replicated service as if it was not replicated, even if this service executes actions that are non-deterministic and have side-effects on the environment, e.g., invoke other services. 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 our theory through an asynchronous replication protocol that handles non-determinism and external side-effects. The replication protocol is asynchronous in the sense that it may vary, at run-time and according to the asynchrony of the system, between some form of primary-backup and some form of active replication.