2.4 Communication Channels

When using the messages passing approach, communication is achieved by transmitting messages on a communication channel, which is a directional link between two processes, i.e. a logical abstraction of the physical medium. A communication from process p to q requires a unidirectional communication channel from p to q. A bidirectional communication channel, also denoted two-way, assume two communication channels: a first from p to q, and a second one from q to p.

A process p sends a message m using the primitive emit at the application layer, which inserts m in its buffer. The buffer of process p sends the message m on the communication channel, which transmits m to the buffer of process q. The latter receives it and delivers it to the application layer of process q. Note that these buffers are typically offered by the operating system.

An example of communication from process p to process q is shown in 2.4.

In the literature, there exist several types of communication channels such as reliable, eventually reliable, fair-lossy, and unreliable [FJR06]. All of them assume the three following common properties.

• No message creation (also called validity [Ray13]): if a process p receives a message from a process q, then q sent it to p.
• No message duplication (also called integrity [Ray13]): if a process p sends a message to a process q, then the process q will receive the message at most one.
• No message alteration: if a process p receives a message from a process q, then the message is exactly the same as the one sent by q, without any modification or corruption.

Each type of communication channel offers different guarantees in terms of message loss.

• Reliable: channels ensure that when a correct process p sends a message to a correct process q, the message will eventually be delivered to q [GR06].
• Eventually reliable: channels assume the existence of a time t after which all messages sent by process p are eventually received by process q. Messages sent before that time t may be lost [BCT96].
• Fair-lossy: channels ensure that when a correct process p sends a message an infinity number of times to a correct process q, then q will deliver the message an infinite number of times [GR06]. This property guarantees that a link does not systematically drop every message.
• Unreliable: also called lossy channels. In this case, messages can be lost, without notifying the processes.

The type of communication channel can also specify bounds for the reception of a message, such as the eventually timely channels or timely channels, or tolerate message loss without any bound, such as lossy asynchronous channels:

• Eventually timely: a link from p to q is eventually timely if it is either a reliable or an eventually reliable channel, satisfying that there exists a bound δ and a time t such that if p sends a message to q at time t and q is correct, then q receives the message from p by time t+δ [Agu⁺04]. Note that if the link is eventually reliable, messages sent before time t can be lost.
• Timely: an eventually timely channel whose bounds hold from t = 0 [Agu⁺04].
• Lossy asynchronous: messages can be arbitrarily delayed (i.e. there is no bound on message delay) or even be lost (an arbitrary number of messages can be lost, if not all) [Agu⁺03; LMS11]. Every message that is not lost is eventually received.

Note that in this thesis, there is no assumption on message ordering, and channels are not required to be FIFO. A FIFO channel stands for First-In First-Out (FIFO), where messages are received to the process by order they were sent.

The different types of communication channels explained previously are summarized in the following 2.3.

Table of Contents