Applications of probabilistic quorums to iterative algorithms Conference Paper uri icon

abstract

  • This paper presents a definition of a read-write register that sometimes returns out-of-date values, shows that the definition is implemented by the probabilistic quorum algorithm of [19], and shows how to program with such registers using the framework of resin and Dubois [25]. Consequently, existing iterative algorithms for an interesting class of problems (including finding shortest paths, constraint satisfaction, and transitive closure) will converge with high probability if executed in a system in which the shared data is implemented with registers satisfying the new definition. Furthermore, the algorithms in this framework will inherit positive attributes concerning load and availability from the underlying register implementation. A monotone version of the new register definition is specified and implemented; it can provide improved expected convergence time and message complexity for iterative algorithms.

published proceedings

  • 21ST INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, PROCEEDINGS

author list (cited authors)

  • Lee, H. Y., Welch, J. L., SOCIETY, I. C., & SOCIETY, I. C.

complete list of authors

  • Lee, HY||Welch, JL||SOCIETY, IEEE COMPUTER||SOCIETY, IEEE COMPUTER

publication date

  • January 2001