Analysis of toggle protocols |
| |
Authors: | Jan Pachl |
| |
Affiliation: | (1) IBM Research Division, Zurich Research Laboratory, Säumerstrasse 4, CH-8803 Rüschlikon, Switzerland |
| |
Abstract: | 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. |
| |
Keywords: | Ring network Protocol Randomization Formal proof |
本文献已被 SpringerLink 等数据库收录! |
|