Pacific Institute for the Mathematical Sciences - PIMS

There is an army of generals who want to plan a common attack. Some traitors among them may lie to the others about what they know. Exchanging only messages, what decision-making protocol can the loyal generals use to arrive at a consensus on which plan to adopt? This problem was first posed over thirty years ago, to enable computation in a network where some of the nodes are faulty. Shortly after the problem was formulated, it was shown to be impossible to solve with a deterministic protocol when messages could be arbitrarily delayed. Randomized protocols were soon developed which could solve the problem if a constant fraction less than a third of the generals were traitors, but they required communication exponential in the number of generals. In the years after, much faster protocols were developed but they relied on the assumption that the traitors couldn't know the communications which passed between the loyal generals. In this work we give the first expected time protocol which uses an amount of communication which is polynomial in the number of generals. It succeeds even if the traitors learn all that the loyal generals know, even if the traitors are controlled by a single mastermind, and even if the mastermind may adaptively select the generals to corrupt, based on the current state of the system.

This work suggests that a new level of security is feasible for coordination in a network, without a need for encryption or secrecy. It is to appear in ACM Symposium on the Theory of Computing (STOC) 2013.