Chapter 23 Distributed computations
Objectives
To introduce and criticise distributed algorithms and protocols. To constantly bear in mind the fundamental characteristics of Distributed systems introduced in Section 5.5.
Points to emphasise
- The basic algorithms are easy to describe. The difficulty comes from considering that any component can fail at any time and we can’t tell whether failure of a message to arrive is due to failure of the network or the sender or congestion.
- If a distributed algorithm replaces a single bottleneck with n bottlenecks it’s useless.
- The basic assumptions of the algorithms may be that the number and identity of participants is known to all of them. One should then consider how this can be varied in response to failure, network partitions, members leaving and joining.
Possible difficulties
The implementation of causal ordering of message delivery, Section 22.4, is difficult. A thorough treatment needs a mathematical basis. The solution presented is based on the assumption that we have a stable process group and everyone sees all the messages.
Teaching hints
- Some algorithms e.g. quorum assembly, depend on the number of participants.
Starting with process groups helps to establish this.
- Note the layering in the Section 22.4 on ordering the delivery of messages. messages arrive at a node but may be queued at a low level and delivered later to the application after other messages.
- Distributed mutual exclusion should start with a discussion of applications where processes each need a copy of the code and where it may reasonable be distributed - i.e. object managers may handle the critical sections.