Computationally efficient fault tolerant ANTS

Abstract

In this paper, we formulate a method to utilize n mobile agents to solve a variant of Ants Nearby Treasure Search problem (ANTS), where an adversary can place treasure at any cell at a distance D from the origin. We devise a method which finds the treasure with the time complex-ity of O(D + D2=n + Df) where D is the Manhattan dis-tance of the treasure from the source and f is the maximum number of failures such that f 2 o(n). The algorithm is specially designed to reduce computation complexity of the distributed system as a whole by efficiently handling fail-ures and also, introducing the elements of parallelism with respect to handling failures. Using our algorithm, we bring down the computation cost/complexity of the system by an order of n, when failures occur, where n is the total number of ants. ANTS problem utilizes the multi-Agent system with self-organization and steering based on a control mechanism which is analogous to the problem of discovering resources that are available to the distributed system. © 2016 ACM.