Re: Proposal: More robust consensus voting with diverse authority sets

[Nick Mathewson <nickm@xxxxxxxxxxxxx>]

On Fri, May 02, 2008 at 10:42:41AM +0200, Peter Palfrader wrote:
 [...]
> Then we no longer need to solve maxclique() over the entire graph, but
> we only need to solve maxclique_that_has_point_A_in_it() with A being
> each of the authorities we trust.
> 
> Now maxclique_that_has_point_P_in_it() in itself hard also*, however we
> can make our live easier by limiting the number of authorities that one
> may list.  If we discard votes with too many neighbors early we
> effectively have created a reasonable upper bound for the amount of work
> we have to do while clique finding.

This is quite plausible.  Let's revise the proposal to say this, and
then think about it for a bit to look for more flaws and/or
opportunities.

yrs,
-- 
Nick