src/consensus/consensus-simulation.py.in

   1 #!@PYTHON@
   2 # This file is part of GNUnet
   3 # (C) 2013, 2018 Christian Grothoff (and other contributing authors)
   4 #
   5 # GNUnet is free software: you can redistribute it and/or modify it
   6 # under the terms of the GNU Affero General Public License as published
   7 # by the Free Software Foundation, either version 3 of the License,
   8 # or (at your 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 # Affero General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU Affero General Public License
  16 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 #
  18 # SPDX-License-Identifier: AGPL3.0-or-later
  19
  20 from __future__ import absolute_import
  21 from __future__ import print_function
  22 from __future__ import division
  23 from builtins import str
  24 from builtins import range
  25 from past.utils import old_div
  26 import argparse
  27 import random
  28 from math import ceil, log, floor
  29 from past.builtins import xrange
  30
  31
  32 def bsc(n):
  33     """ count the bits set in n"""
  34     l = n.bit_length()
  35     c = 0
  36     x = 1
  37     for _ in range(0, l):
  38         if n & x:
  39             c = c + 1
  40         x = x << 1
  41     return c
  42
  43
  44 def simulate(k, n, verbose):
  45     assert k < n
  46     largest_arc = old_div(int(2**ceil(log(n, 2))), 2)
  47     num_ghosts = (2 * largest_arc) - n
  48     if verbose:
  49         print("we have", num_ghosts, "ghost peers")
  50         # n.b. all peers with idx<k are evil
  51     peers = list(range(n))
  52     # py2-3 compatible, backwards.
  53     # refer to http://python-future.org/compatible_idioms.html#xrange
  54     info = [1 << x for x in range(n)]
  55
  56     def done_p():
  57         for x in range(k, n):
  58             if bsc(info[x]) < n-k:
  59                 return False
  60         return True
  61     rounds = 0
  62     while not done_p():
  63         if verbose:
  64             print("-- round --")
  65         arc = 1
  66         while arc <= largest_arc:
  67             if verbose:
  68                 print("-- subround --")
  69             new_info = [x for x in info]
  70             for peer_physical in range(n):
  71                 peer_logical = peers[peer_physical]
  72                 peer_type = None
  73                 partner_logical = (peer_logical + arc) % n
  74                 partner_physical = peers.index(partner_logical)
  75                 if peer_physical < k or partner_physical < k:
  76                     if verbose:
  77                         print("bad peer in connection", peer_physical, "--", partner_physical)
  78                     continue
  79                 if peer_logical & arc == 0:
  80                     # we are outgoing
  81                     if verbose:
  82                         print(peer_physical, "connects to", partner_physical)
  83                     peer_type = "outgoing"
  84                     if peer_logical < num_ghosts:
  85                         # we have a ghost, check if the peer who connects
  86                         # to our ghost is actually outgoing
  87                         ghost_partner_logical = (peer_logical - arc) % n
  88                         if ghost_partner_logical & arc == 0:
  89                             peer_type = peer_type + ", ghost incoming"
  90                     new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]
  91                     new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]
  92                 else:
  93                     peer_type = "incoming"
  94                 if verbose > 1:
  95                     print("type of", str(peer_physical) + ":", peer_type)
  96             info = new_info
  97             arc = arc << 1
  98         rounds = rounds + 1
  99         random.shuffle(peers)
 100     return rounds
 101
 102
 103 if __name__ == "__main__":
 104     parser = argparse.ArgumentParser()
 105     parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")
 106     parser.add_argument("n", metavar="n", type=int, help="#(all peers)")
 107     parser.add_argument("r", metavar="r", type=int, help="#(rounds)")
 108     parser.add_argument('--verbose', '-v', action='count')
 109
 110     args = parser.parse_args()
 111     sum = 0.0
 112     for n in range(0, args.r):
 113         sum += simulate(args.k, args.n, args.verbose)
 114     print(old_div(sum, args.r))