{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Visualize the effect of network behavioral properties on distributed algorithms\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"id": "bQX5hbAmIKRO",
"outputId": "10242ef7-4936-4970-9711-0379033b9d30"
},
"outputs": [],
"source": [
"# for interactive plots\n",
"%matplotlib notebook\n",
"\n",
"from pydistsim.network import NetworkGenerator\n",
"from pydistsim.demo_algorithms.broadcast import Flood\n",
"from pydistsim.simulation import Simulation\n",
"from pydistsim.network.behavior import (\n",
" NetworkBehaviorModel,\n",
" random_loss,\n",
")\n",
"\n",
"from pydistsim.gui import drawing as draw\n",
"from IPython.display import HTML"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction\n",
"\n",
"First, we will define the network and the distributed algorithm that we will use to illustrate the effect of network\n",
"properties on distributed algorithms. We will use the **Flood** as the distributed algorithm and a 4 by 4 grid as\n",
"the network.\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"net = NetworkGenerator.generate_grid_network(16)\n",
"sim = Simulation(net, (Flood,))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's create a helper function to visualize the network and the algorithm, with the behavioral properties as a\n",
"parameter. We also define whether or not the visualization will display the internal clock of the nodes.\n"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def make_vid(properties: NetworkBehaviorModel, clock_as_label: bool = False, **kwargs) -> HTML:\n",
" # Set the network behavior properties\n",
" net.behavioral_properties = properties\n",
"\n",
" # Dont interrupt the simulation when a restriction is violated (Total Reliability in this case)\n",
" sim.check_restrictions = False\n",
" sim.reset()\n",
"\n",
" if clock_as_label:\n",
" # Show the clock of each node as a label, for that, we need to pass a lambda function to the node_labels parameter\n",
" kwargs_new = {\"show_labels\": True, \"node_labels\": lambda: {node: node.clock for node in net.nodes}}\n",
" else:\n",
" kwargs_new = {\"show_labels\": False}\n",
"\n",
" kwargs_new.update(kwargs)\n",
"\n",
" # Create the animation\n",
" anim = draw.create_animation(sim, **kwargs_new)\n",
" video = anim.to_html5_video()\n",
"\n",
" return HTML(video)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ideal Communication\n",
"\n",
"First, the simplest scenario is when the network has no loss and no delay. In this case, the algorithm will appear to be\n",
"executing in a synchronous manner.\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_vid(NetworkBehaviorModel.IdealCommunication)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Delay\n",
"\n",
"Now, let's visualize the effect of delay on the distributed algorithm. We will introduce a random delay in every edge of\n",
"the network. The delay will be between 1 and 16 time units.\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# RandomDelayCommunication introduces random delays in the communication, proportional to the size of the network\n",
"make_vid(NetworkBehaviorModel.RandomDelayCommunication)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Loss\n",
"\n",
"Here we will visualize the effect of loss on the distributed algorithm. We will introduce a random loss in every edge of\n",
"the network. The loss will happen with a probability of 0.1.\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# UnlikelyRandomLossCommunication sets the probability of a message being lost to 0.1\n",
"make_vid(NetworkBehaviorModel.UnlikelyRandomLossCommunication)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now increase the loss probability to 0.5. It should be low enough to allow the algorithm to terminate on most\n",
"executions.\n"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Create our own NetworkBehaviorModel, with a message loss probability of 0.5\n",
"make_vid(NetworkBehaviorModel(message_loss_indicator=random_loss(0.5)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we increase the loss probability to 0.7. The algorithm will surely not terminate.\n"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Now with much higher message loss probability\n",
"make_vid(NetworkBehaviorModel(message_loss_indicator=random_loss(0.7)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Clock skew\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we will visualize the effect of clock skew on the distributed algorithm. We will start to use the parameter\n",
"`clock_as_label` to display the internal clock of the nodes in the visualization.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `clock_increment` parameter of `NetworkBehaviorModel` will be used to simulate the clock skew. It will be added\n",
"to the internal clock of the nodes in every simulation step. For a fully synchronous network, the clock skew should be a\n",
"constant value for all nodes.\n",
"\n",
"The next cell does exactly that. We set an increment of 1.\n"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_vid(\n",
" NetworkBehaviorModel(clock_increment=lambda node: 1),\n",
" clock_as_label=True,\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The increment now is set to be a random value between 1 and 2. This will make the nodes' internal clocks to drift apart\n",
"slowly.\n"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import random\n",
"\n",
"\n",
"make_vid(\n",
" NetworkBehaviorModel(clock_increment=lambda node: random.randint(1, 2)),\n",
" clock_as_label=True,\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To exaggerate the effect of clock skew, we set the increment to be a random value between 1 and 5.\n"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_vid(\n",
" NetworkBehaviorModel(clock_increment=lambda node: random.randint(1, 5)),\n",
" clock_as_label=True,\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Everything together\n",
"\n",
"Just for fun, let's visualize the effect of all the disruptive network properties together.\n"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
""
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_vid(\n",
" NetworkBehaviorModel(\n",
" message_loss_indicator=random_loss(0.3), # 30% packet loss\n",
" message_delay_indicator=lambda network, message: random.randint(1, 5), # 1 to 5 time units delay\n",
" clock_increment=lambda node: random.randint(1, 3), # 1 to 3 time units per clock tick\n",
" ),\n",
" clock_as_label=True,\n",
")"
]
}
],
"metadata": {
"colab": {
"provenance": []
},
"kernelspec": {
"display_name": "venv_pydistim_dev",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.0rc1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}