Self-Stabilizing Periodic Mutual-exclusive Propagation in Sparse Networks

Message propagation is fundamental in constructing distributed systems upon sparsely connected communication networks. For providing easy message propagation primitives, the mutual-exclusive propagation (MEP) of one-bit messages is investigated with a simplified discrete system model. Inspired by natural propagation systems, efficient self-stabilizing periodic MEP processes are proposed with the MEP systems. For handling the worst-case scenarios, the MEP systems are generally analyzed with formal proofs upon arbitrarily connected networks. It shows that the MEP systems can be stabilized with arbitrary initial system states within a short bounded time. Meanwhile, the numeric simulation shows that the propagation errors can be significantly reduced if the message delays are randomly distributed. Propagation patterns are also discussed in further deriving finer propagation results in the MEP systems. It shows that bounded clock drifts and some benign faults can be well handled in the MEP systems. Featured by its very simple mechanism, the proposed MEP primitive can be employed as a practical building block of upper-layer self-stabilizing synchronous systems.
Comment: 12 pages, 7 figures