aboutsummaryrefslogtreecommitdiff
path: root/src/consensus/consensus-simulation.py.in
diff options
context:
space:
mode:
Diffstat (limited to 'src/consensus/consensus-simulation.py.in')
-rw-r--r--src/consensus/consensus-simulation.py.in108
1 files changed, 108 insertions, 0 deletions
diff --git a/src/consensus/consensus-simulation.py.in b/src/consensus/consensus-simulation.py.in
new file mode 100644
index 000000000..3ce44cd91
--- /dev/null
+++ b/src/consensus/consensus-simulation.py.in
@@ -0,0 +1,108 @@
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
18from __future__ import absolute_import
19from __future__ import print_function
20import argparse
21import random
22from math import ceil, log, floor
23from past.builtins import xrange
24
25
26def bsc(n):
27 """ count the bits set in n"""
28 l = n.bit_length()
29 c = 0
30 x = 1
31 for _ in range(0, l):
32 if n & x:
33 c = c + 1
34 x = x << 1
35 return c
36
37
38def simulate(k, n, verbose):
39 assert k < n
40 largest_arc = int(2**ceil(log(n, 2))) / 2
41 num_ghosts = (2 * largest_arc) - n
42 if verbose:
43 print("we have", num_ghosts, "ghost peers")
44 # n.b. all peers with idx<k are evil
45 peers = range(n)
46 # py2-3 compatible, backwards.
47 # refer to http://python-future.org/compatible_idioms.html#xrange
48 info = [1 << x for x in xrange(n)]
49
50 def done_p():
51 for x in xrange(k, n):
52 if bsc(info[x]) < n-k:
53 return False
54 return True
55 rounds = 0
56 while not done_p():
57 if verbose:
58 print("-- round --")
59 arc = 1
60 while arc <= largest_arc:
61 if verbose:
62 print("-- subround --")
63 new_info = [x for x in info]
64 for peer_physical in xrange(n):
65 peer_logical = peers[peer_physical]
66 peer_type = None
67 partner_logical = (peer_logical + arc) % n
68 partner_physical = peers.index(partner_logical)
69 if peer_physical < k or partner_physical < k:
70 if verbose:
71 print("bad peer in connection", peer_physical, "--", partner_physical)
72 continue
73 if peer_logical & arc == 0:
74 # we are outgoing
75 if verbose:
76 print(peer_physical, "connects to", partner_physical)
77 peer_type = "outgoing"
78 if peer_logical < num_ghosts:
79 # we have a ghost, check if the peer who connects
80 # to our ghost is actually outgoing
81 ghost_partner_logical = (peer_logical - arc) % n
82 if ghost_partner_logical & arc == 0:
83 peer_type = peer_type + ", ghost incoming"
84 new_info[peer_physical] = new_info[peer_physical] | info[peer_physical] | info[partner_physical]
85 new_info[partner_physical] = new_info[partner_physical] | info[peer_physical] | info[partner_physical]
86 else:
87 peer_type = "incoming"
88 if verbose > 1:
89 print("type of", str(peer_physical) + ":", peer_type)
90 info = new_info
91 arc = arc << 1
92 rounds = rounds + 1
93 random.shuffle(peers)
94 return rounds
95
96
97if __name__ == "__main__":
98 parser = argparse.ArgumentParser()
99 parser.add_argument("k", metavar="k", type=int, help="#(bad peers)")
100 parser.add_argument("n", metavar="n", type=int, help="#(all peers)")
101 parser.add_argument("r", metavar="r", type=int, help="#(rounds)")
102 parser.add_argument('--verbose', '-v', action='count')
103
104 args = parser.parse_args()
105 sum = 0.0
106 for n in xrange(0, args.r):
107 sum += simulate(args.k, args.n, args.verbose)
108 print(sum / args.r)