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