Lamport Clock Ticks

You are debugging an incident timeline on one node. The node records events in order, but receives messages stamped by other nodes. Your task is to keep this node's Lamport clock correct.

You are given a sequence of events at a single node. Each event is one of:

• local: local computation
• send: message sent
• recv: message received with sender's Lamport timestamp

Clock starts at 0.

Rules:

• local / send: clock = clock + 1
• recv: clock = max(clock, msgTimestamp) + 1

Return the Lamport timestamp after each event.

Types

type Event struct {
    Kind         string
    MsgTimestamp int
}

Function signature

func LamportTimestamps(events []Event) []int

Example

Input:

[
  {Kind:"local"},
  {Kind:"send"},
  {Kind:"recv", MsgTimestamp:5},
  {Kind:"local"}
]

Output:

[1, 2, 6, 7]

Implementation blueprint (near-solution)

1. Initialize clock := 0 and out := make([]int, 0, len(events)).
2. For each event:
   • If recv: set clock = max(clock, MsgTimestamp) + 1.
   • Else (local / send): increment once.
3. Append clock to output for every event.
4. Return output.

Reference pseudocode:

clock = 0
for ev in events:
  if ev.kind == recv:
    clock = max(clock, ev.msgTs) + 1
  else:
    clock = clock + 1
  append(out, clock)

Why this is correct

• Receive must include remote timestamp to preserve happened-before order.
• +1 guarantees strict local progress.

Constraints

• 0 <= len(events) <= 100000
• For recv events, MsgTimestamp >= 0
• Kind is always one of local, send, recv

Common mistakes

• Forgetting +1 after max(...).
• Treating send as not advancing time.
• Returning final clock only instead of per-event clocks.