src/consensus/consensus-simulation.py

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