### 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.

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.

## 2 Comments:

hello Please try the following updated web browser,Very handy,Immediately free download!

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

Post a Comment

<< Home