.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/network/gossip/plot_02_rumor_spreading.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_02_rumor_spreading.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_02_rumor_spreading.py:


Rumor spreading in log2 n + ln n rounds (Frieze and Grimmett 1985, Pittel 1987)
===============================================================================

How long does push gossip take to reach everyone? On the complete graph,
Frieze and Grimmett, and then Pittel more precisely, showed it takes
``log2 n + ln n + O(1)`` rounds. The first term is the doubling phase, while
almost every call reaches someone new; the second is a coupon-collector
phase, while the last few peers wait to be called.

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

The measured rounds track ``log2 n + ln n`` with a gap that stays roughly
constant as n grows a thousandfold. A network of a million peers needs only
about 34 rounds: this is why gossip scales.

The history behind this experiment: :doc:`/history/network_breakthroughs`.
See :doc:`/exercises/network` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Measure rounds for n from 16 to 16384
-------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-38

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk

    sizes = [2**k for k in range(4, 15, 2)]
    measured = [np.mean([bk.network.spread_rumor(n, seed=s).rounds for s in range(8)]) for n in sizes]
    predicted = [bk.network.pittel_rounds(n) for n in sizes]
    gaps = [m - p for m, p in zip(measured, predicted, strict=True)]
    print([round(float(g), 2) for g in gaps])
    assert max(gaps) - min(gaps) < 2.5  # The O(1) term does not grow with n.
    print(round(bk.network.pittel_rounds(10**6), 1), "rounds for a million peers")





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

 .. code-block:: none

    [0.73, 1.09, 1.7, 0.94, 0.93, 1.3]
    33.7 rounds for a million peers




.. GENERATED FROM PYTHON SOURCE LINES 39-41

The two phases
--------------

.. GENERATED FROM PYTHON SOURCE LINES 41-57

.. code-block:: Python

    run = bk.network.spread_rumor(16384, seed=1)
    doubling = next(r for r, count in enumerate(run.informed) if count > 16384 / 2)
    print(f"half informed after {doubling} rounds; done after {run.rounds}")
    assert abs(doubling - np.log2(16384)) < 2

    fig, (left, right) = plt.subplots(1, 2, figsize=(10, 3.8))
    left.semilogx(sizes, measured, "o", label="simulated push")
    left.semilogx(sizes, predicted, "-", color="black", label="log2 n + ln n")
    left.set(xlabel="peers n", ylabel="rounds", title="Rounds to inform everyone")
    left.legend()
    right.plot(run.informed, marker="o", markersize=3)
    right.axvline(doubling, color="black", linestyle="--", label="half informed")
    right.set(xlabel="round", ylabel="informed peers", title="Doubling, then the tail")
    right.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/network/gossip/images/sphx_glr_plot_02_rumor_spreading_001.png
   :alt: Rounds to inform everyone, Doubling, then the tail
   :srcset: /api/gallery/network/gossip/images/sphx_glr_plot_02_rumor_spreading_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    half informed after 14 rounds; done after 24




.. GENERATED FROM PYTHON SOURCE LINES 58-62

Exercise
--------
Run push on a ring (``bk.network.ring_lattice(n, 2)``) instead of the
complete graph. How do the rounds grow with n now, and why?


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

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


.. _sphx_glr_download_api_gallery_network_gossip_plot_02_rumor_spreading.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_02_rumor_spreading.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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