Bounding the Unbounded
Many important protocols in distributed computing have simple and
elegant solutions if we allow the assumption of unbounded size
registers. This assumption can be simulated in practice using sufficiently
large but bounded registers; however the resulting protocols are
extremely vulnerable to transient faults. In this paper we present a
general methodology for the transformation of unbounded register
protocols so that they can work with bounded registers in a
self-stabilizing fashion. The applicability of our method is demonstrated
with two examples: spanning tree computation and topology update.
Click here
for proceedings version.
Click here