Affiliations: The Johns Hopkins University, Baltimore, MD, USA | Northeastern University, Boston, MA, USA | School of Engineering and Applied Science, Washington University in St Louis, Campus Box 1115, One Brookings Drive, St Louis, Missouri 63130-4899, USA
Note: [] The ideas in this paper were first described in an extended abstract that appeared in the 32nd IEEE Symposium on Foundations of Computer Science, October 1991.
Note: [] Supported by Air Force Contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K-0171, NSF contract CCR8611442, and a special grant from IBM.
Note: [] Supported by ONR contract N00014-85-K-0168, by NSF grants CCR-8915206, and by DARPA contracts N00014-89-J-1988.
Note: [] Corresponding author, Tel.: +1 314 935 6106, E-mail: [email protected]. Supported by NSF Research Grant NCR-9405444; part of this work was done while the author was at Lab. for Computer Science, MIT.
Abstract: Self-stabilizing protocols must begin operating correctly even when started from an arbitrary state. The end-to-end problem is to ensure reliable message delivery across an unreliable network under the weakest possible guarantee from the network – that the sender and receiver are never separated by a cut of permanently failed links. In this paper we present the first self-stabilizing end-to-end protocol. Our solution has message complexities comparable with the best known non-stabilizing solutions. Our solution also has good stabilization time complexity: the time for the protocol to stabilize has the same complexity as the time the protocol takes to deliver a message.
