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


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.