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