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