Specification, Implementation and Application of Randomized Regular Registers
Hyunyoung Lee and Jennifer L. Welch
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
This paper presents a definition of a randomized regular register, shows
that the definition is implemented by the probabilistic quorum algorithm
of Malkhi, Reiter and Wright (1997), and shows how to program with such
registers using the framework of Uresin and Dubois (1990). Consequently,
existing iterative algorithms for a large class of problems (including
solving systems of linear equations, finding shortest paths, etc.) will
converge with high probability if executed in a system in which the shared
data is implemented with registers satisfying the new condition. A modified
definition is presented and its expected time for convergence is calculated
and compared experimentally with that for the original definition.