from using this terminology, however, because in this book the words synchronous and
asynchronous will have other meanings throughout (cf.
Section 2.1). When used, as in
Algorithm Task-t, to transmit messages to more than one task, the send operation is
assumed to be able to do all such transmissions in parallel.
The relation of blocking and nonblocking send operations with message buffering
requirements raises important questions related to the design of distributed algorithms. If, on
the one hand, a blocking send requires no message buffering (as the message is passed
directly between the synchronized tasks), on the other hand a nonblocking send requires the
ability of a channel to buffer an unbounded number of messages. The former scenario poses
great difficulties to the program designer, as communication deadlocks occur with great ease
when the programming is done with the use of blocking operations only. For this reason,
however unreal the requirement of infinitely many buffers may seem, it is customary to start
the design of a distributed algorithm by assuming nonblocking operations, and then at a later
stage performing changes to yield a program that makes use of the operations provided by
the language at hand, possibly of a blocking nature or of a nature that lies somewhere in
between the two extremes of blocking and nonblocking send operations.
The use of nonblocking send operations does in general allow the correctness of distributed
algorithms to be shown more easily, as well as their properties. We then henceforth assume
that, in Algorithm Task_t, send operations have a nonblocking nature. Because Algorithm
Task_t is a template for all the algorithms appearing in the book, the assumption of
nonblocking send operations holds throughout. Another important aspect affecting the
design of distributed algorithms is whether the channels in D
T
deliver messages in the FIFO
order or not. Although as we remarked in
Section 1.3 this property may at times be essential,
we make no assumptions now, and leave its treatment to be done on a case-by-case basis.
We do make the point, however, that in the guards of Algorithm Task_t at most one
message can be available for immediate reception on a FIFO channel, even if other
messages have already arrived on that same channel (the available message is the one to
have arrived first and not yet received). If the channel is not FIFO, then any message that
has arrived can be regarded as being available for immediate reception.
1.5 Handling infinite-capacity channels
As we saw in Section 1.4, the blocking or nonblocking nature of the send operations is
closely related to the channels ability to buffer messages. Specifically, blocking operations
require no buffering at all, while nonblocking operations may require an infinite amount of
buffers. Between the two extremes, we say that a channel has capacity k ≥ 0 if the number
of messages it can buffer before either a message is received by the receiving task or the
sending task is suspended upon attempting a transmission is k. The case of k = 0
corresponds to a blocking send, and the case in which k → ∞ corresponds to a nonblocking
send.
Although Algorithm Task_t of
Section 1.4 is written under the assumption of infinite-capacity
channels, such an assumption is unreasonable, and must be dealt with somewhere along
the programming process. This is in general achieved along two main steps. First, for each
channel c a nonnegative integer b(c) must be determined that reflects the number of buffers
actually needed by channel c. This number must be selected carefully, as an improper
choice may introduce communication deadlocks in the program. Such a deadlock is
represented by a directed cycle of tasks, all of which are suspended to send a message on
the channel on the cycle, which cannot be done because all channels have been assigned