COMPSCI 711 Distributed Systems Assignment 3
Due date: 23:59 22nd October
NOTE: Your answers MUST be entered using a word processor.
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.