A dynamic majority determination algorithm for reconfiguration of network partitions (Q1111008)

We present a conservative consistency and recovery control algorithm for replicated files in the presence of network partitioning due to communication link failures. This algorithm supports partial replication, provides nonblocking operations by allowing update access to a file in that file's majority partition, and brings all copies up to date on all sites whenever the communication links among them are repaired. This algorithm belongs to the class of dynamic voting algorithms proposed in the recent literature. When the communication link among some partitions is reestablished, the algorithms proposed so far do not always allow the merge (reconciliation) of these partitions to form a single partition. A merge condition has to be satisfied to avoid possible inconsistencies. This is undesirable because in a system with more than one replicated file, two or more partitions cannot be integrated to form a single partition if any one of the replicated fields in these partitions does not satisfy the merge condition. This restriction might cause the system to remain partitioned for a long time even if communication links are repaired. (In the previous papers, such a problem is not addressed, since a system with only one replicated file is assumed.) The algorithm proposed in this paper avoids any such merge condition and integrates the partitions whenever a communication link failure is repaired, thus providing a higher degree of availability. This work formalizes the presentation of algorithms and data structures for implementation.