Zusammenfassung
A token located at some vertex v of a connected, undirected graph G on n vertices is said to be
taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of
the neighbors of v. The authors consider the following problem: Suppose that two tokens are placed on G, and
at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying
to keep the tokens apart as long as possible. What is the expected time M before they meet?
The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing.
Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound.
The authors use a novel potential function argument to show that in the worst case $M = (4/27+o(1))n^3$.
Nutzer