[cap-talk] impossibility of solving the "coordinated attack problem" ("generals problem")

Rob J Meijer rmeijer at xs4all.nl
Tue Feb 7 12:17:18 EST 2006


> In the end, it's probabilistic, as Paul Syverson has pointed out (is
> there a link for that?). When you have a vast number of channels (as in
> a face-to-face meeting) the probabilities get so close to 100% you can
> neglect the difference.

With probabilities the solution is actualy quite simple in theory
(although almost as far fetched as the problem description itself).

I'll state it in my clumsy engineer view and recolection of probablistics
so please bare with me here. Maybe one of the academics on the list will
recognize this (school) example and be able to translate it into the
proper description.

You implement the actual actions as probablistic actions, that is make
prommises about the 'current unconditional' probability that you will take
an action and actualy conform to that probability by picking a random
number
to determine wheter to take the action. You can than simply keep on
sending the updated version of this probability (together with your
conditional probabilities) for a pre defined set of messages. If the
protocol length and the conditional probabilities are picked apropriately,
you will end up
with a sufficiently high probability of agreeing on the action and together
taking it.

Having said this, I believe both the problem and the solution are just
basically school stuff, given the fact that there are no real live
examples that I know of of the abouve type of protocol being used for
reliability.
The problem just isn't there in many systems as to warant the use of a
solution as such.

Rob



More information about the cap-talk mailing list