The Wandering Token: Congestion Avoidance of a Shared Resource

In a distributed system where scalability is an issue, like in a GRID,
the problem of enforcing mutual exclusion often arises in
a soft form: the infrequent failure of the mutual exclusion
predicate is tolerated, without compromising the consistent operation
of the overall system. For instance this occurs when the operation
subject to mutual exclusion requires massive use of a shared resource.

We introduce a scalable soft mutual exclusion algorithm, based
on token passing: one distinguished feature of our algorithm is that
instead of introducing an overlay topology we adopt a random walk
approach.

The consistency of our proposal is evaluated by simulation, and
we exemplify its use in the coordination of large data transfers in a
backbone based network.