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


Lamport clocks: ordering events without a shared clock (Lamport 1978)
=====================================================================

Peers' clocks drift, so wall-clock timestamps cannot say which of two events
came first. Lamport replaced physical time with *happened before*: an event
precedes the later events at its own process, a message's send precedes its
receive, and the relation is transitive. A counter that ticks at every event
and jumps past every timestamp it receives respects that order.

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

Every arrow in the space-time diagram points forward in Lamport time: that
is the clock condition. Ordering events by ``(timestamp, process)`` gives one
total order that all processes can compute alike, which Lamport used for
mutual exclusion and which underlies state-machine replication. But a
smaller timestamp does not prove an event came first: events that are
concurrent still receive ordered numbers.

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 26-28

Three processes exchange three messages
---------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 28-42

.. code-block:: Python

    import matplotlib.pyplot as plt

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

    history = [
        [("send", "m1"), ("local", "a"), ("receive", "m3")],
        [("receive", "m1"), ("send", "m2")],
        [("local", "b"), ("receive", "m2"), ("send", "m3")],
    ]
    stamps = bk.network.lamport_timestamps(history)
    print(stamps)
    assert stamps == ((1, 2, 6), (2, 3), (1, 4, 5))





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

 .. code-block:: none

    ((1, 2, 6), (2, 3), (1, 4, 5))




.. GENERATED FROM PYTHON SOURCE LINES 43-47

The clock condition
-------------------
Each receive is stamped later than its send, and each process's stamps
increase, so every chain of causes has increasing timestamps.

.. GENERATED FROM PYTHON SOURCE LINES 47-59

.. code-block:: Python

    sends = {
        label: stamps[p][i]
        for p, events in enumerate(history)
        for i, (kind, label) in enumerate(events)
        if kind == "send"
    }
    for p, events in enumerate(history):
        assert list(stamps[p]) == sorted(set(stamps[p]))
        for i, (kind, label) in enumerate(events):
            if kind == "receive":
                assert stamps[p][i] > sends[label]








.. GENERATED FROM PYTHON SOURCE LINES 60-63

One total order everyone agrees on
----------------------------------
Break timestamp ties by process number.

.. GENERATED FROM PYTHON SOURCE LINES 63-70

.. code-block:: Python

    order = sorted(
        (stamps[p][i], p, label)
        for p, events in enumerate(history)
        for i, (_, label) in enumerate(events)
    )
    print([f"P{p}:{label}" for _, p, label in order])





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

 .. code-block:: none

    ['P0:m1', 'P2:b', 'P0:a', 'P1:m1', 'P1:m2', 'P2:m2', 'P2:m3', 'P0:m3']




.. GENERATED FROM PYTHON SOURCE LINES 71-76

The converse fails
------------------
Local event ``b`` (time 1) and local event ``a`` (time 2) are not causally
related: no chain of messages links them. Their timestamps are ordered
anyway, so a Lamport timestamp cannot detect concurrency.

.. GENERATED FROM PYTHON SOURCE LINES 76-82

.. code-block:: Python

    assert stamps[2][0] < stamps[0][1]

    fig, ax = plt.subplots(figsize=(8, 3.5))
    plot_space_time(history, ax=ax)
    fig.tight_layout()




.. image-sg:: /api/gallery/network/events/images/sphx_glr_plot_02_lamport_clocks_001.png
   :alt: Space-time diagram
   :srcset: /api/gallery/network/events/images/sphx_glr_plot_02_lamport_clocks_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 83-87

Exercise
--------
Add a message from P0 to P2 sent right after ``a`` and received before
``b``. Which timestamps change, and is ``a`` still concurrent with ``b``?


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

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


.. _sphx_glr_download_api_gallery_network_events_plot_02_lamport_clocks.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/events/plot_02_lamport_clocks.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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