Distributed Systems - Assignment
- Two processes P and
Q are connected in a ring using two channels, and they constantly
rotate a message m. At one time, there is only one copy of
m in the system. Each process's state consists of the number
of times it has received m, and P sends m first. At
a certain point, P has the message and its state is 101. Immediately
after sending m, P initiates the snapshot algorithm.
- Explain the operation of the
algorithm in this case, giving the possible global state(s) reported
- The following figure shows
events occuring for each of two processes, p1 and p2.
Arrows between processes denote message transmission.
- Draw and label the lattice
of consistent states (p1 state, p2 state), beginning
with the initial state (0,0).
- Jones is running a collection
of processes p1, p2, ...,pN. Each process pi contains
variable vi. She wishes to determine whether all the variables
v1, v2, ...,vN were ever equal in the course of the execution.
(i) Jones' processes run in
a synchronous system. She uses a monitor process to determine whether
the variables were ever equal. When should the application processes
communicate with the monitor process, and what should their messages
(ii) Explain the statement possibly(v1=v2=...=vN).
How can Jones determine whether this statement is true of her execution?
- Is it possible to implement
either a reliable or an unreliable (process) failure detector using
an unreliable communication channel?
- 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?
- In the Bully algorithm, a
recovering process starts an election and will become the new coordinator
if it has a higher identifier than the current incumbent. Is this
a necessary feature of the algorithm?
- Suggest how to adapt the Bully
algorithm to deal with temporary network partition (slow communication)
and slow processes.