Proposal: More robust consensus voting with diverse authority sets

[Nick Mathewson]

On Tue, Apr 29, 2008 at 04:14:08PM +0200, Peter Palfrader wrote:
> On Wed, 02 Apr 2008, Nick Mathewson wrote:
> 
> >                                    Is there a simpler approach that
> > does what we want, or do we really need to do the NP-hard thing?
> 
> Did one occur to you yet?  If not, should we go forward with this
> proposal?

All I can think of is providing explicit "flag day" options in the
authority configuration: something to the effect of "before May 1, the
authority list is X; after May 1, the authority list is Y."  This
isn't as powerful as proposal 134 though, and I think it might be less
good than we need.

I decided that I'd eel better about the NP-hard thing if we codde up
the sample C implementation and found out that it scaled well to a
large number of authorities.  ("Scaling well" here means something
like "not replacing RSA as our biggest time-sink in voting", and
"large number of authorities" meaning something far larger than
anything we're hoping to do now.)

To test this, I hacked up a quick and dirty recursive max-clique
implemention in python, to get a handle on scaling issues and
efficiency concerns.  With a little tweaking and a few standard AI
search hacks, I got something that performed fine up to even 50
authorities (which is more than we ever plan to do).  I've attached
the code, in case anybody wants to adopt the approach: basically, it's
a greedy depth-first search with pruning.

So, afaik, the sole remaining big problem in this proposal is
migration.  IIUC, the current consensus-method thing won't work, for
reasons explained in an earlier message of mine on this thread:

   >The 'consensus method' thing is only meant to determine which
   >algorithm the voting authorities use to produce the consensus from the
   >votes, not which authorities' votes count.

Once we solve this, I think building proposal 134 would be a fine
thing to do.

peace,
-- 
Nick
-------------- next part --------------
A non-text attachment was scrubbed...
Name: maxclique.py
Type: text/x-python
Size: 4461 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20080429/8eed65b0/attachment.py>