Analysis of toggle protocols

Summary 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 inO(N) round trips after the last error, whereN 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 isO(lnN). Jan Pachl works at IBM Zurich Research Laboratory. Previously he worked at BNR in Ottawa and at the University of Waterloo. His interests include communication protocols, distributed systems, skiing and loud music.