Stabilizing communication protocols
- 1 April 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (4) , 448-458
- https://doi.org/10.1109/12.88464
Abstract
A communication protocol is stabilizing if and only if starting from any unsafe state (i.e. one that violates the intended invariant of the protocol), the protocol is guaranteed to converge to a safe state within a finite number of state transitions. Stabilization allows the processes in a protocol to reestablish coordination between one another whenever coordination is lost due to some failure. The authors identify some important characteristics of stabilizing protocols; they show in particular that a stabilizing protocol is nonterminating, has an infinite number of safe states, and has timeout actions. They also propose a formal method for proving protocol stabilization: in order to prove that a given protocol is stabilizing, it is sufficient (and necessary) to exhibit and verify what is called a 'convergence stair' for the protocol. Finally, they discuss how to redesign a number of well-known protocols to make them stabilizing; these include the sliding-window protocol and the two-way handshake.Keywords
This publication has 7 references indexed in Scilit:
- Self-stabilization of the alternating-bit protocolPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Token systems that self-stabilizeIEEE Transactions on Computers, 1989
- Uniform self-stabilizing ringsACM Transactions on Programming Languages and Systems, 1989
- A class of inherently fault tolerant distributed programsIEEE Transactions on Software Engineering, 1988
- Delivery and discrimination: the Seine protocolPublished by Association for Computing Machinery (ACM) ,1988
- The mutual exclusion problemJournal of the ACM, 1986
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974