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