A more difficult problem.
The processes are asynchronous and may crash (as before). On the network side each directed
pair of processes is connected by a channel that is either fair or unreliable. An unreliable channel
is similar to a fair channel as far as the validity and integrity properties are concerned but has no
termination property. Whatever the number of times a message is sent (even an infinite number
of times), the channel can lose all its messages. So, if an unreliable channel connects pi to pj ,
it is possible that no message sent by pi is ever received by pj on this channel, exactly as if this
channel was missing.
An example of such a network is represented in Fig. 3.5. A black or white big dot represents a
process. A simple arrow from a process to another process represents a fair unidirectional channel. A double arrow indicates that both unidirectional channels connecting the two processes
are fair. All the other channels are unreliable (in order not to overload the figure they are not
represented).
Notion of fair path In order to be able to construct a communication abstraction that, in
any run, allows any pair of non-faulty processes to communicate, basic assumptions on the
connectivity of the non-faulty processes are required. These assumptions are based on the notion
of a fair path. Hence, given an execution, it is assumed that every directed pair of non-faulty
processes is connected by a directed path made up of non-faulty processes and fair channels,
which is known as a fair path.
When considering Fig. 3.5, let the black dots denote the non-faulty processes and the white
dots denote the faulty ones. One can check that every directed pair of non-faulty processes is
connected by a fair path.
What has to be done Considering the previous system mode with very weak connectivity,
design:
• an algorithm implementing a Heartbeat failure detector, and
• an algorithm building URB-broadcast with the help of a Heartbeat failure detector, and a
failure detector of the class Θ.
Solution in [12] (original paper) and in Chapter 4 of the monograph [366].