Date Added: Jan 2010
This paper presents in detail an efficient and provably correct algorithm for database replication over partition able networks. The algorithm avoids the need for end-to-end acknowledgments for each action while supporting network partitions and merges and allowing dynamic instantiation of new replicas. One round of end-to-end acknowledgments is required only upon a membership change event such as a network partition. New actions may be introduced to the system at any point, not only while in a primary component. The paper shows how performance can be further improved for applications that allow relaxation of consistency requirements. The paper provides experimental results that demonstrate the efficiency of the approach.