Skip to main content

Vector Clock Coordination

This page explains event coordination based on Vector Clocks, a deterministic method for synchronizing events in a decentralized environment.

The Core Concept​

Vector clocks enable independent processors to establish identical event orderings without requiring centralized control. The key insight is tracking not just "when" but "after what" each event occurred.

Here's how it works at a high level:

  1. Each timeline maintains a vector - a map of counters for every participant
  2. Messages carry these vectors - showing what the sender has seen from each participant
  3. Processors compare vectors to determine ordering relationships
  4. Concurrent events (with incomparable vectors) are ordered alphabetically by timeline BlueId
  5. All processors apply identical rules, ensuring consistent ordering

This approach preserves causal relationships (if A caused B, B must follow A) while deterministically ordering concurrent events, all without requiring synchronized clocks or central coordination.

Vector Clock Fundamentals​

A Vector Clock Coordinator is defined in a document's contracts:

contracts:
  channelCoordinator:
    type: Vector Clock Coordinator
    channels: [aliceChannel, bobChannel]

Each timeline entry contains a vector clock - a map of timeline BlueIds to counter values:

type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Starting the discussion"
  vectorClock:
    z7Q92rGt4v: 1  # Sender's timeline (incremented)
    Hkzm8Ypd5k: 0  # Other participant's timeline

Simple Example: Alice and Bob​

Let's walk through a basic scenario with just Alice and Bob:

Initial Messages​

# Alice posts first message
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Hello Bob"
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 0  # Bob's timeline

# Bob posts first message (hasn't seen Alice's)
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Hello Alice"
  vectorClock:
    z7Q92rGt4v: 0  # Alice's timeline
    Hkzm8Ypd5k: 1  # Bob's timeline

These messages are concurrent (neither happened before the other), so they are ordered by alphabetical comparison of their timeline BlueIds. In this case, if z7Q92rGt4v comes before Hkzm8Ypd5k alphabetically, Alice's message would be processed first.

Acknowledgments and Responses​

# Alice acknowledges Bob's message
type: Timeline Entry
message: 
  type: Vector Clock Acknowledgment
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 1  # Bob's timeline (updated)

# Bob responds after seeing Alice's message
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "I got your message"
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline (last seen)
    Hkzm8Ypd5k: 2  # Bob's timeline (incremented)

Bob's response has a vector clock that clearly indicates it happened after Alice's first message (since it includes knowledge of that message).

How Processors Determine Order​

When a processor observes these events (potentially in any order), it orders them by:

  1. Comparing Vector Clocks: For events with vectors A and B:

    • If all elements in A ≤ corresponding elements in B, and at least one A < B, then A happened before B
    • If this comparison doesn't establish an order, the events are concurrent

  2. Ordering Concurrent Events:

    • Concurrent events are ordered alphabetically by their timeline BlueIds

In our example, the resulting order would be:

  1. Alice's first message (if z7Q92rGt4v < Hkzm8Ypd5k alphabetically)
  2. Bob's first message
  3. Bob's second message (causally after Alice's first)

Complex Scenario: Network Partitions and Multiple Participants​

Let's examine a more complex scenario with four participants (Alice, Bob, Celine, Dean) and network partitions:

Phase 1: Initial Concurrent Messages​

# Alice posts
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Meeting tomorrow?"
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 0  # Bob's timeline
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Bob posts (unaware of Alice)
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Project update"
  vectorClock:
    z7Q92rGt4v: 0  # Alice's timeline
    Hkzm8Ypd5k: 1  # Bob's timeline
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Celine posts (unaware of both)
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Budget proposal"
  vectorClock:
    z7Q92rGt4v: 0  # Alice's timeline
    Hkzm8Ypd5k: 0  # Bob's timeline
    JNcA3FV6xD: 1  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

Phase 2: First Wave of Acknowledgments​

# Alice acknowledges Bob
type: Timeline Entry
message: 
  type: Vector Clock Acknowledgment
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 1  # Bob's timeline (updated)
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Bob acknowledges Alice and Celine
type: Timeline Entry
message: 
  type: Vector Clock Acknowledgment
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 1  # Bob's timeline
    JNcA3FV6xD: 1  # Celine's timeline (updated)
    qbn5KJsLNc: 0  # Dean's timeline

Phase 3: Network Splits into THREE Partitions​

  • Partition 1: Alice alone
  • Partition 2: Bob alone
  • Partition 3: Celine and Dean (just joining)

Phase 4: Activity in Isolated Partitions​

# Alice (alone) posts new message
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Can anyone see this?"
  vectorClock:
    z7Q92rGt4v: 2  # Alice's timeline (incremented)
    Hkzm8Ypd5k: 1  # Bob's timeline
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Bob (alone) posts new message
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Network issues?"
  vectorClock:
    z7Q92rGt4v: 1  # Alice's timeline
    Hkzm8Ypd5k: 2  # Bob's timeline (incremented)
    JNcA3FV6xD: 1  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Dean joins and posts first message
type: Timeline Entry
message: 
  type: Vector Clock Message
  message: "Hello, I'm new here"
  vectorClock:
    z7Q92rGt4v: 0  # Alice's timeline
    Hkzm8Ypd5k: 0  # Bob's timeline
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 1  # Dean's timeline (first message)

Phase 5: Partial Network Healing​

  • Alice and Bob partitions connect
  • Celine and Dean remain separated
# Alice acknowledges Bob's second message
type: Timeline Entry
message: 
  type: Vector Clock Acknowledgment
  vectorClock:
    z7Q92rGt4v: 2  # Alice's timeline
    Hkzm8Ypd5k: 2  # Bob's timeline (updated)
    JNcA3FV6xD: 0  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

# Bob acknowledges Alice's second message
type: Timeline Entry
message: 
  type: Vector Clock Acknowledgment
  vectorClock:
    z7Q92rGt4v: 2  # Alice's timeline (updated)
    Hkzm8Ypd5k: 2  # Bob's timeline
    JNcA3FV6xD: 1  # Celine's timeline
    qbn5KJsLNc: 0  # Dean's timeline

Phase 6: Complete Network Healing​

After the network fully heals and all messages are exchanged, each participant's vector clock reflects awareness of all messages:

# Final state - Alice's vector
vectorClock:
  z7Q92rGt4v: 2  # Alice's timeline
  Hkzm8Ypd5k: 2  # Bob's timeline
  JNcA3FV6xD: 1  # Celine's timeline
  qbn5KJsLNc: 1  # Dean's timeline

# Final state - Bob's vector
vectorClock:
  z7Q92rGt4v: 2  # Alice's timeline
  Hkzm8Ypd5k: 2  # Bob's timeline
  JNcA3FV6xD: 1  # Celine's timeline
  qbn5KJsLNc: 1  # Dean's timeline

The Resulting Deterministic Order​

Despite the complex network conditions, all processors will determine the same event order:

  1. Alice's first message (timestamp: [1,0,0,0])
  2. Bob's first message (timestamp: [0,1,0,0])
  3. Celine's message (timestamp: [0,0,1,0])
  4. Alice's second message (timestamp: [2,1,0,0])
  5. Bob's second message (timestamp: [1,2,1,0])
  6. Dean's message (timestamp: [0,0,0,1])

The vector clock system ensures this ordering is consistent for all processors, regardless of the order in which they observed the events.

Vector clock coordination provides a robust foundation for deterministic event ordering in decentralized Blue documents, handling complex scenarios like network partitions while maintaining Blue's core guarantee that all processors reach identical document states.