×
Pachl, Jan

Analysis of toggle protocols. (English) Zbl 0723.68016

Distrib. Comput. 5, No. 1, 25-35 (1991).
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 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).

Cited in 1 Document

MSC:

68M10 Network design and communication in computer systems

Keywords:

protocol; randomization; ring network
PDF BibTeX XML Cite
\textit{J. Pachl}, Distrib. Comput. 5, No. 1, 25--35 (1991; Zbl 0723.68016)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Bain LJ: Statistical analysis of reliability and life-testing models. Dekker, New York 1978 · Zbl 0419.62076
[2] Cohen R, Segall A: An efficient reliable ring protocol. Manuscript (1989)
[3] Dijkstra EW: Self-stabilizing systems in spite of distributed control. Commun ACM 17:643–644 (1974) · Zbl 0305.68048
[4] Pachl J, Casey L: A robust ring transmission protocol. Comput Networks ISDN Syst 13:313–321 (1987)
[5] Pachl J: Livelocks in slotted ring networks. Proc IEEE INFOCOM 88 Conference (March 29–31, 1988, New Orleans, Louisiana), pp 174–179
[6] Pachl J: Analysis of a nearly robust protocol for slotted ring networks. IBM Res Rep RZ 1854 (1989)
[7] Ross SM: Stochastic processes. Wiley. 1983
[8] Wilkes MV, Wheeler DJ: The Cambridge digital communication ring. In: Meisner NB, Rosenthal R (ed) Proc of the LAN Symposium (May 1979, Boston, Mass.), pp 47–61
[9] Wheeler DJ: The livelock-free protocol of the Cambridge Ring. Comput J 32: 95 (1989)
[10] Zafiropulo P, Rothauser EH: Signalling and frame structures in highly decentralized loop systems. Proc 1 st Int Conf on Computer Communications (October 24–26, 1972, Washington, DC), pp 309–315
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.