Self-stabilizing c-wave algorithms for arbitrary networks

【Author】 Karaata, Mehmet Hakan; Alrashed, Ebrahim; Allaho, Mohammad

【Source】COMPUTING

【影响因子】2.420

【Abstract】In this paper, we propose the first self-stabilizing c-wave algorithm for broadcasting large size messages from multiple initiator processes such that every process receives at least one of these messages broadcast by the initiators. The proposed algorithm first splits each message into a sequence of message shares and then broadcasts the message shares in a pipelined manner in order. We then present an improved maximally concurrent self-stabilizing c-wave algorithm called dynamic clusteringc-wavealgorithm that constructs dynamic broadcast trees by allowing a process to dynamically change its parent to a neighbouring process with the most message shares to implement a maximally concurrent broadcasting of large size messages. The improved algorithm is maximally concurrent in the sense that a process is allowed to receive a message share from any neighbouring process with a larger sequence of message shares than its current parent from which it receives message shares in the broadcast trees constructed by the initiators when available. We implemented and experimentally evaluated the c-wave algorithm to compare its message propagation delay to those of the m and the k-wave algorithms. Simulation results show that the proposed algorithm significantly reduces the broadcast propagation delays compared to that of the m and the k-wave algorithms. The improvement is more evident over the m-wave algorithm. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using c-wave algorithms. In addition, the proposed algorithms have applications in blockchain, mobile wireless sensor networks, VANETs and military communication networks.

【Keywords】c-wave; Distributed computing; Multi-node broadcast; m-wave; Self-stabilization; Wave algorithms

【发表时间】

【收录时间】2022-08-28

【文献类型】理论模型

【主题类别】

区块链技术-协同技术-边缘计算