Give

Time, clocks and ordering

Why clocks can't order events across machines, and logical clocks that can.

Back to Coding · Replication and consensus

Planned. This module is part of the plan and is not written yet.

COCO-DST-REP-0303Level15–16

Why it matters

If each of the Lantern's two computers stamped records with its own clock, a few seconds of drift could put a learner's answer before the question it answers. Logical clocks order events without trusting wall time.

Draft outline · in review
For
Level 15–16 · 200 Level to 300 Level
Inside
5 lessons and a test · about 90 minutes
Topic
Replication and consensus · extension, 3 of 4
Plate CO-DST-REP-03: planned.

Inside the module.

5 lessons in order, about 90 minutes in all, then a short test. Learners go at their own pace; the minutes are a guide, not a timetable.

Draft outline · in review

  1. Lesson 1: Why clocks drift

    Each computer's clock runs slightly fast or slow, and syncing over a network is never exact.

    Explain15 min, from minute 0

  2. Lesson 2: Which happened first?

    Find cases where timestamps from two machines give the wrong order.

    Discussion15 min, from minute 15

  3. Lesson 3: Happened-before

    Lamport's relation: same-process order, and a send always comes before its receive.

    Explain15 min, from minute 30

  4. Lesson 4: Lamport clocks

    Add 1 at each event, and on receiving set the clock to the larger of the two values plus 1.

    Worked example25 min, from minute 45

  5. Lesson 5: Order the events

    Assign Lamport timestamps to message diagrams, and see what they can't tell you.

    Practice20 min, from minute 70

  6. End-of-module test

    Explain why physical clocks can't order events across machines, and use Lamport clocks to order events.

    Mastered at 85% or more. Retake it until you pass; nothing is lost, and each try gives feedback.

    Already know it? A Challenge Test (planned) clears the whole module: 90% overall, no objective below 75%.

    Last stageafter about 90 min

Practicalities

Draft outline · in review

  • Built to run offline

    Planned to run on the Lantern's own computer, with no internet needed.

  • Languages

    Planned first in English; every module aims to reach all of the Lantern's languages.

Try a question.

One question from the module, as a learner would meet it. Have a go, then open the worked solution a step at a time.

Draft outline · in review

Processes P and Q start with Lamport clocks at 0. P does one local event, then sends a message to Q. Before the message arrives, Q has done 3 local events. What timestamp does Q give to receiving the message?

Work it out on paper first, then show the answer and mark it yourself.

Particulars

Where it sits

Coding · Distributed computing · Replication and consensus

What a learner can do after it

  1. Explain why physical clocks cannot reliably order events across machines.
  2. Use logical clocks to order events.

Needs first

Unlocks

Level

Level 15–16 · 200 Level to 300 Level

Show levels in

Level mappings are approximate. A qualified teacher or lecturer in each country must check them before they appear in the app. Levels 13–18 describe the content, not the learner: “Level 15” means material usually taught in a second-year university course, whoever chooses to learn it.

Difficulty for its level

3 of 4 · Extension

Time

About 90 minutes

Alignments

  • Aligned to CS2023partial · in reviewCS2023 Parallel and Distributed Computing: ordering and time (descriptive ref)

Alignment in review until a qualified teacher or lecturer checks it. No exam body, university or vendor endorses us; learners still sit the real exam. University-level modules give knowledge, not university credit.

Challenge Test

Planned: a Challenge Test to prove you know it and skip it. Pass at 90% overall, with no objective below 75%.

University courses it previews

Computer Science, Software Engineering

On these pathways

The route here.

Everything this module builds on, drawn as a route from its foundations. Solid lanes must be mastered first, or cleared by a Challenge Test; dashed lanes are suggestions that never lock anything.

From Level 1, Instructions in order to Level 11, Recursion
  1. CO-BLK-SEQ-01 Instructions in order, Level 1–4, Coding. Planned.
  2. CO-BLK-SEQ-01Instructions in orderCoding · Primary 1 to Primary 4 (Level 1–4) · Planned
  3. CO-BLK-LOP-01 Repeat blocks, Level 3–5, Coding. Sample lesson in the demo.
  4. CO-BLK-LOP-01Repeat blocksCoding · Primary 3 to Primary 5 (Level 3–5) · Sample lesson in the demo Needs Instructions in order (required).Try the sample lesson: Repeat blocks
  5. DS-CMP-TYP-01 The home row, Level 3–6, Digital skills. Planned.
  6. DS-CMP-TYP-01The home rowDigital skills · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  7. CO-BLK-CND-01 If this, then that, Level 3–6, Coding. Planned.
  8. CO-BLK-CND-01If this, then thatCoding · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  9. CO-BLK-LOP-02 Patterns with loops, Level 4–6, Coding. Planned.
  10. CO-BLK-LOP-02Patterns with loopsCoding · Primary 4 to Primary 6 (Level 4–6) · Planned Needs Repeat blocks (required).
  11. DS-FIL-ORG-01 Folders that make sense, Level 4–7, Digital skills. Planned.
  12. DS-FIL-ORG-01Folders that make senseDigital skills · Primary 4 to JSS 1 (Level 4–7) · Planned · recommended
  13. MA-ARI-ORD-01 Order of operations, Level 5–6, Maths. Planned.
  14. MA-ARI-ORD-01Order of operationsMaths · Primary 5 to Primary 6 (Level 5–6) · Planned · recommended
  15. CO-BLK-LOP-03 Loops inside loops, Level 5–7, Coding. Planned.
  16. CO-BLK-LOP-03Loops inside loopsCoding · Primary 5 to JSS 1 (Level 5–7) · Planned · recommended
  17. CO-PRG-PYB-01 Your first Python program, Level 7–9, Coding. Planned.
  18. CO-PRG-PYB-01Your first Python programCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Patterns with loops (required), The home row (recommended).
  19. CO-PRG-PYB-02 Variables, Level 7–9, Coding. Sample lesson in the demo.
  20. CO-PRG-PYB-02VariablesCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Sample lesson in the demo Needs Your first Python program (required).Try the sample lesson: Variables
  21. CO-PRG-PYB-03 Numbers and calculations, Level 7–9, Coding. Planned.
  22. CO-PRG-PYB-03Numbers and calculationsCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Variables (required), Order of operations (recommended).
  23. MA-ALG-FRM-01 Substituting into formulae, Level 7–8, Maths. Planned.
  24. MA-ALG-FRM-01Substituting into formulaeMaths · JSS 1 to JSS 2 (Level 7–8) · Planned · recommended
  25. CO-NET-HOW-01 Packets, addresses and routes, Level 7–10, Coding. Planned.
  26. CO-NET-HOW-01Packets, addresses and routesCoding · JSS 1 to SSS 1 (Level 7–10) · Planned
  27. CO-PRG-PYB-05 Decisions with if, Level 8–10, Coding. Planned.
  28. CO-PRG-PYB-05Decisions with ifCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Numbers and calculations (required), If this, then that (recommended).
  29. CO-PRG-PYB-06 Loops in Python, Level 8–10, Coding. Planned.
  30. CO-PRG-PYB-06Loops in PythonCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Decisions with if (required), Loops inside loops (recommended).
  31. CO-PRG-PYF-01 Defining functions, Level 8–11, Coding. Planned.
  32. CO-PRG-PYF-01Defining functionsCoding · JSS 2 to SSS 2 (Level 8–11) · Planned Needs Loops in Python (required).
  33. CO-PRG-PYB-07 Lists, Level 8–10, Coding. Planned.
  34. CO-PRG-PYB-07ListsCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Loops in Python (required).
  35. CO-SYS-OPS-01 What an operating system does, Level 8–11, Coding. Planned.
  36. CO-SYS-OPS-01What an operating system doesCoding · JSS 2 to SSS 2 (Level 8–11) · Planned · recommended
  37. CO-PRG-PYF-02 Parameters and return values, Level 9–11, Coding. Planned.
  38. CO-PRG-PYF-02Parameters and return valuesCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Defining functions (required), Substituting into formulae (recommended).
  39. CO-ALG-SRT-01 Linear search, Level 9–11, Coding. Planned.
  40. CO-ALG-SRT-01Linear searchCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required), Lists (required).
  41. CO-PRG-PYF-03 Scope, Level 9–11, Coding. Planned.
  42. CO-PRG-PYF-03ScopeCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required).
  43. CO-PRG-PYF-04 Breaking problems into functions, Level 9–12, Coding. Planned.
  44. CO-PRG-PYF-04Breaking problems into functionsCoding · JSS 3 (BECE) to SSS 3 (WASSCE) (Level 9–12) · Planned Needs Parameters and return values (required), Lists (required).
  45. CO-ALG-SRT-03 Simple sorts, Level 10–12, Coding. Planned.
  46. CO-ALG-SRT-03Simple sortsCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned Needs Linear search (required).
  47. CO-ALG-SRT-02 Binary search, Level 10–12, Coding. Planned.
  48. CO-ALG-SRT-02Binary searchCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned Needs Linear search (required).
  49. CO-PRG-PYF-05 Recursion, Level 11–13, Coding. Planned.
  50. CO-PRG-PYF-05RecursionCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned Needs Scope (required).
  51. CO-ALG-SRT-04Merge sortCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned Needs Simple sorts (required), Recursion (required).
  52. CO-SWD-GIT-01Why version control?Coding · SSS 3 (WASSCE) to A level / JUPEB / foundation year (Level 12–13) · Planned Needs Parameters and return values (required), Folders that make sense (recommended).
  53. CO-SWD-GIT-02Commits and historyCoding · SSS 3 (WASSCE) to A level / JUPEB / foundation year (Level 12–13) · Planned Needs Why version control? (required).
  54. CO-ALG-SRT-05Comparing algorithmsCoding · SSS 3 (WASSCE) to A level / JUPEB / foundation year (Level 12–13) · Planned Needs Binary search (required), Merge sort (required).
  55. From here on: Beyond school · university level
    CO-SWD-GIT-03Branches and mergingCoding · A level / JUPEB / foundation year to 100 Level (Level 13–14) · Planned Needs Commits and history (required).
  56. CO-SWD-GIT-04Working together with remotesCoding · A level / JUPEB / foundation year to 100 Level (Level 13–14) · Planned Needs Branches and merging (required).
  57. CO-DST-CCR-01Doing many things at onceCoding · 100 Level to 200 Level (Level 14–15) · Planned Needs Breaking problems into functions (required), Comparing algorithms (required), What an operating system does (recommended).
  58. CO-DST-FND-01What makes a system distributedCoding · 200 Level (Level 15) · Planned Needs Doing many things at once (required), Packets, addresses and routes (required), Working together with remotes (required).
  59. CO-DST-REP-01Why replicate?Coding · 200 Level to 300 Level (Level 15–16) · Planned Needs What makes a system distributed (required).
  60. CO-DST-REP-03Time, clocks and orderingCoding · 200 Level to 300 Level (Level 15–16) · Planned · the destination Needs Why replicate? (required).
35 stops across Coding, Digital skills and Maths. 2 have a sample lesson in the demo; the other 33 are planned and not yet written.

Help light the room where this is learned.

Every route on this map starts in a classroom with 24 stations, a tutor that works offline and a facilitator upstairs. Four are planned and waiting for light.

Help light a LanternTalk to us about a major gift