Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs

Abstract

We consider a problem of decentralized exploration of a faulty network by several simple, memoryless agents. The model we adopt for a network is a directed graph. We design an asynchronous algorithm that can cope with failures of network edges and nodes. The algorithm is self-stabilizing in the sense that it can be started with arbitrary initializations and scalable -new agents can be added while other agents are already running.