Machinations

“Whenever a man has cast a longing eye on offices, a rottenness begins in his conduct.” ~Thomas Jefferson

I want to continue my occasional series about consensus today by talking about leader election.  Actually, it’s going to be the problem of “committee election”, or as it is referred to more fancily, universe reduction.  The problem is basically this: you have a collection of n people, some hidden fraction of which are bad, and you want to elect a small committee of the people such that the fraction of bad people in the committee is not much more than the fraction of bad people in the general population.  The problem is complicated by the fact that there is no trusted outside party that can be used to, e.g.  count up all the votes.  Instead, the problem needs to be solved just through direct communication among the players.  We’ll assume everyone has synchronized clocks and, moreover, that there is a way to broadcast a message to everyone (i.e. a consensus algorithm).

We’ll be interested in the very challenging case where the bad guys are computationally unbounded, i.e. no cryptography!  Why do we torture ourselves like this?  Well there are a few reasons.  First, the intellectual interest in determining exactly what is and is not possible with cryptographic assumptions.  Second, the practical problem of maybe avoiding some of the computational overhead associated with cryptography e.g. setting up a PKI.  Finally, the desire to avoid assumptions about the “hardness” of certain problems, assumptions that may in the end not wind up not being completely correct.

In FOCS 1999, Uri Feige proposed a very clever solution to the committee election problem in his paper “Non-cryptographic Selection Protocols”.  I’m going to simplify the algorithm a bit to make it blog friendly.  So here’s the setup: we have n people, a hidden fraction of whom are bad and we want to elect a committee of these people such that the fraction of bad people in the committee is not much more than the fraction of bad in the general population.  Here’s the algorithm: we put everyone up on a ledge and we put a certain number of large bins under the ledge.  Each person then must jump into a bin.  We tell the good guys to choose their bins independently and uniformly at random.  Then, once everyone has jumped (we give them a fixed amount of time to do so), we take the bin with the smallest number of people in it and select these people as the winners.  The rest of the bins are carted off to the politician recycling center.

Why should this work?  We have no control over what the bad guys do, and moreover we assume they are omniscient and can secretly collude.  Thus, we can expect the bad guys to hem and haw standing on the ledge until all the good guys have jumped, and then carefully decide amongst themselves what bins to jump into in order to try to throw the election.  Except it turns out that there’s really nothing much they can do.  Assume there are x bins and n people and that t of those people are bad.  Then the expected number of good people jumping in each bin is (n-t)/x.  Moreover, if x is chosen carefully, we can show that with high probability, the number of good people in every bin is very closely concentrated around the expected value[1].  But then what is the worst the bad people can do?  The chosen bin will certainly have no more than n/x people in it.  Thus, the chosen bin will have a fraction of good people in it that is very close to the fraction of good people in the general population.

So that’s the idea.  Cool no?  Much of the technical challenge of Feige’s paper is showing how you can extend this idea to choose a single leader, so that this leader has probability of being bad no more than a fixed constant.  The paper is a good read so I won’t reveal any of the details of how to do this.  Also I want to point out that Feige’s algorithm is a critical tool in many of the modern consensus algorithms.  But doesn’t his algorithm require a consensus algorithm in order to announce bin choices for each person?  Yes, the trick is to use his algorithm among small groups where consensus is not that costly and then to create a kind of tournament network to eventually elect a very small representative group after running many election protocols in parallel.

[1] For example, let t = n/3 and x = n/(log n).  Then Chernoff bounds and a union bound show that with probability that goes to 1 as n gets large, the number of good players in every bin is between (1-epsilon) and (1+epsilon) times (2/3)log n.