Solutions to homework 1

Notice:
These solutions appear courtesy of the students who wrote them. In observance of Swedish customs their identity is not disclosed.

Q1.

(15 pts)

1.

Mutual exclusion:
Suppose that the process P_i is using the common resource and that the process P_j nevertheless tries to grab the resource. Notice that P_i must have sent the message R_i and received acknowledgments from all other process prior to grabbing the resource; this means that R_i must have been put in P_j's queue. But as P_i still controls the resource, no release message can have been sent, so R_i still resides in P_j's queue. Therefore P_j will only try to grab the resource if R_j is first in P_j' queue; this implies that T_j < T_i which violates the right chronology condition below. We conclude that at most one process can access the resource at a given time.

2.

Right chronology:
As the definition in the problem does not make sense, I will use the following definition: Control over the resource is granted in the same order as the requests were made.

Suppose that P_i and P_j have made requests R_i = (T_i, RR) and R_j = (T_j, RR) with T_i < T_j but P_j nevertheless is granted the resource before P_i is. For this to happen, R_j must be first in P_j's local queue and P_j must have received acknowledgments from all other processes, including P_i, with time stamps later than T_j. But these two conditions cannot be simultaneously satisfied if the channels are FIFO: P_i sent its request R_i before the acknowledgment to P_j was sent, and therefore R_i must have arrived to P_j when the acknowledgment from P_i arrives. But this contradicts the assumption that R_j is first in P_j's local queue -- as T_i < T_j, the first entry in P_j's local queue will be R_i.

3.

Fairness:
Consider a request R_i from P_i. It is put in P_i's local queue at the same time as the requests are sent to all other processes. Suppose that there are k requests, some of which might not have reached P_i, for the resource with earlier time stamp than R_i. Each of these k requests corresponds to a process which grabs the resource for a finite period of time, so we are done if we can show that some process always will grab the resource if there are pending requests and the resource is free. (Right chronology implies that it suffices to show this.) Of the k requests, one request R_j will have the earliest time stamp T_j. It will therefore occupy the first position in P_j's local queue, so when the acknowledgments have arrived to P_j (and the resource is free), P_j will grab the resource. Thus deadlock cannot occur and it follows that P_i's request R_i eventually will be granted.

Q2.

(10 pts)
We define a correct snapshot to be a set of states of the processes and the channels, such that the state of a channel from P to Q is the sequence of messages, which were sent from P before P recorded its state but had not been received by Q by the time that Q recorded its state.

By the marker sending rule and the assumption that the channels are FIFO, all messages from P reaching Q before the marker from P arrives at Q were sent before P recorded its state. By the marker receiving rule and the same assumption that the channels are FIFO, the sequence of messages reaching Q between the time that Q recorded its state and the time that the marker from P reached Q are recorded as the state of the channel from P to Q. These two statements put together are exactly our definition of a correct snapshot, since P and Q are arbitrary. We have assumed that all messages will eventually reach their destination, otherwise it could be the case that the state of a channel is never determined.

Q3.

(10 pts)
Suppose that all messages take exactly 30 minutes to arrive, or that they never arrive. Also, divide time into rounds of 30 minutes, and require that both A and B always send a message every round. Thus, every round, both A and B also receive a message, or the information that a message was lost. It is quite obvious that if a protocol for coordination exists, so it does with these restrictions.

Now, suppose there is a protocol that makes coordination possible, and suppose this protocol makes both parties decide within r rounds. (With coordination we mean that both A and B decide the same thing, and that the decision is not trivial, i.e., always  or 1, the parity of the date, or whatever.)

Now, the message that is sent from A to B in round r-1 (and is received by B at round r) could be lost or not, and A does not know if it is. So, B's decision can not depend on this message if A and B are to agree. Similarly, A's decision cannot depend on the last message sent from B to A.

Thus, the communication in the last round is not necessary, and there thus is a protocol that would have terminated in r-1 rounds.

By induction we get a protocol that terminates in 0 rounds, and thus must be trivial; this is a contradiction.