.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/network/events/plot_03_vector_clocks.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` 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_03_vector_clocks.py: Vector clocks: detecting concurrency (Fidge and Mattern 1988) ============================================================= A Lamport timestamp orders events but cannot tell whether two events are causally related. Fidge and Mattern independently gave each process a vector of counters, one per process. Entry ``q`` of an event's vector counts the events at process ``q`` that happened before or at it, so comparing two vectors entry by entry answers exactly whether one event caused the other or the two are concurrent. What to look for ---------------- For every pair of events, vectors and Lamport timestamps never disagree on a causal pair, but only vectors recognize the concurrent pairs. Concurrent updates are the ones a replicated system must reconcile; two conflicting transactions broadcast at the same time are concurrent in exactly this sense. 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 The same history as the Lamport example --------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 28-47 .. code-block:: Python import itertools import matplotlib.pyplot as plt import numpy as np import blockchainkit as bk history = [ [("send", "m1"), ("local", "a"), ("receive", "m3")], [("receive", "m1"), ("send", "m2")], [("local", "b"), ("receive", "m2"), ("send", "m3")], ] vectors = bk.network.vector_timestamps(history) lamport = bk.network.lamport_timestamps(history) events = [(p, i) for p, row in enumerate(history) for i in range(len(row))] names = [f"P{p}:{history[p][i][1]}" for p, i in events] for name, (p, i) in zip(names, events, strict=True): print(f"{name:7s} Lamport {lamport[p][i]} vector {vectors[p][i]}") .. rst-class:: sphx-glr-script-out .. code-block:: none P0:m1 Lamport 1 vector (1, 0, 0) P0:a Lamport 2 vector (2, 0, 0) P0:m3 Lamport 6 vector (3, 2, 3) P1:m1 Lamport 2 vector (1, 1, 0) P1:m2 Lamport 3 vector (1, 2, 0) P2:b Lamport 1 vector (0, 0, 1) P2:m2 Lamport 4 vector (1, 2, 2) P2:m3 Lamport 5 vector (1, 2, 3) .. GENERATED FROM PYTHON SOURCE LINES 48-50 Classify every pair ------------------- .. GENERATED FROM PYTHON SOURCE LINES 50-69 .. code-block:: Python relation = np.zeros((len(events), len(events))) for (x, (p, i)), (y, (q, j)) in itertools.product(enumerate(events), repeat=2): a, b = vectors[p][i], vectors[q][j] if bk.network.happened_before(a, b): relation[x, y] = 1 assert lamport[p][i] < lamport[q][j] # Causal order implies Lamport order. elif bk.network.happened_before(b, a): relation[x, y] = -1 concurrent = int((relation[np.triu_indices(len(events), 1)] == 0).sum()) print(concurrent, "concurrent pairs") assert bk.network.concurrent(vectors[0][1], vectors[2][0]) # "a" and "b". fig, ax = plt.subplots(figsize=(6, 5)) ax.imshow(relation, cmap="coolwarm", vmin=-1, vmax=1) ax.set_xticks(range(len(events)), names, rotation=60) ax.set_yticks(range(len(events)), names) ax.set_title("row -> column (red), column -> row (blue), concurrent (grey)") fig.tight_layout() .. image-sg:: /api/gallery/network/events/images/sphx_glr_plot_03_vector_clocks_001.png :alt: row -> column (red), column -> row (blue), concurrent (grey) :srcset: /api/gallery/network/events/images/sphx_glr_plot_03_vector_clocks_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none 8 concurrent pairs .. GENERATED FROM PYTHON SOURCE LINES 70-76 Exercise -------- A vector clock grows with the number of processes. Why can no scalar clock capture concurrency exactly? Hint: in this history, find events x, y, z with x concurrent to y and y concurrent to z, but x before z. Could "equal timestamps" ever mean "concurrent"? .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.137 seconds) .. _sphx_glr_download_api_gallery_network_events_plot_03_vector_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_03_vector_clocks.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_03_vector_clocks.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_03_vector_clocks.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_03_vector_clocks.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_