Stabilizing data-link over non-FIFO channels with optimal fault-resilience

Shlomi Dolev (1) , Swan Dubois (2) , Maria Potop-Butucaru (2) , Sébastien Tixeuil (3)

1 Department of Computer Science [Beer-Sheva]
2 Regal - Large-Scale Distributed Systems and Applications
3 NPA - Networks and Performance Analysis

Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels. This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels. We propose a fault-send-deliver optimal stabilizing data-link layer that emulates a reliable FIFO communication channel over unreliable capacity bounded non-FIFO channels.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil. Stabilizing data-link over non-FIFO channels with optimal fault-resilience. [Research Report] ???. 2010. ⟨inria-00536048v2⟩