Optimal consistency protocols for replicated files

The author presents an absolute upper bound on the read and write availabilities of a replicated field and a method of computing them. He introduces a novel class of consistency protocols called stochastic protocols that allow the file manager program to randomly choose whether a file will be made available or not. Using this class of protocols, the author derives a strict upper bound on the write availability of a replicated file in a nonpartitionable environment without an oracle and shows that a corresponding implementable protocol exists.<>