.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/network/gossip/plot_01_epidemic_algorithms.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_network_gossip_plot_01_epidemic_algorithms.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_network_gossip_plot_01_epidemic_algorithms.py:


Epidemic algorithms: push, pull and push-pull (Demers et al. 1987)
==================================================================

Demers and colleagues at Xerox PARC kept the replicas of a database
consistent by letting each replica periodically call a random other one and
exchange updates, like an infection passing between people. They compared
*push* (the caller sends what it knows), *pull* (the caller asks for what it
lacks), and both together.

What to look for
----------------

Push starts fast but finishes slowly: near the end, an informed caller
mostly reaches peers that already know, so the uninformed fraction shrinks
only by a constant factor per round. Pull is the reverse: an uninformed peer
stays uninformed only if it calls another uninformed peer, so once most
peers know, the uninformed fraction *squares* each round. Push-pull gets
both phases and finishes first.

The history behind this experiment: :doc:`/history/network_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 25-27

Spread one update among 4096 replicas
-------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-39

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.network.visualizers import plot_rumor_spread

    n = 4096
    modes = ("push", "pull", "push-pull")
    runs = {mode: bk.network.spread_rumor(n, mode=mode, seed=3) for mode in modes}
    for mode, run in runs.items():
        print(f"{mode:9s} {run.rounds} rounds")
    assert runs["push-pull"].rounds < runs["pull"].rounds < runs["push"].rounds





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    push      21 rounds
    pull      15 rounds
    push-pull 11 rounds




.. GENERATED FROM PYTHON SOURCE LINES 40-44

Pull squares the residue
------------------------
If a fraction s is uninformed at the start of a round, an uninformed peer
calls another uninformed peer with probability about s.

.. GENERATED FROM PYTHON SOURCE LINES 44-50

.. code-block:: Python

    residue = [1 - count / n for count in runs["pull"].informed]
    for before, after in zip(residue, residue[1:], strict=False):
        if 0 < before < 0.5:
            print(f"{before:.4f} -> {after:.4f}   (s**2 = {before**2:.4f})")
            assert abs(after - before**2) < 0.02





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    0.3325 -> 0.1145   (s**2 = 0.1106)
    0.1145 -> 0.0127   (s**2 = 0.0131)
    0.0127 -> 0.0000   (s**2 = 0.0002)




.. GENERATED FROM PYTHON SOURCE LINES 51-55

Push shrinks it by a constant factor
------------------------------------
An uninformed peer escapes every one of about n informed callers with
probability (1 - 1/n)**n, close to 1/e.

.. GENERATED FROM PYTHON SOURCE LINES 55-68

.. code-block:: Python

    residue = [1 - count / n for count in runs["push"].informed]
    late = [
        after / before
        for before, after in zip(residue, residue[1:], strict=False)
        if 0.01 < before < 0.2
    ]
    print([round(ratio, 2) for ratio in late])
    assert all(0.25 < ratio < 0.5 for ratio in late)

    fig, ax = plt.subplots(figsize=(7, 4))
    plot_rumor_spread(runs, ax=ax)
    fig.tight_layout()




.. image-sg:: /api/gallery/network/gossip/images/sphx_glr_plot_01_epidemic_algorithms_001.png
   :alt: Rumor spreading
   :srcset: /api/gallery/network/gossip/images/sphx_glr_plot_01_epidemic_algorithms_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    [0.43, 0.39, 0.43]




.. GENERATED FROM PYTHON SOURCE LINES 69-75

Exercise
--------
Demers et al. also studied *rumor mongering*: a peer stops pushing once it
has called k peers that already knew. Implement it with a loop around
random calls and measure the *residue*, the fraction never informed, for
k = 1, 2, 3.


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.392 seconds)


.. _sphx_glr_download_api_gallery_network_gossip_plot_01_epidemic_algorithms.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/network/gossip/plot_01_epidemic_algorithms.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_epidemic_algorithms.ipynb <plot_01_epidemic_algorithms.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_epidemic_algorithms.py <plot_01_epidemic_algorithms.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_epidemic_algorithms.zip <plot_01_epidemic_algorithms.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_