Reliable Communication Over Unreliable Channels
Layered communication protocols frequently implement a FIFO message facility on top of an unreliable non-FIFO service such as that provided by a packet-switching network. This paper investigates the possibility of implementing a reliable message layer on top of an underlying layer that can lose pack...
| Main Authors: | , , , , , , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149174 |
| _version_ | 1811076874214834176 |
|---|---|
| author | Afek, Yehuda Attiya, Hagit Fekete, Alan Fischer, Michael Lynch, Nancy A. Mansour, Yishay Wang, Da-Wei Zuck, Lenore |
| author_facet | Afek, Yehuda Attiya, Hagit Fekete, Alan Fischer, Michael Lynch, Nancy A. Mansour, Yishay Wang, Da-Wei Zuck, Lenore |
| author_sort | Afek, Yehuda |
| collection | MIT |
| description | Layered communication protocols frequently implement a FIFO message facility on top of an unreliable non-FIFO service such as that provided by a packet-switching network. This paper investigates the possibility of implementing a reliable message layer on top of an underlying layer that can lose packets and deliver them out of order, with the additional restriction that the implementation uses only a fixed finite number of different packets. A new formalism is presented to specify communication layers and their properties, the notion of their implementation by I/O automata, and the properties of such implementations. An I/O automaton that implements a reliable layer over an unreliable layer is presented. In this implementation, the number of packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur. A proof is given that no protocol can avoid such performance degradation. |
| first_indexed | 2024-09-23T10:29:23Z |
| id | mit-1721.1/149174 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:29:23Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491742023-03-30T04:01:24Z Reliable Communication Over Unreliable Channels Afek, Yehuda Attiya, Hagit Fekete, Alan Fischer, Michael Lynch, Nancy A. Mansour, Yishay Wang, Da-Wei Zuck, Lenore Layered communication protocols frequently implement a FIFO message facility on top of an unreliable non-FIFO service such as that provided by a packet-switching network. This paper investigates the possibility of implementing a reliable message layer on top of an underlying layer that can lose packets and deliver them out of order, with the additional restriction that the implementation uses only a fixed finite number of different packets. A new formalism is presented to specify communication layers and their properties, the notion of their implementation by I/O automata, and the properties of such implementations. An I/O automaton that implements a reliable layer over an unreliable layer is presented. In this implementation, the number of packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur. A proof is given that no protocol can avoid such performance degradation. 2023-03-29T14:34:51Z 2023-03-29T14:34:51Z 1992-10 https://hdl.handle.net/1721.1/149174 27929931 MIT-LCS-TM-447 application/pdf |
| spellingShingle | Afek, Yehuda Attiya, Hagit Fekete, Alan Fischer, Michael Lynch, Nancy A. Mansour, Yishay Wang, Da-Wei Zuck, Lenore Reliable Communication Over Unreliable Channels |
| title | Reliable Communication Over Unreliable Channels |
| title_full | Reliable Communication Over Unreliable Channels |
| title_fullStr | Reliable Communication Over Unreliable Channels |
| title_full_unstemmed | Reliable Communication Over Unreliable Channels |
| title_short | Reliable Communication Over Unreliable Channels |
| title_sort | reliable communication over unreliable channels |
| url | https://hdl.handle.net/1721.1/149174 |
| work_keys_str_mv | AT afekyehuda reliablecommunicationoverunreliablechannels AT attiyahagit reliablecommunicationoverunreliablechannels AT feketealan reliablecommunicationoverunreliablechannels AT fischermichael reliablecommunicationoverunreliablechannels AT lynchnancya reliablecommunicationoverunreliablechannels AT mansouryishay reliablecommunicationoverunreliablechannels AT wangdawei reliablecommunicationoverunreliablechannels AT zucklenore reliablecommunicationoverunreliablechannels |