Stabilization Time for Token Replications in Self-Stabilizing Random Walk Based Distributed Algorithms
Alain Bui, Devan Sohier · 2007
This article presents the first algorithm to compute meeting times in a graph, and illustrates this computation by giving a full analysis of the Israeli and Jalfon random walk based distributed mutual exclusion algorithm. This allows comparisons between this algorithm and others self-stabilizing distributed mutual exclusion algorithm in terms of average times to access the critical resource and stabilization times, and also in terms of message complexity. This can give an objective criterion to the trade-off between time complexity and message complexity.