[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

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

To: or-dev@xxxxxxxxxxxxx
Subject: Re: Proposal: More robust consensus voting with diverse authority sets
From: "Nikita Borisov" <nikita@xxxxxxxx>
Date: Wed, 2 Apr 2008 07:33:28 -0500
Delivered-to: archiver@xxxxxxxx
Delivered-to: or-dev-outgoing@xxxxxxxx
Delivered-to: or-dev@xxxxxxxx
Delivery-date: Wed, 02 Apr 2008 08:33:39 -0400
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=6bzX72s0ehkUvZ8Lj4bTlRm68tRRy5So1rpRWFHSaJg=; b=PhtMCRIeSv1F9KsDluIeR3VaKzUBzVnn9vBbd4lyMccGD7M8BSn8cMetUTTLx0GnG5zkGt0Ktey7/57NloAsxz8cdf1PvxJMBnRKAtdlex/RQPGayn/4AGPHAnUaS8PMeDLGh/Nv1Dm5fFP66gkfqZ/T/v7ZqIsN0gHKkcB90ts=
Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=dVXIqPzXS0jimirt2ysHUspM5Klv0gWBV2v9HLpJJZwusZW9An7Fce2rZIQyLXXRBCfXsic1gXidvQ7yzu0SiiJwUhTc+e/Dpk9hiEYVWzXe3XSzqAVux96jcdhA8PFmEkTshy0Cmo4hJM/dzozNL/lLiFw8wTsnM4E1ZRZeQVQ=
In-reply-to: <20080402085834.GB1590@xxxxxxxxxxxxxxxxxxxx>
References: <20080401150213.GD1693@xxxxxxxxxxxxxxxxxxx> <20080401160235.GT26841@xxxxxxxxxxxxxx> <20080402085834.GB1590@xxxxxxxxxxxxxxxxxxxx>
Reply-to: or-dev@xxxxxxxxxxxxx
Sender: owner-or-dev@xxxxxxxxxxxxx

On Wed, Apr 2, 2008 at 3:58 AM, Peter Palfrader <peter@xxxxxxxxxxxxx> wrote:
> For those reading along at home, such fully connected subgraphs as
>  written about in the procedure are called cliques.
>  See http://en.wikipedia.org/wiki/Clique_problem 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:http://citeseer.ist.psu.edu/pardalos98exact.html>.

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 - http://www.crhc.uiuc.edu/~nikita/
Assistant Professor, Electrical and Computer Engineering
Tel: (217) 244-5385, Office: 460 CSL

References:
- Proposal: More robust consensus voting with diverse authority sets
  - From: Peter Palfrader
- Re: Proposal: More robust consensus voting with diverse authority sets
  - From: Nick Mathewson
- Re: Proposal: More robust consensus voting with diverse authority sets
  - From: Peter Palfrader

Prev by Author: Re: Status of Tor proposals and proposal process (March 2008)
Next by Author: Re: Status of Tor proposals and proposal process (March 2008)
Previous by thread: Re: Proposal: More robust consensus voting with diverse authority sets
Next by thread: Re: Proposal: More robust consensus voting with diverse authority sets
Index(es):
- Author
- Thread