DISTRIBUTED SYSTEMS : COMP3008J
Exercise Sheet 4
Assignment 4
! This is a graded assignment and it is worth 20% of your final grade.
1. Figure 1 shows some processes organised into a logical ring, in which messages travel clockwise). Process 28 was previously the coordinator. Process 15 notices that the previous coordinator has failed and begins an election to elect a new coordinator using the Ring Algorithm.
a. Show all the messages sent as part of the election. E.g. ¡°4 sends ¡®elect(4)¡¯ to 17¡±. (4points)
b. What is the bandwidth (measured in messages)? (1point)
c. What is the turnaround time (measured in serialised messages)? (1point)
3
1
17
11
15
7
9
28
24
Figure 1: Processes in a Ring
2. Given the processes in Figure 1 (ignoring the logical ring), if process 15 notices the failure of the coordinator and holds an election using the Bully Algorithm instead:
Dr. Anca Jurcut
What is the bandwidth (measured in messages)? (1 point)
What is the turnaround time (measured in serialised messages)? (1point)
Page 1
a.
b.
Show all the messages sent as part of the election. E.g. ¡°4 sends ¡®elect(4)¡¯ to 17¡±. (4points)
c.
10
4
DISTRIBUTED SYSTEMS : COMP3008J
Exercise Sheet 4
3. Following the election above, a new coordinator has been elected. Now processes 9 and 17 wish to enter a critical region at the ¡°same time¡± (although 9 requests this slightly earlier). Using a centralised algorithm for mutual exclusion, show all the messages sent so that 9 and 17 be allowed enter and leave the critical region. Your answer should indicate when they enter the critical region. (4points)
4. Do the same as for question 3, except use Distributed Mutual Exclusion. We assume 9 sends a message with a timestamp ¡°10¡± whereas 17 sends a message with a timestamp ¡°12¡±. (4points)
Total Points: 20
* Please submit your answers to Brightspace before Monday at 10am Irish time, Oct. 26th.
Dr. Anca Jurcut Page 2