A Snap-Stabilizing m-wave Algorithm for Tree Networks

摘要

In this paper, we propose the first efficient, reliable and safe snap-stabilizing $m$-$wave$ (multi-initiator wave) algorithm implementing concurrent waves started by multiple initiator processes in tree networks. Unlike its self-stabilizing counterpart and broadcast algorithms, the proposed algorithm is a reliable and safe $m$-wave algorithm, i.e. it implements an $m$-wave such that after it is started in an arbitrary initial configuration or after faults, the first $m$-wave started is guaranteed to reach all system processes as per its specification. In addition, the proposed $m$-wave algorithm increases the efficiency of the broadcast compared to a $1$-wave algorithm by allowing the broadcast to be initiated by multiple processes. Our proposed algorithm is safe in the sense that after initiating an $m$-wave, it completes as per the specifications. Additionally, it is reliable as the algorithm guarantees that each process receives at least one broadcast from an initiator process. Furthermore, the proposed algorithm significantly reduces the broadcast completion time compared to that of its single counterparts. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators. In addition, the proposed algorithm has applications in mobile wireless sensor networks, VANETs and military communication networks.