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 $(\rightarrow,ID)$ where $\rightarrow$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 P_i send the message R_i=(T_i,RR) to all and puts the message in its local queue. Here T_i denotes the time at which R_i is sent while RR stands for ``request resource''.

2.

Receiving a request: upon receiving R_i process P_j enqueues it and sends a timestamped acknowledgement to P_i.

3.

Grabbing the resource: P_i is granted the resource if and only if (a) R_i is first in its local queue, and (b) it has received a timestamped message from all other processes whose sending time is later than T_i.

4.

Notifying resource release: P_i removes R_i from its local queue and sends a timestamped message ``resource released'' to all.

5.

Remote resource release: upon receipt of ``resource released' from P_i, every P_j removes R_i 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.