Snap-Stabilization in Message-Passing Systems?

In this paper, we tackle the problem of snap-stabilization in message-passing sys-tems. Snap-stabilization allows to design protocols that withstand transient faults: indeed, any computation that is started after faults cease immediately satisfies the expected specification. Our contribution is twofold: we demonstrate that in message passing systems (i) snap-stabilization is impossible for nontrivial problems if channels are of finite yet unbounded capacity, and (ii) snap-stabilization becomes possible in the same setting with bounded-capacity channels. The latter contribution is constructive, as we propose two snap-stabilizing protocols for propagation of information with feedback and mutual exclusion. Our work opens exciting new research perspectives, as it enables the snap-stabili-zing paradigm to be implemented in actual networks