A self-stabilizing token circulation with graceful handover on bidirectional ring networks

Abstract

In self-organizing distributed systems in which there is no centralized controller, cooperation of processes and fault-tolerance are crucial. The former can be formalized by process synchronization, which is one of the fundamental problems in concurrent, parallel and distributed computing. The latter can be formalized by self-stabilization. A self-stabilizing distributed algorithm is a class of fault-tolerant distributed algorithms that tolerates a finite number of any kind of transient faults. It can be considered as a self-organizing system because it does not need a globally synchronized initialization nor reset, and the system automatically converges to some legitimate configuration.
In this paper, we propose a self-stabilizing distributed algorithm for a token ring with the graceful handover on bidirectional ring networks with the message-passing communication model. The motivation of this work is to design a protocol, by a formal approach, which is useful for the self-organizing multi-node security camera system that guarantees continuous observation. More specifically, a system consists of several nodes each of which is equipped with a video camera, some of the nodes are active in monitoring, and others are inactive to save energy. The problem is to design an algorithm with the graceful handover of active nodes. That is, at least one node is active at any time, in other words, there is no time instant at which no node is active. This problem is formalized as the mutual inclusion problem, which is a process synchronization problem such that at least one process is in the critical section. To this end, we propose an algorithm for circulating two tokens on bidirectional ring networks under the state-reading model by extending Dijkstra’s self-stabilizing token ring. We also propose the concept of the model gap tolerance property for the graceful handover. The proposed algorithm is self-stabilizing, and it guarantees the graceful handover in message-passing distributed systems.