src/consensus/consensus-simulation.py

   1 #!/usr/bin/python\r
   2 # This file is part of GNUnet\r
   3 # (C) 2013 Christian Grothoff (and other contributing authors)\r
   4 #\r
   5 # GNUnet is free software; you can redistribute it and/or modify\r
   6 # it under the terms of the GNU General Public License as published\r
   7 # by the Free Software Foundation; either version 2, or (at your\r
   8 # option) any later version.\r
   9 #\r
  10 # GNUnet is distributed in the hope that it will be useful, but\r
  11 # WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  13 # General Public License for more details.\r
  14 #\r
  15 # You should have received a copy of the GNU General Public License\r
  16 # along with GNUnet; see the file COPYING.  If not, write to the\r
  17 # Free Software Foundation, Inc., 59 Temple Place - Suite 330,\r
  18 # Boston, MA 02111-1307, USA.\r
  19 \r
  20 import argparse\r
  21 import random\r
  22 from math import ceil,log,floor\r
  23 \r
  24 def bsc(n):\r
  25   """ count the bits set in n"""\r
  26   l = n.bit_length()\r
  27   c = 0\r
  28   x = 1\r
  29   for _ in range(0, l):\r
  30     if n & x:\r
  31       c = c + 1\r
  32     x = x << 1\r
  33   return c\r
  34 \r
  35 def simulate(k, n, verbose):\r
  36   assert k < n\r
  37   largest_arc = int(2**ceil(log(n, 2))) / 2\r
  38   num_ghosts = (2 * largest_arc) - n\r
  39   if verbose:\r
  40     print "we have", num_ghosts, "ghost peers"\r
  41   # n.b. all peers with idx<k are evil\r
  42   peers = range(n)\r
  43   info = [1 << x for x in xrange(n)]\r
  44   def done_p():\r
  45     for x in xrange(k, n):\r
  46       if bsc(info[x]) < n-k:\r
  47         return False\r
  48     return True\r
  49   rounds = 0\r
  50   while not done_p():\r
  51     if verbose:\r
  52       print "-- round --"\r
  53     arc = 1\r
  54     while arc <= largest_arc:\r
  55       if verbose:\r
  56         print "-- subround --"\r
  57       new_info = [x for x in info]\r
  58       for peer_physical in xrange(n):\r
  59         peer_logical = peers[peer_physical]\r
  60         peer_type = None\r
  61         partner_logical = (peer_logical + arc) % n\r
  62         partner_physical = peers.index(partner_logical)\r
  63         if peer_physical < k or partner_physical < k:\r
  64           if verbose:\r
  65             print "bad peer in connection", peer_physical, "--", partner_physical\r
  66           continue\r
  67         if peer_logical & arc == 0:\r
  68           # we are outgoing\r
  69           if verbose:\r
  70             print peer_physical, "connects to", partner_physical\r
  71           peer_type = "outgoing"\r
  72           if peer_logical < num_ghosts:\r
  73             # we have a ghost, check if the peer who connects\r
  74             # to our ghost is actually outgoing\r
  75             ghost_partner_logical = (peer_logical - arc) % n\r
  76             if ghost_partner_logical & arc == 0:\r
  77               peer_type = peer_type + ", ghost incoming"\r
  78           new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]\r
  79           new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]\r
  80         else:\r
  81           peer_type = "incoming"\r
  82         if verbose > 1:\r
  83           print "type of", str(peer_physical) + ":", peer_type\r
  84       info = new_info\r
  85       arc = arc << 1;\r
  86     rounds = rounds + 1\r
  87     random.shuffle(peers)\r
  88   return rounds\r
  89 \r
  90 if __name__ == "__main__":\r
  91   parser = argparse.ArgumentParser()\r
  92   parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")\r
  93   parser.add_argument("n", metavar="n", type=int, help="#(all peers)")\r
  94   parser.add_argument("r", metavar="r", type=int, help="#(rounds)")\r
  95   parser.add_argument('--verbose', '-v', action='count')\r
  96 \r
  97   args = parser.parse_args()\r
  98   sum = 0.0;\r
  99   for n in xrange (0, args.r):\r
 100     sum += simulate(args.k, args.n, args.verbose)\r
 101   print sum / args.r;\r
 102 \r
 103 \r