proof.html

Proof

In granting a request each input considers only cells which are actually requested by outputs. Note that these are the most preferred cells by the outputs. The input grants the request to the output whose requested cell appears first in the input preference list. At the end of the phase, the input transfers the requested cell to the corresponding output.

As an example consider an input that holds three cells b.2, a.1, and b.1 in this order. Assume that both outputs a and b make requests for their most preferred cells, i.e., a.1 and b.1, respectively. As a result, the input will grant the request to a, as a.1 is more preferred than b.1 by the input. (Although b.2 is the most preferred cell by the input this is not considered in the decision process.)

As shown in the paper, to demonstrate that the algorithm works correctly it is sufficient to prove that at the beginning of each time slot t the position of any cell p enqueued at the input is no larger than its rank (see Lemmas 2 & 3), i.e,

rank(p, t) >= pos(p,t)

The proof is by induction. Bellow we give the proof for the induction step.

Consider a cell p destined to output j, enqueued at input i which is not transferred during a phase. Then one of the following three cases holds:

1. input i transfers a more preferred cell

2. output j receives a more preferred cell

3. neither output j nor input i transfer a cell more preferred than p

Since cases 1 and 2 are treated in the paper (see Lemma 3), following we give the proof for case 3.

Let q be the most preferred cell by output j at input i. Next, we show that if the scenario described in case 3 happens, then a cell r more preferred than q (by input) is transferred from input i. Without loss of generality assume that no two cells destined to the same output have the same priority. (If needed these cells can be differentiated based on both the index of the input they arrive and their arrival times.)

Consider two cases, whether (a) a cell less preferred than p is transferred to output j, or (b) no cell is transferred to j.

Case a. Let p' denote the cell transferred to j. Clearly p' cannot belong to i, since the input transfers the most preferred cell of the output, which in this case is q. (Note that since p' is less preferred than p, p' cannot coincide to q.) Thus, p' has to belong to another input. Since p' is less preferred than q by output j, it follows that output j has made a request in a previous round to input i, but was rejected (eventually in a latter round). This can happen only because during that round input i has granted a request to an output asking for a cell more preferred than q (by input i). In the subsequent rounds this request either survives, or it is replaced by a request for a more preferred cell. In either case input i will grant a request to an output k for a cell r that appears before q in the i-th preference list. Since at the end of the phase, cell r will be transferred the proof for this case follows.

Case b. The proof for this case is similar; if no cell is transferred to j then there was a previous round during which j was rejected by i. Using the same reasoning as above it follows that input i will transfer a more preferred cell than q.

Note that if p coincides to q, case 3 reduces to case 1. In the followings we assume that the two cells are different.

Assume p is not transferred during slot t. Then one of the followings scenarios has to be true for cell p:

A. either case 1 or 2 occurs during each phase. This scenario is treated in the paper (see proof of Lemma 3).

B. case 3 occurs in both phases. According to the above proof, this means that a cell more preferred than q was transferred from the input during each phase. Then according to A the invariant will hold for q at t+1, i.e., rank(q, t+1) >= pos(q, t+1). Since q is more preferred than p by the output, while p is more preferred than q by the input, it follows that rank(p, t+1) > pos(p, t+1).

C. case 3 occurs in the first phase; either case 1 or 2 occurs in the second phase. Since q is more preferred than p by the output, while p is more preferred than q by the input, we have rank(p, t) >= rank(q, t), and pos(p, t) < rank(q, t), respectively. Therefore from the induction hypothesis for q we have rank(p, t) >= pos(p,t) +1. Since in the second phase either the rank of p increases by one, or its position decreases by one, the proof follows.

D. either case 1 or 2 occurs in the first phase; case 3 occurs in the second phase. Let q be the most preferred cell of output j at input i during the second phase. The only reason for which q is not transferred during the first phase is because either case 1 or 2 occurs for q. (Case 3 can not occur because this would imply, according to the above proof, that another cell q' more preferred by j was at the input during the first phase. Since cell q' is not transferred during this phase, q could not be the most preferred cell by j in the second phase.) Further, in the second phase a cell more preferred than q is transferred from the input. Then according to A, rank(q, t+1) >= pos(q,t+1). Consequently we have also rank(p, t+1) >= pos(p,t+1).

The proof for the basic step is similar to the proof for the induction step. The only difference is that since the arriving cell is the most preferred by its input, case 1 cannot occur.

Ion Stoica

Last modified: Fri Aug 7 10:19:12 EDT 1998