Analysis of toggle protocols

Abstract

The paper deals with the problem of managing full and empty slots in a slotted ring network. Two solutions are formally described and proved correct. The first solution is deterministic; it recovers in O(N) round trips after the last error, where N is the number of nodes in the network. The second solution is randomized; the expected number of round trips to recovery after the last error is O(ln N). © 1991 Springer-Verlag.