A Link-failure Resilient Token based Mutual Exclusion Algorithm for Directed Graph Topology

摘要

This paper proposes a new token-based mutual exclusion algorithm for directed graph topology, with or without cycles. In one of our earlier works [1], we have introduced a token based algorithm assuming an inverted tree topology. Such a stable, hierarchical topology is quite unrealistic for mobile networks due to frequent link failures and node mobility. The proposed solution overcomes this. Besides maintaining the correctness in terms of liveness and safety, the proposed algorithm ensures fairness in allocating the token amongst the competing processes. The algorithm offers solution paths even in presence of link failures.