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


The Byzantine generals problem (Lamport, Shostak and Pease 1982)
================================================================

Generals surrounding a city must agree to attack or retreat, communicating
by messenger, while some of them are traitors who tell different generals
different things. Lamport, Shostak and Pease proved agreement possible if
and only if more than two thirds of the generals are loyal, and gave the
oral-messages algorithm OM(m): every lieutenant relays what it heard, and
everyone takes a majority.

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

With four generals and one traitor, the loyal ones always agree, and follow
a loyal commander. With three generals and one traitor, a loyal lieutenant
can be talked out of the commander's order: n > 3m is necessary. This
3f + 1 bound reappears in every Byzantine fault-tolerant blockchain.

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

.. GENERATED FROM PYTHON SOURCE LINES 25-27

Four generals, one traitor anywhere
-----------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-36

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    for traitor in range(4):
        result = bk.consensus.oral_messages(4, {traitor}, "attack", rounds=1)
        assert result.agreement and result.validity
        print(f"traitor {traitor}: loyal decisions {result.decisions}")





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

 .. code-block:: none

    traitor 0: loyal decisions {1: 'retreat', 2: 'retreat', 3: 'retreat'}
    traitor 1: loyal decisions {2: 'attack', 3: 'attack'}
    traitor 2: loyal decisions {1: 'attack', 3: 'attack'}
    traitor 3: loyal decisions {1: 'attack', 2: 'attack'}




.. GENERATED FROM PYTHON SOURCE LINES 37-39

Three generals are not enough
-----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 39-43

.. code-block:: Python

    result = bk.consensus.oral_messages(3, {2}, "attack", rounds=1)
    print("loyal lieutenant 1 decides:", result.decisions[1], "although the commander said attack")
    assert not result.validity





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

 .. code-block:: none

    loyal lieutenant 1 decides: retreat although the commander said attack




.. GENERATED FROM PYTHON SOURCE LINES 44-46

When does OM(1) survive one traitor?
------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 46-62

.. code-block:: Python

    sizes = range(3, 9)
    survives = []
    for n in sizes:
        runs = [bk.consensus.oral_messages(n, {t}, "attack", rounds=1) for t in range(n)]
        survives.append(all(r.agreement and r.validity for r in runs))
    assert survives == [n > 3 for n in sizes]
    fig, ax = plt.subplots(figsize=(7, 3))
    ax.bar([str(n) for n in sizes], survives, color=["#16a34a" if ok else "#dc2626" for ok in survives])
    ax.set(
        xlabel="generals n (one traitor)",
        yticks=[0, 1],
        yticklabels=["fails", "works"],
        title="OM(1) needs n > 3",
    )
    fig.tight_layout()




.. image-sg:: /api/gallery/consensus/agreement/images/sphx_glr_plot_01_byzantine_generals_001.png
   :alt: OM(1) needs n > 3
   :srcset: /api/gallery/consensus/agreement/images/sphx_glr_plot_01_byzantine_generals_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 63-68

Exercise
--------
Run ``oral_messages(7, {a, b}, "attack", rounds=2)`` for every pair of
traitors, then with rounds=1. Why does tolerating m traitors need m + 1
rounds of relaying?


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

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


.. _sphx_glr_download_api_gallery_consensus_agreement_plot_01_byzantine_generals.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/consensus/agreement/plot_01_byzantine_generals.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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