The University of Melbourne COMP90020: Distributed Algorithms Sample Exam 2020 SM1 Exam Duration: 3 hours Total marks for this exam: 60 Authorised materials: This is an open book assessment. You are allowed to: • Use the textbook, lecture slides, and any other reading materials used or referenced through- out the course. • Use explanations or examples given in the lectures. • Use the solutions given for all the tutorial questions. While you are undertaking this assessment you must not: • Use any messaging or communications technology. • Act in any manner that could be regarded as providing assistance to another student who is undertaking this assessment, or will in the future be undertaking this assessment. The work you submitmust be based on your own knowledge and skills, without assistance from any other person. Instructions to Students: • There are 12 questions in this exam, attempt all of them. • All questions require you to upload a file with your answer. • Write your answer on a sheet of paper, scan or photograph your answer, and upload the corresponding file. • You may answer on any clean, blank paper that you have available. • Alternatively, you can write your answers digitally using a tablet and pen, save the file as a picture, and upload the file as your answer. • Write legibly and be as concise as possible. • For further information on Canvas Quizzes please see: https://students.unimelb.edu.au/your- course/manage-your-course/exams-assessments-and-results/exams/exam-types. 1 Question 1 [3 Marks] Using Cristian’s method for synchronizing clocks where we use a time server, we record the round- trip time and the timestamp returned by the server as 4 sec and 09:55:28 (hh:mm:ss), respectively. (A) What time should we set the local clock to? (1 mark) (B) What is the accuracy of this setting? (1 mark) (C) What is the accuracy of the setting if we know for a fact that the minimum round trip time is 1 second? Show your calculations and notation clearly. Question 2 [3 Marks] Why is the implementation of a reliable failure detector only possible in a synchronous distributed system? Question 3 [6 Marks] Give an example execution of the ring-based mutual exclusion algorithm to show that processes are not necessarily granted entry to the critical section in happened-before order. Question 4 [3 Marks] Consider a set of distributed processes p1, p2, and p3 that use the Ricart and Agrawala’s algorithm for mutual exclusion. Assume that p3 is currently in the critical section (CS) and there is no other process in the WANTED state. (A) Now consider requests from p1 and p2 (in that order) to enter CS. Show the state and queue entries at each process. (1.5 marks) (B) Now, p3 exits the CS and informs all relevant processes that CS is released. Show the state and queue entries at each process, at this stage. (1.5 marks) Question 5 [9 Marks] In a certain system, each process typically uses a critical section many times before another process requires it. Explain why Ricart and Agrawala’s multicast-based mutual exclusion algorithm is inefficient for this case, and describe how to improve its performance. Does your adaptation satisfy liveness condition ME2? Question 6 [3 Marks] In the following reliable multicast algorithm (Figure 1) that we saw in class, explain briefly what would happen if we were to have ‘R-deliver m’ before the ‘if (q 6= p) then…’ statement. 2 Figure 1: Reliable multicast algorithm. Question 7 [6 Marks] The figure below (Figure 2) shows some multicast messages happening for three processes on different machines. Is the ordering of these multicast messages CO, FIFO and/or TO? Explain your answer. Figure 2: Ordered multicast example. 3 Question 8 [6 Marks] Consider a distributed system involving 5 processes, p1, p2, p3, p4 and p5. Process p1 is appointed as the general for this run and its proposed value is a. Process p3 has been hijacked by a hacker, and will relay the value b to processes p2 and p5, and c to the rest. The system does not have a digital signature mechanism. Show that processes p2, p4 , and p5 can still reach an agreement. How many cycles are mandatory for reaching the agreement? Question 9 [6 Marks] For distributed transactions, we discussed the one phase commit protocol. What are the disadvan- tages of this protocol? How can the two phase commit (2PC) protocol overcome these disadvan- tages? Explain your answer. Question 10 [6 Marks] Consider the following wait-for-graph (Figure 3). Show that the system is in a deadlock situation. What is the most efficient way (in terms of number of terminations) to get out of the deadlock? Figure 3: Wait-for-Graph Question 11 [6 Marks] Consider transactions W and Y (Figure 4): Figure 4: Transactions W and Y. show a concurrent execution of these transactions that has a dirty read. 4 Question 12 [3 Marks] Explain how optimistic concurrency control can increase the system concurrency? In what situation optimistic concurrency control fails to enhance the systems throughput? 5
