Proposal: More robust consensus voting with diverse authority sets

Nikita Borisov nikita at
Wed Apr 2 12:33:28 UTC 2008

On Wed, Apr 2, 2008 at 3:58 AM, Peter Palfrader <peter at> wrote:
> For those reading along at home, such fully connected subgraphs as
>  written about in the procedure are called cliques.
>  See for a short overview.
>  Finding the maximum clique is an NP hard problem, but it might just
>  scale to up to our 20 nodes.  There is literature on how to solve it,
>  for instance Steven Murdoch found "An Exact Parallel Algorithm For The
>  Maximum Clique Problem" by  Panos M. Pardalos, Jonas Rappe, Mauricio
>  G.C. Resende - <URL:>.

I've built a max-clique implementation before, and it worked well for
social network graphs on the order of 100, so 20 should be no problem
at all.

- Nikita
Nikita Borisov -
Assistant Professor, Electrical and Computer Engineering
Tel: (217) 244-5385, Office: 460 CSL

More information about the tor-dev mailing list