Self-Stabilizing Master-Slave Token Circulation in Unoriented Cactus Graphs

摘要

Token circulation in networks is a fundamental task in the distributed systems. In this paper, we consider selfstabilizing master-slave token circulation in a Cactus graph. Cactus graph is a connected undirected graph where cycles are pairwise edge disjoint. Cactus graphs are being increasingly used in many applications of sensor, ad hoc and other clustered networks, especially when the tree topology is not appropriate. The master-slave model is especially suitable for sensor network or ad hoc networks based on cluster architecture, where a base station or a cluster head has more memory, and is more powerful than other ordinary nodes and can serve as master node (cluster head). The proposed token circulation algorithm for a bidirectional Cactus Graph (1) does not need to know the size of the cactus graph and so, can tolerate dynamic addition and removal of nodes as long as the cactus topology is preserved; (2) works under an unfair distributed daemon (an arbitrary non-empty subset of privileged nodes is selected to move at each step); (3) is a randomized protocol. The algorithm stabilizes in O(n2 log n) steps using an unfair distributed daemon. Most previous randomized protocols for token circulation have assumed only directed graphs.