X-Ability: A Theory of Replication

[摘要] 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. 17 Pages

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）

[关键词] replication;fault-tolerance;high-availability;Exactly-once