Testing the Mega-Merger implementation

To ensure the correctness of the algorithm, we will run a few tests.

Since the problem Mega-Merger solves is topologically independent Distributed Election, we will test the algorithm in a few different scenarios. The network will be of different sizes and shapes, and the proportion of initiators will vary.

The network behavior will be: message ordering, no message loss, random delay based on the network size and unsynchronized clocks.

from random import uniform

from pydistsim.demo_algorithms.santoro2007.mega_merger.algorithm import MegaMergerAlgorithm, ExampleParameters
from pydistsim.network import NetworkGenerator
from pydistsim.network.behavior import NetworkBehaviorModel
from pydistsim.simulation import Simulation

def test_net(net):
    # Numerical parameters: city names and weights are integers
    par = ExampleParameters.numerical_parameters.copy()

    # Randomize the parameters
    par.update({"percentage_of_initiators": uniform(0.1, 1)})

    # Create the simulation object
    sim = Simulation(net, ((MegaMergerAlgorithm, par),))

    # Run the simulation
    sim.run()

    assert all(node.status in MegaMergerAlgorithm.S_term for node in net)
    assert len({node.memory["city"].name for node in sim.network.nodes()}) == 1
    assert len({node for node in sim.network.nodes() if node.status == MegaMergerAlgorithm.Status.ELECTED}) == 1

Ring network

%%time

for n in [1, 10, 40, 100]:
    net = NetworkGenerator.generate_ring_network(n)
    net.behavioral_properties = NetworkBehaviorModel.RandomDelayCommunication
    test_net(net)
    print(f"Test passed for ring network with {n} nodes.")

print("\nAll tests passed for ring networks with 1, 10, 40 and 100 nodes.\n")

Test passed for ring network with 1 nodes.
Test passed for ring network with 10 nodes.
Test passed for ring network with 40 nodes.
Test passed for ring network with 100 nodes.

All tests passed for ring networks with 1, 10, 40 and 100 nodes.

CPU times: user 6.85 s, sys: 0 ns, total: 6.85 s
Wall time: 6.85 s

Complete network

%%time

for n in range(2, 35):
    net = NetworkGenerator.generate_complete_network(n)
    net.behavioral_properties = NetworkBehaviorModel.RandomDelayCommunication
    test_net(net)

print("All tests passed for complete networks with 2 up to 35 nodes.\n")

All tests passed for complete networks with 2 up to 35 nodes.

CPU times: user 9.52 s, sys: 0 ns, total: 9.52 s
Wall time: 9.52 s

Square mesh/grid network

%%time

for n in range(2, 11):
    n = n * n

    net = NetworkGenerator.generate_mesh_network(n)
    net.behavioral_properties = NetworkBehaviorModel.RandomDelayCommunication
    test_net(net)
    print(f"Test passed for square mesh network with {n} nodes.")

print("\nAll tests passed for square mesh networks with 4 up to 121 nodes.\n")

Test passed for square mesh network with 4 nodes.
Test passed for square mesh network with 9 nodes.
Test passed for square mesh network with 16 nodes.
Test passed for square mesh network with 25 nodes.
Test passed for square mesh network with 36 nodes.
Test passed for square mesh network with 49 nodes.
Test passed for square mesh network with 64 nodes.
Test passed for square mesh network with 81 nodes.
Test passed for square mesh network with 100 nodes.

All tests passed for square mesh networks with 4 up to 121 nodes.

CPU times: user 6.26 s, sys: 4.89 ms, total: 6.27 s
Wall time: 6.26 s

Path network (1 x n grid)

%%time

for n in range(2, 51):
    net = NetworkGenerator.generate_mesh_network(a=1, b=n)
    net.behavioral_properties = NetworkBehaviorModel.RandomDelayCommunication
    test_net(net)
    if n % 10 == 0:
        print(f"Test passed for path network with {n} nodes.")

print("\nAll tests passed for path networks with 1 up to 50 nodes.\n")

Test passed for path network with 10 nodes.
Test passed for path network with 20 nodes.
Test passed for path network with 30 nodes.
Test passed for path network with 40 nodes.
Test passed for path network with 50 nodes.

All tests passed for path networks with 1 up to 50 nodes.

CPU times: user 11.1 s, sys: 34.8 ms, total: 11.2 s
Wall time: 11.1 s

Star network

%%time

for n in range(2, 45):
    net = NetworkGenerator.generate_star_network(n)
    net.behavioral_properties = NetworkBehaviorModel.RandomDelayCommunication
    test_net(net)
    if n % 10 == 0:
        print(f"Test passed for star network with {n} nodes.")

print("\nAll tests passed for star networks with 2 up to 44 nodes.\n")

Test passed for ring network with 10 nodes.
Test passed for ring network with 20 nodes.
Test passed for ring network with 30 nodes.
Test passed for ring network with 40 nodes.

All tests passed for ring networks with 2 up to 44 nodes.

CPU times: user 7.53 s, sys: 10 μs, total: 7.53 s
Wall time: 7.53 s