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


State-machine replication: same inputs, same order, same state (Lamport 1978, Schneider 1990)
=============================================================================================

If every replica starts in the same state and applies the same commands in
the same order, deterministic execution keeps them identical. Lamport
introduced the idea; Schneider's tutorial made it the standard recipe for
fault tolerance. A blockchain is exactly this: consensus agrees on the
order of transactions, and every node executes them.

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

Replicas that apply the same log agree. Applying the same commands in a
different order generally gives a different state, because the commands do
not commute. And one nondeterministic input, here each replica reading its
own clock, makes replicas diverge even with the same log.

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

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Three commands on one counter
-----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-54

.. code-block:: Python

    import itertools

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    commands = {
        "add 5": bk.vm.assemble("LOAD 0\nPUSH 5\nADD\nSTORE 0"),
        "double": bk.vm.assemble("LOAD 0\nPUSH 2\nMUL\nSTORE 0"),
        "minus 3": bk.vm.assemble("LOAD 0\nPUSH 3\nSUB\nSTORE 0"),
    }


    def replay(log, storage=None):
        state = dict(storage or {0: 1})
        for name in log:
            state = dict(bk.vm.execute(commands[name], storage=state).storage)
        return state[0]


    log = ["add 5", "double", "minus 3"]
    replicas = [replay(log) for _ in range(3)]
    print("same log:", replicas)
    assert len(set(replicas)) == 1

    orders = {" > ".join(order): replay(order) for order in itertools.permutations(log)}
    print(orders)
    assert len(set(orders.values())) > 1





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

 .. code-block:: none

    same log: [9, 9, 9]
    {'add 5 > double > minus 3': 9, 'add 5 > minus 3 > double': 6, 'double > add 5 > minus 3': 4, 'double > minus 3 > add 5': 4, 'minus 3 > add 5 > double': 6, 'minus 3 > double > add 5': 1}




.. GENERATED FROM PYTHON SOURCE LINES 55-58

Nondeterminism breaks replication
---------------------------------
A command that stores "the current time" as each replica sees it.

.. GENERATED FROM PYTHON SOURCE LINES 58-71

.. code-block:: Python

    clocks = [1000, 1002, 999]
    stamped = [
        bk.vm.execute(bk.vm.assemble("STORE 1"), arguments=(clock,), storage={0: 1}).storage[1]
        for clock in clocks
    ]
    print("timestamps:", stamped)
    assert len(set(stamped)) == 3

    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.barh(list(orders), list(orders.values()), color="#7c3aed")
    ax.set(xlabel="final counter", title="Same commands, different orders")
    fig.tight_layout()




.. image-sg:: /api/gallery/vm/replication/images/sphx_glr_plot_01_state_machine_replication_001.png
   :alt: Same commands, different orders
   :srcset: /api/gallery/vm/replication/images/sphx_glr_plot_01_state_machine_replication_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    timestamps: [1000, 1002, 999]




.. GENERATED FROM PYTHON SOURCE LINES 72-77

Exercise
--------
Blockchains put the time into the block header, chosen once by the
proposer and agreed by consensus. Rewrite the timestamp command so all
replicas take the time from the log instead of their clocks.


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

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


.. _sphx_glr_download_api_gallery_vm_replication_plot_01_state_machine_replication.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/vm/replication/plot_01_state_machine_replication.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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