-#!/usr/bin/python\r
-# This file is part of GNUnet\r
-# (C) 2013 Christian Grothoff (and other contributing authors)\r
-#\r
-# GNUnet is free software; you can redistribute it and/or modify\r
-# it under the terms of the GNU General Public License as published\r
-# by the Free Software Foundation; either version 2, or (at your\r
-# option) any later version.\r
-#\r
-# GNUnet is distributed in the hope that it will be useful, but\r
-# WITHOUT ANY WARRANTY; without even the implied warranty of\r
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\r
-# General Public License for more details.\r
-#\r
-# You should have received a copy of the GNU General Public License\r
-# along with GNUnet; see the file COPYING. If not, write to the\r
-# Free Software Foundation, Inc., 59 Temple Place - Suite 330,\r
-# Boston, MA 02111-1307, USA.\r
-\r
-import argparse\r
-import random\r
-from math import ceil,log,floor\r
-\r
-def bsc(n):\r
- """ count the bits set in n"""\r
- l = n.bit_length()\r
- c = 0\r
- x = 1\r
- for _ in range(0, l):\r
- if n & x:\r
- c = c + 1\r
- x = x << 1\r
- return c\r
-\r
-def simulate(k, n, verbose):\r
- assert k < n\r
- largest_arc = int(2**ceil(log(n, 2))) / 2\r
- num_ghosts = (2 * largest_arc) - n\r
- if verbose:\r
- print "we have", num_ghosts, "ghost peers"\r
- # n.b. all peers with idx<k are evil\r
- peers = range(n)\r
- info = [1 << x for x in xrange(n)]\r
- def done_p():\r
- for x in xrange(k, n):\r
- if bsc(info[x]) < n-k:\r
- return False\r
- return True\r
- rounds = 0\r
- while not done_p():\r
- if verbose:\r
- print "-- round --"\r
- arc = 1\r
- while arc <= largest_arc:\r
- if verbose:\r
- print "-- subround --"\r
- new_info = [x for x in info]\r
- for peer_physical in xrange(n):\r
- peer_logical = peers[peer_physical]\r
- peer_type = None\r
- partner_logical = (peer_logical + arc) % n\r
- partner_physical = peers.index(partner_logical)\r
- if peer_physical < k or partner_physical < k:\r
- if verbose:\r
- print "bad peer in connection", peer_physical, "--", partner_physical\r
- continue\r
- if peer_logical & arc == 0:\r
- # we are outgoing\r
- if verbose:\r
- print peer_physical, "connects to", partner_physical\r
- peer_type = "outgoing"\r
- if peer_logical < num_ghosts:\r
- # we have a ghost, check if the peer who connects\r
- # to our ghost is actually outgoing\r
- ghost_partner_logical = (peer_logical - arc) % n\r
- if ghost_partner_logical & arc == 0:\r
- peer_type = peer_type + ", ghost incoming"\r
- new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]\r
- new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]\r
- else:\r
- peer_type = "incoming"\r
- if verbose > 1:\r
- print "type of", str(peer_physical) + ":", peer_type\r
- info = new_info\r
- arc = arc << 1;\r
- rounds = rounds + 1\r
- random.shuffle(peers)\r
- return rounds\r
-\r
-if __name__ == "__main__":\r
- parser = argparse.ArgumentParser()\r
- parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")\r
- parser.add_argument("n", metavar="n", type=int, help="#(all peers)")\r
- parser.add_argument("r", metavar="r", type=int, help="#(rounds)")\r
- parser.add_argument('--verbose', '-v', action='count')\r
-\r
- args = parser.parse_args()\r
- sum = 0.0;\r
- for n in xrange (0, args.r):\r
- sum += simulate(args.k, args.n, args.verbose)\r
- print sum / args.r;\r
-\r
-\r
+#!/usr/bin/python
+# This file is part of GNUnet
+# (C) 2013 Christian Grothoff (and other contributing authors)
+#
+# GNUnet is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published
+# by the Free Software Foundation; either version 2, or (at your
+# option) any later version.
+#
+# GNUnet is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with GNUnet; see the file COPYING. If not, write to the
+# Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+# Boston, MA 02110-1301, USA.
+
+import argparse
+import random
+from math import ceil,log,floor
+
+def bsc(n):
+ """ count the bits set in n"""
+ l = n.bit_length()
+ c = 0
+ x = 1
+ for _ in range(0, l):
+ if n & x:
+ c = c + 1
+ x = x << 1
+ return c
+
+def simulate(k, n, verbose):
+ assert k < n
+ largest_arc = int(2**ceil(log(n, 2))) / 2
+ num_ghosts = (2 * largest_arc) - n
+ if verbose:
+ print "we have", num_ghosts, "ghost peers"
+ # n.b. all peers with idx<k are evil
+ peers = range(n)
+ info = [1 << x for x in xrange(n)]
+ def done_p():
+ for x in xrange(k, n):
+ if bsc(info[x]) < n-k:
+ return False
+ return True
+ rounds = 0
+ while not done_p():
+ if verbose:
+ print "-- round --"
+ arc = 1
+ while arc <= largest_arc:
+ if verbose:
+ print "-- subround --"
+ new_info = [x for x in info]
+ for peer_physical in xrange(n):
+ peer_logical = peers[peer_physical]
+ peer_type = None
+ partner_logical = (peer_logical + arc) % n
+ partner_physical = peers.index(partner_logical)
+ if peer_physical < k or partner_physical < k:
+ if verbose:
+ print "bad peer in connection", peer_physical, "--", partner_physical
+ continue
+ if peer_logical & arc == 0:
+ # we are outgoing
+ if verbose:
+ print peer_physical, "connects to", partner_physical
+ peer_type = "outgoing"
+ if peer_logical < num_ghosts:
+ # we have a ghost, check if the peer who connects
+ # to our ghost is actually outgoing
+ ghost_partner_logical = (peer_logical - arc) % n
+ if ghost_partner_logical & arc == 0:
+ peer_type = peer_type + ", ghost incoming"
+ new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]
+ new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]
+ else:
+ peer_type = "incoming"
+ if verbose > 1:
+ print "type of", str(peer_physical) + ":", peer_type
+ info = new_info
+ arc = arc << 1;
+ rounds = rounds + 1
+ random.shuffle(peers)
+ return rounds
+
+if __name__ == "__main__":
+ parser = argparse.ArgumentParser()
+ parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")
+ parser.add_argument("n", metavar="n", type=int, help="#(all peers)")
+ parser.add_argument("r", metavar="r", type=int, help="#(rounds)")
+ parser.add_argument('--verbose', '-v', action='count')
+
+ args = parser.parse_args()
+ sum = 0.0;
+ for n in xrange (0, args.r):
+ sum += simulate(args.k, args.n, args.verbose)
+ print sum / args.r;
+
+
projects / oweals / gnunet.git / blobdiff