A Bound of Data Availability when Networks Partition Dartmouth Technical Report PCS-TR90-145 Michael Goldweber Donald B. Johnson Date: March 1990 URL (PDF): (688KB) Abstract: Many consistency or replication control schemes that increase data availability in distributed systems exist, and the search for improvements continues, though there have been no good nontrivial upper bound demonstrating how much improvement is possible. We present a new upper bound for data availability under replication for general networks. In addition we also describe a new technique that yields near optimal levels of data availability with respect to this bound.