Optimal Termination Protocols for Network Partitioning

We address the problem of maintaining the distributed database consistency in presence of failures while maximizing the database availability. Network partitioning is a failure which partitions the distributed system into a number of parts, no part being able to communicate with any other. Formalizations of various notions in this context are developed and two measures for the performances of protocols in presence of a network partitioning are introduced. A general optimality theory is developed for two classes of protocols - centralized and decentralized. Optimal protocols are produced in all cases.published_or_final_versio