There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they permit at most one (distinguished) partition to process updates at any given time. This project seeks to: 1) Identify the algorithm that yields optimal availability under a model called the site model, and prove the optimality of that algorithm; 2) Determine heuristics that provide near optimal availability under other models in which the sites and links are modeled as heterogeneous objects. The focus of this research is on dynamic algorithms, in which the potential distinguised partitions cannot be listed in advance (i.e., the list changes over time). Such algorithms have been shown to provide better availability than the more traditional static algorithms. The issue of replica control is of central importance in distributed databases. This research will yield improved algorithms and establish limits on the best one can achieve in this arena.
