X-Ability: a theory of replication |
| |
Authors: | Svend Frølund Rachid Guerraoui |
| |
Affiliation: | (1) HP Labs, Palo Alto, CA 94304, USA, US;(2) Swiss Federal Institute of Technology, 1015-Lausanne, Switzerland, CH |
| |
Abstract: | Summary. Different replication algorithms 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 and possibly come out with new
ones. We present a formal definition of the problem solved by replication in the form of a correctness criterion called x-ability (exactly-once ability). 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 its clients. We illustrate the value of x-ability through a novel 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.
Received: December 2000 / Accepted: September 2001 |
| |
Keywords: | : Replication – High-availability – Exactly-once – Correctness condition – Multi-tier systems |
本文献已被 SpringerLink 等数据库收录! |
|