Wednesday, February 14, 2007

A Solution to a Distributed Systems Problem

The solution to this puzzle is:

Any protocol that solves this problem is equivalent to one
in which there are rounds of message exchanges: first A (say)
sends to B, next B sends to A, then A sends to B, and so on. We
show that in assuming the existence of a protocol to solve the
problem, we are able to derive a contradiction. This
establishes that no such protocol exists.

Select the protocol that solves the problem using the fewest
rounds. By assumption, such a protocol must exist and, by
construction, no protocol solving the problem using fewer rounds
exists. Without loss of generality suppose that m, the last
message sent by either process, is sent by A.

Observe that the action ultimately taken by A cannot depend on
whether m is recieved by B, because its receipt could never be
learned by A (since it is the last message). Thus, A's choice of
action alpha or beta does not depend on m. Next, observe that the
action ultimately taken by B cannot depend on whether m is
recieved by B, because B must make the same choice of action alpha
or beta even if m is lost (due to channel failure).

Having argued that the action chosen by A and B does not depend on
m, we conclude that m is superfluous. Thus, we can construct a new
protocol in which one fewer message is sent. However, the existence
of such a shorter protocol contradicts the assumption that our
original protocol used the fewest number of rounds.

1 Comments:

Blogger Unknown said...

Isn't this the famous two army problem in communications? I remember studying that in Tanenbaum's book.

5:35 AM  

Post a Comment

<< Home