COMPSCI 711 Distributed Systems Assignment 3 Due date: 23:59 22nd October NOTE: Your answers MUST be entered using a word processor. </br>Q1 [2 marks] Which kind of logical time system do you need if you are required to develop an auditing system to monitor and analyze the execution of a distributed system develop a broadcast scheme for ensuring all the components in the distributed system receive the broadcast message in the same order. You must provide sufficient justification/examples for your answer. Q2 [3 marks] The implementation of the virtual synchrony discussed in our lecture assumes that no failure occurs during the view change. Augment the scheme so that it can cope with failures during the view change. It can be assumed that at most one failure occurs during a view change. You must provide a description of the modified scheme and justify why your scheme satisfies virtual synchrony. Q3 [3 marks] Assume that a task might crash in Raymond’s algorithm discussed in the lecture. Augment Raymond's algorithm to make it tolerate task crashes. It should be assumed that a task re-starts immediately after a crash and the state on the crashed task is lost. Hint: Consider how the crashed task rebuilds its states after it re-starts. Q4 [2 marks] Assume that we are running a computation that consists of several tasks. The tasks are distributed across the machines in a distributed system. Each task only knows the location of the tasks that it communicates with. Suppose we want to find out the CPU load information on each of the machines hosting the tasks. Outline an algorithm that finds the CPU load information from all the machines that host the execution of the tasks. Q5 [2 marks] Assume that the algorithm for collecting cyclic garbage discussed in our lecture works as a complement to the weighted reference counting garbage collection algorithm. Describe a mechanism that allows us to know whether the probes used in the cyclic garbage collection have reached an object through all the predecessors of the object. You should describe the principle as well as the detailed procedure of the mechanism. Q6 [2 marks] For some systems, the Chandy-Lamport algorithm can be modified so that all the channel states are recorded as empty. Which property do these systems need to possess and how Chandy- Lamport algorithm should be modified so that the algorithm does not need to record the channel state? Describe how the modified algorithm works. Q7 [2 marks] • In the Paxos algorithm, after an acceptor has received the accept request message from a proposer, can the acceptor ignore the prepare request message with a larger version number that is sent by a different proposer? You must clearly describe the reason behind your answer. • Paxos uses version numbers to help the acceptors to decide whether they should respond to a received prepare request message. Assume that we have modified the algorithm. In the modified algorithm, the version numbers are not used by the algorithm, and, whenever an acceptor receives a prepare request message, it always participates in the run of the algorithm initiated by the proposer that sends the prepare request message. Use an example to explain why version numbers are important in preventing some possible deadlock/livelock situations during the first phase of the algorithm. In your answer, you must clearly describe the scenario in which a deadlock/livelock occurs. Submission Please convert your file to a PDF file and name your file as upi.pdf where upi is your university login ID, e.g. jbon007.pdf. Submit the file through Canvas. NO email submission will be accepted.
欢迎咨询51作业君