[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Crash resilient communication in dynamic networks

Preliminary version

  • Miscellaneous
  • Conference paper
  • First Online:
Distributed Algorithms (WDAG 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 725))

Included in the following conference series:

Abstract

An end-to-end data delivery protocol for dynamic communication networks is presented. The protocol uses bounded sequence numbers and can tolerate both link failures and processor crashes. Previous bounded end-to-end protocols could not tolerate crashes. A reliable data link layer is not assumed; instead the protocol is designed to work on top of the “bare” network, consisting of nodes connected by FIFO non-duplicating links that can lose messages. Our protocol retransmits messages and uses multiple paths, and thus causes messages to be duplicated and reordered. Yet the data items are delivered without omission or duplication and in FIFO fashion.

This work was supported by NSF Presidential Young Investigator Award CCR-91-58478 and funds from the Texas A&M University College of Engineering.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Y. Afek, H. Attiya, A. Fekete, M. Fischer, N. Lynch, Y. Mansour, D. Wang, and L. Zuck. Reliable Communication Over Unreliable Channels. Technical Report YALEU/DCS/TR-853, Department of Computer Science, Yale University, October 1992.

    Google Scholar 

  2. Y. Afek, B. Awerbuch, and E. Gafni. Applying Static Network Protocols to Dynamic-Networks. In Proc. of the 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 358–370, 1987.

    Google Scholar 

  3. H. Attiya, S. Dolev, and J. Welch. Memory Requirements for Connection Management. Technical Report LPCR #9316, Department of Computer Science, Technion.

    Google Scholar 

  4. B. Awerbuch and S. Even. Reliable Broadcast Protocols in Unreliable Networks. Networks, 16:381–396, 1986.

    Google Scholar 

  5. Y. Afek and E. Gafni. End-to-End Communication in Unreliable Networks. In Proc. of the 7th Annual ACM Symposium on Principles of Distributed Computing, pp. 131–148, 1988.

    Google Scholar 

  6. Y. Afek and E. Gafni. Bootstrap Network Resynchronization: An Efficient Technique for End-to-End Communication. In Proc. of the 10th Annual ACM Symposium on Principles of Distributed Computing, pp. 295–307, 1991.

    Google Scholar 

  7. B. Awerbuch, O. Goldreich, and A. Herzberg. A Quantitative Approach to Dynamic Networks. In Proc. of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pp. 189–203, 1990.

    Google Scholar 

  8. Y. Afek, E. Gafni and A. Rosen. The Slide Mechanism with Applications in Dynamic Networks. In Proc. of the 11th Annual ACM Symposium on Principles of Distributed Computing, pp. 35–46, 1992.

    Google Scholar 

  9. B. Awerbuch, Y. Mansour, and N. Shavit. Polynomial End to End Communication. In Proc. of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 358–363, 1989.

    Google Scholar 

  10. B. Awerbuch and M. Sipser. Dynamic Networks are as Fast as Static Networks. In Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 206–220, 1988.

    Google Scholar 

  11. K. Bartlett, R. Scantlebury, and P. Wilkinson. A Note on Reliable Full-Duplex Transmission over Half-Duplex Links. Communications of the ACM, 12(5):260–261, May 1969.

    Google Scholar 

  12. S. Dolev, and J. Welch. Crash Resilient Communication in Dynamic Networks, Technical Report 93-032, Department of Computer Science, Texas A&M University.

    Google Scholar 

  13. S. G. Finn. Resynch Procedures and a Fail-Safe Network Protocol. IEEE Trans. on Communication, COM-27:840–845, June 1979.

    Google Scholar 

  14. A. Fekete, N. Lynch, Y. Mansour and J. Spinelli, The Impossibility of Implementing Reliable Communication in the Face of Crashes, to appear in Journal of the ACM. Also: Technical Memo MIT/LCS/355.C, Laboratory for Computer Science, Massachusetts Institute of Technology, September 1991.

    Google Scholar 

  15. A. Herzberg. Connection-Based Communication in Dynamic Networks. In Proc. of the 11th Annual ACM Symposium on Principles of Distributed Computing, pp. 13–24, 1992.

    Google Scholar 

  16. D. Wang and L. Zuck, Tight Bounds for the Sequence Transmission Problem. Proc. 8th ACM Symposium on Principles of Distributed Computing, pp. 73–83, 1989.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Texas A&M University, 77843, College Station, Texas, USA

    Shlomi Dolev & Jennifer L. Welch

Authors
  1. Shlomi Dolev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jennifer L. Welch
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

André Schiper

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dolev, S., Welch, J.L. (1993). Crash resilient communication in dynamic networks. In: Schiper, A. (eds) Distributed Algorithms. WDAG 1993. Lecture Notes in Computer Science, vol 725. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57271-6_32

Download citation

  • DOI: https://doi.org/10.1007/3-540-57271-6_32

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-57271-8

  • Online ISBN: 978-3-540-48029-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation