consensus-simulation.py

Go to the documentation of this file.

#!/home/buildbot/bb-worker/sandbox/bin/python
# This file is part of GNUnet
# (C) 2013, 2018 Christian Grothoff (and other contributing authors)
#
# GNUnet is free software: you can redistribute it and/or modify it
# under the terms of the GNU Affero General Public License as published
# by the Free Software Foundation, either version 3 of the License,
# 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
# Affero General Public License for more details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
# SPDX-License-Identifier: AGPL3.0-or-later
 
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 = list(range(n))
    info = [1 << x for x in range(n)]
 
    def done_p():
        for x in range(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 range(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 range(0, args.r):
        sum += simulate(args.k, args.n, args.verbose)
    print(sum // args.r)