Canny financial cryptographers know that connection-oriented protcools like TCP are not up to scratch if you really care about your packets. They are reliable, but that doesn't mean you can rely on them! TCP is only a reliable protocol until it stops, and then it becomes unreliable - there is no way for you to tell whether a dropped connection delivered the data or not. Or, indeed, how many times.
This problem is underwritten by what amounts to a law of computer science called the Coordination Problem. In trying to recall what this was called, I asked Twan van der Schoot, and predictably, he gave me the fullest answer. Here it is, somewhat edited:
The "Law" you are refering to [writes Twan] is the result of the attempt to solve the "Coordination Problem" or "Coordinated Attack Problem", failing in the attempt, and then proving that it cannot be solved. People generally say it is a "folk" problem in the distributed systems community. Paul Syverson attributes the original problem statement to Gray (1978).
Here's the proof. It is very simple and of a rare beauty. The only thing wrong with it is that it needs an indirect method using a reductio ad absurdum argument.
The problem setup:
We have two perfect processes (i.e. which do not fail), say Alice and Bob. Alice and Bob communicate bidirectionally over a channel with transient errors (i.e. an imperfect channel). Can you devise a protocol that guarantees that Alice and Bob both choose the same action a or b?
1. Assume there is such a protocol. And, without loss of generality, assume that it is the shortest one (i.e. the one with the least communication exchanges in either direction).
2a. Assume that Alice just has sent its last message m in the last step of the protocol. At this point in the protocol, Alice's choice of action a or b must be independent of the message m. Alice will not receive any message thereafter. In other words, prior to sending m, Alice already committed to either action a or b independent of message m.
2b. The choice by Bob for either action a or b must be the same as the choice by Alice after receiving message m from Alice, whether Bob received message m or not (message loss). So Bob's commitment to action a or b is also independent of the received message m.
2c. But then sending message m in the last step of the protocol is redundant, and can be dropped. But then we have a protocol which is one step shorter;
4. But then we have a contradiction, because the protocol was the shortest (1). Hence there is no such protocol.
Conclusion: So there is no protocol which solves the coordination problem.
There are more formal proofs, but they require a lot of formal theory. This one I grabbed from "Distributed Systems, 2nd Edition. Sape Mullender ed. Addison-Wesley 1993".
Note, however, that the "coordination attack" fails in an "absolute" sense. If we allow for some probablity thinking, we can at least approximate a solution. And that is why, say, the Internet works :)
Paul Syverson wrote a little monopgraph in 2003 "Logic, Convention, and Common Knowledge; A Conventionalist Account of Logic". Syverson claims that the Coordination Attack can be solved using a combination of logic and game theoretical ideas. I've started reading the book recently and it is laden with philosophy, (epistemic) logic and game theory. So it will take a little time before I'll grasp the basic tennet of the underlying concepts.
TwanPosted by iang at October 15, 2004 02:01 PM | TrackBack