GNUnet  0.11.x
consensus-simulation.py
Go to the documentation of this file.
1 #!/home/buildbot/bb-worker/sandbox/bin/python3
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 import argparse
21 import random
22 from math import ceil, log, floor
23 
24 
25 def bsc(n):
26  """ count the bits set in n"""
27  l = n.bit_length()
28  c = 0
29  x = 1
30  for _ in range(0, l):
31  if n & x:
32  c = c + 1
33  x = x << 1
34  return c
35 
36 
37 def simulate(k, n, verbose):
38  assert k < n
39  largest_arc = int(2**ceil(log(n, 2))) // 2
40  num_ghosts = (2 * largest_arc) - n
41  if verbose:
42  print("we have", num_ghosts, "ghost peers")
43  # n.b. all peers with idx<k are evil
44  peers = list(range(n))
45  info = [1 << x for x in range(n)]
46 
47  def done_p():
48  for x in range(k, n):
49  if bsc(info[x]) < n - k:
50  return False
51  return True
52 
53  rounds = 0
54  while not done_p():
55  if verbose:
56  print("-- round --")
57  arc = 1
58  while arc <= largest_arc:
59  if verbose:
60  print("-- subround --")
61  new_info = [x for x in info]
62  for peer_physical in range(n):
63  peer_logical = peers[peer_physical]
64  peer_type = None
65  partner_logical = (peer_logical + arc) % n
66  partner_physical = peers.index(partner_logical)
67  if peer_physical < k or partner_physical < k:
68  if verbose:
69  print(
70  "bad peer in connection", peer_physical, "--",
71  partner_physical
72  )
73  continue
74  if peer_logical & arc == 0:
75  # we are outgoing
76  if verbose:
77  print(peer_physical, "connects to", partner_physical)
78  peer_type = "outgoing"
79  if peer_logical < num_ghosts:
80  # we have a ghost, check if the peer who connects
81  # to our ghost is actually outgoing
82  ghost_partner_logical = (peer_logical - arc) % n
83  if ghost_partner_logical & arc == 0:
84  peer_type = peer_type + ", ghost incoming"
85  new_info[peer_physical] = new_info[peer_physical] | info[
86  peer_physical] | info[partner_physical]
87  new_info[partner_physical
88  ] = new_info[partner_physical] | info[
89  peer_physical] | info[partner_physical]
90  else:
91  peer_type = "incoming"
92  if verbose > 1:
93  print("type of", str(peer_physical) + ":", peer_type)
94  info = new_info
95  arc = arc << 1
96  rounds = rounds + 1
97  random.shuffle(peers)
98  return rounds
99 
100 
101 if __name__ == "__main__":
102  parser = argparse.ArgumentParser()
103  parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")
104  parser.add_argument("n", metavar="n", type=int, help="#(all peers)")
105  parser.add_argument("r", metavar="r", type=int, help="#(rounds)")
106  parser.add_argument('--verbose', '-v', action='count')
107 
108  args = parser.parse_args()
109  sum = 0.0
110  for n in range(0, args.r):
111  sum += simulate(args.k, args.n, args.verbose)
112  print(sum // args.r)
def simulate(k, n, verbose)
static int list
Set if we should print a list of currently running services.
Definition: gnunet-arm.c:69