Fascinating. I've never before heard this classic problem referred to as the "coordination problem". I first read about this problem in this paper by Akkoyunlu, Ekanadham, and Huber, "Some Constraints and Tradeoffs in the design of Network Communications", e.g.:

http://delivery.acm.org/10.1145/810000/806523/p67-akkoyunlu.pdf?key1=806523&key2=7125128311&coll=GUIDE&dl=GUIDE&CFID=66673262&CFTOKEN=44966762

where it isn't given a name but it describes (at the end of the paper) the problem of two groups of gangsters trying to agree to put a plan into action. They present essentially the same proof above.

There has been a fair amount of discussion of the "The Byzantine Generals Problem" paper by Lamport, Shostak, and Pease:

http://delivery.acm.org/10.1145/360000/357176/p382-lamport.pdf?key1=357176&key2=2914128311&coll=GUIDE&dl=GUIDE&CFID=66672184&CFTOKEN=82281844

but after looking again at that paper I think it focused primarily on a different set of problems (n/3 ...) and doesn't deal with the above "coordination problem" directly.

I hope we have some others on the list who are steeped in computer science history and may be able to shed some light on the development of the understanding of this problem and its naming.

--Jed http://www.webstart.com/jed/
_______________________________________________
cap-talk mailing list
http://www.eros-os.org/mailman/listinfo/cap-talk

[Another] discussion led to what I considered an interesting discussion of the "coordination problem" AKA the "Two Generals Problem":

http://en.wikipedia.org/wiki/Two_Generals'_Problem

where I was able to add some clarity to the historical thread as noted on the above Wikipedia page (not self serving in this case ;-).

--Jed http://www.webstart.com/jed/

Hello from Madrid, Spain. I am researching about the Nature of Internet. And translating some problems into Spanish. I have been surfing trying to find the original version of Gray, no sucess. Would you be so kind as to tell me if avalaible?

I know it can be found in:

James Gray "Notes on Data Base Operating Systems"
In Lecture Notes In Computer Science; Vol. 60 "Operating Systems, An Advanced Course" pp 393 - 481
1978 Springer-Verlag London, UK
ISBN:3-540-08755-9

Apparently, Gray called it the "Generals Paradox".

But I don't have a copy of it on my bookshelfs.

In any case I read about the "Two Generals" problem in:
"Distributed Systems - Second Edition"
Edited by Sape Mullender
Addison-Wesley 1993
Section 2.2 Good Models/A Coordination Problem.

Only later I learned the "Coordination problem" originated with Jim Gray.

Great.
Please, find first translation into Spanish of the Generals Paradox here
http://www.ithinksearch.com/searchology/index.php/Problemas_y_Paradojas_Clásicas_de_Search_Filosofía

Also avalaible The problems of Ganster´s and the Go problem.

If you want to send me or write drafs of ideas at this wiki, I will translated them into Spanish.

I am inquiring about using or not a reductio ad absurdum argument for re-thinking these kind problems. Any fuzzy or discrete ideas?

This "old archeology of deep thought stuff" is fascinating.

Thank you very much from Spain!

Hi Nuño Valenzuela,

Great you were able to digg up the original text! Since university I don't have easy access to such archeological material.

Although Gray stated the "Generals Paradox" problem in 1978, the formal proof using the reductio ad absurdam is given by Yemini and Cohen in 1979 [1]

Halpern and Moses provided a proof in 1990 [2] using the notion of "common knowledge". If I'm not mistaken this proof is discussed in Fagin et al from 1995 [3] section 6.1. I don't remember the details of that proof, but it's main line of reasoning doesn't rely on such a reductio. May be a small lemma burrowed deeply in the proof does require the use of reductio, you've to find that out yourself ;-)

In any case, the proof in [3] is much much longer than the one given in [1].

FYI, Paul Syverson claims to have found a solution to the paradox. He needs a booklet [4] to explain it, invoking game theory and epistemic logic.

best regards,

Twan

[1] Y. Yemini and D. Cohen "Some Issues in distributed processes communication" in proc. of the 1st International Conf. on Distributed Computing Systems, pp 199-203.
[2] J.Y. Halpern and Y.Moses "Knowledge and common knowledge in a distributed environment", JACM 37(2), pp549-587.
[3] R. Fagin, J. Y. Halpern, Y. Moses and M. Y. Vardi "Reasoning About Knowledge" MIT-press 1995 (ISBN 0-262-06162-7).
[4] Paul Syverson, "Logic, Convention, and Common Knowledge - A Conventionalist Account of Logic", CLSI publications 2003 (ISBN 1-57586-392-8).