An open modal stabilizing m-wave algorithm for arbitrary networks

doi:10.1016/j.jpdc.2019.01.014

An open modal stabilizing m-wave algorithm for arbitrary networks

2019-06-01

1

PRE

AI

M

Mehmet Hakan Karaata *

DOI：10.1016/j.jpdc.2019.01.014

原文链接

原文求助

摘要

En 中文

A system that operates in multiple input and corresponding operational modes depending on external input is referred to as an open modal (multi-mode) system. An input mode refers to a particular type and pattern of input whereas an operational mode refers to the operational semantics or the specification implemented by an algorithm. An open modal stabilizing system can operate in multiple operational modes and, eventually enters an operational mode depending on its current input mode. Such a system can be viewed as a generalization of the closed single-mode stabilizing systems that do not receive external input and implement a single operational mode upon entering a legitimate configuration. A wave is a distributed execution, often made up of a broadcast phase followed by a feedback phase, requiring the participation of all the system processors before a particular event called decision is taken. Wave algorithms with one initiator such as the 1-wave algorithm (Bui et al., 1999) have been shown to be very efficient for broadcasting messages in networks. However as the network size increases, having a single initiator adversely affects the message delivery times to nodes further away from the initiator. As a remedy, broadcast waves can be initiated by multiple initiator nodes forming a collection of waves covering the entire network to reduce the completion times of broadcasts. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators (Prakash and Singhal, 1994). In this paper, we propose the first open modal stabilizing m-wane (multi-initiator wave) algorithm implementing concurrent waves started by multiple initiator processors. An m-wave is an execution in which a (non-empty) set of processors initiate broadcasts such that each processor in the network receives a broadcast that was initiated in the current m-wave. A broadcast is said to be initiated by a processor, if the processor has received an input and started the broadcast by informing others of this event. Since the algorithm is a modal algorithm, it is capable of operating in multiple operational and input modes, where the operational mode is determined by the input mode. Due to being stabilizing, the algorithm eventually behaves according to its specification, that is, after a delay and possible attempts to complete waves, every initiated m-wave is completed as per its specification. In addition, after stabilization, if the input mode changes, the system remains in a legitimate configuration, however, enters a new operational mode after a delay in which the corresponding broadcast semantics is implemented. (C) 2019 Published by Elsevier Inc.

Keyword:

Multi-node broadcast

m-wave algorithms

Modal systems

Open systems

Stabilization

Wave algorithms

An open modal stabilizing m-wave algorithm for arbitrary networks

摘要

AI总结

期刊

机构

引用论文