COMPSCI 711代写、代写Java，Python语言程序

日期：2021-10-20 11:24

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.