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