On a random walk problem arising in self-stabilizing token management
Prasad Tetali, Peter M. Winkler · 1991
We show that the token management protocol proposed by Israeli and Jalfon in PODC '90 self-stabilizes in polynomial time.The protocol makes use of accidental meetings in random walks to reduce a multiplicity of tokens to only one.In an abstract setting, our theorem reads as follows:Let two tokens be placed on vertices of a connected, undirected, n-vertex graph.Suppose that at each tick of a clock a "schedule demon" points to one of the tokens, which then takes a random step to a neighboring vertex.Then, regardless of the demon's strategy, the tokens will meet in expected time at most 8n3/27.Our proof technique makes novel use of a potential function on pairs of vertices, a "remoteness" ordering and a random walk identity, all of which may be of independent theoretical interest.