Next: Homework 2 Up: Lecture Notes in Theoretical Previous: Routing in Parallel Computers

# Homework 1

Q1.
Consider the notion of total order among events in a distributed system discussed in class, i.e. the time'' associated to an event is the pair where is the logical time of the event and ID denotes the id number of the process where the event occurs (we assume different processes have different ID's). In what follows the time of an event is the associated total order. We are given n processes and 1 resource and wish to find an algorithm for granting the resource which satisfies the following 3 conditions. We assume that channels are FIFO.
1.
Mutual Exclusion. At most one process at a time can access the resource.
2.
Right Chronology. Requests must be granted in the order they are made.
3.
Fairness. If no process holds the resource for ever eventually every request is granted.
Show that the following protocol satisfies the three conditions above. Each process has its own queue of chronologically ordered events.
1.
Requesting a resource: process Pi send the message Ri=(Ti,RR) to all and puts the message in its local queue. Here Ti denotes the time at which Ri is sent while RR stands for request resource''.
2.
Receiving a request: upon receiving Ri process Pj enqueues it and sends a timestamped acknowledgement to Pi.
3.
Grabbing the resource: Pi is granted the resource if and only if (a) Ri is first in its local queue, and (b) it has received a timestamped message from all other processes whose sending time is later than Ti.
4.
Notifying resource release: Pi removes Ri from its local queue and sends a timestamped message resource released'' to all.
5.
Remote resource release: upon receipt of resource released' from Pi, every Pj removes Ri from local queue.
Show that this protocol satisfies the three properties above. Argue precisely but concisely.
Q2.
In class we gave an elegant and economical protocol for taking global snapshots due to Chandy and Lamport. Recall that the underlying topology is a connected graph: each processor sits at a vertex and can send messages to its neighbours. An edge between two processors is called a channel.
• MARKER SENDING RULE FOR A PROCESS P.
Process P records its state and sends a marker to all neighbours. COMMENT: this rule is activated when P wants'' to take a snapshot.
• MARKER RECEIVING RULE FOR A PROCESS Q.
Let c be the channel between P and Q;
if Q has not recorded its state then
begin
Q records its state;
Q records the state of c as empty;
Q sends a marker to all neighbours; end
else Q records the state of c as the sequence of messages received along c after Q's state was recorded and before the marker was received along c.
Give a definition of correct snapshot'' and prove that this protocol correctly computes one. Give a proof which is both correct and concise.
Q3.
THE COORDINATED ATTACK PROBLEM. Two allied armies A and B are camped at the bottom of a hill, while a third enemy army is camped at the top. After evaluating the situation the generals of the A and B armies resolved that if they attacked simultaneously they would overrun the enemy, whereas if they did so separately they would be vanquished. To achieve coordination both A and B can rely on messengers. Messengers are guaranteed to reach the other camp within half an hour (i.e. the system is synchronous), but they can fall victims of ambushes and hence their delivery is not guaranteed (i.e. channels are not secure). The problem faced by the two allied armies is to agree on a time to attack simultaneously. Show that such a coordination is impossible.

Next: Homework 2 Up: Lecture Notes in Theoretical Previous: Routing in Parallel Computers
Viggo Kann
Sat Dec 20 23:41:16 MET 1997