Autonomous Node Type Identification in Distributed and Asynchronous Networks

Abstract

This paper addresses the problem of enabling each node in a distributed network over a directed graph to autonomously determine its node type and the associated topological information, and to independently terminate its computation, all through asynchronous communication with neighboring nodes. To this end, we introduce the notions of leader and follower nodes, and for each leader node, define a set of topologically related nodes, referred to as the leader set. We develop several graph-theoretic criteria for identifying node types and leader sets, which are rigorously analyzed to provide topological insight into their applicability. Based on these criteria, we design a fully distributed algorithm that operates under asynchronous inter-node communication without global coordination. In the proposed algorithm, once each node identifies its node type and leader set, it sends instruction messages to its neighbors such that the identifications of its neighboring nodes are accelerated and early algorithm termination of the node is inferred to its neighboring nodes. We prove that it enables all nodes to determine their roles and leader sets within finite time. Simulation results validate the proposed approach and demonstrate the effectiveness and scalability of the algorithm in representative network scenarios. © 1963-2012 IEEE.