Help me locate a proof about distributed transactions

August 18, 2006 2:09 AM

A while back I was implementing a distributed transaction coordinator, and in the process also learned some of the pertaining theory. The only thing I can remember semi-vividly was a proof showing that you can't synchronize an action between two parties over an unreliable link, but I can't seem to find it any longer. The final step of the proof was something like "thus, if this was possible, you could shorten every conceivable protocol by one step, which reduces all protocols to the zero-step protocol, which is impossible". I'm pretty sure that it's a standard result of computer science, but I'm unable to find the right keywords to locate it. Help?
posted by themel to science & nature (5 comments total)

Are you thinking of the Impossibility of Distributed Consensus With One Faulty Process proof? (PDF) If not, you might find something good here -- Coordination Problems in Distributed Systems (PDF).
posted by beatrice at 2:57 AM on August 18, 2006 [1 favorite]

this is often called the two army problem
posted by paradroid at 7:23 AM on August 18, 2006

Thanks. I was indeed looking for what Dolev and Strong refer to as the Chinese Generals Problem or its relative, the Atomic Commit Problem. Google has thrown lots of information at me, and I'm pretty sure the proof I'm looking for is somewhere in there. Thanks!
posted by themel at 7:54 AM on August 18, 2006

paging paulsc... :-)
posted by baylink at 9:11 AM on August 18, 2006

Thought the Chinese Generals Problem was probably what you were talking about. But it was 3 AM so I figured it was equally likely I was loopy. Been a long time since my theory classes.
posted by beatrice at 1:59 PM on August 18, 2006