Algorithms¶

These are real distributed algorithms written choreographically — the same class of programs Klor (the Clojure original) demonstrates with Chang–Roberts leader election and Fokkink's textbook algorithms. They run for real: python examples_algorithms.py, and tests/test_algorithms.py pins the documented outputs.

Ring leader election (simplified Chang–Roberts)¶

Three roles form a ring A → B → C → A, each holding its own ID. Whoever holds the largest ID is elected.

@choreography
def ring_election(id_a: A, id_b: B, id_c: C):
    # (1) one circuit: a token carrying the best ID seen so far visits B, C,
    #     then returns to A; each role folds in its own ID.
    t1 = A(id_a)
    t2v = move(t1, A, B)          # A -> B
    t2 = B(max(t2v, id_b))        # B folds in its ID
    t3v = move(t2, B, C)          # B -> C
    t3 = C(max(t3v, id_c))        # C folds in its ID
    t4v = move(t3, C, A)          # C -> A
    best = A(max(t4v, id_a))      # A folds in its ID: circuit complete

    # (2) share the winner with every role (an agreement broadcast)
    shared = copy(best, A, B)          # now at {A, B}
    shared = copy(shared, A, C)        # now at {A, B, C}

    # (3) every role decides locally whether it is the leader
    winner_a = A(id_a == shared)
    winner_b = B(id_b == shared)
    winner_c = C(id_c == shared)
    payload = pack(shared, winner_a, winner_b, winner_c)
    return payload

The interesting parts are all location statements:

• the token is one value that lives at exactly one role at a time — move hands it around the ring, so there is no shared state and no race;
• pack gathers the per-role verdicts into one return value;
• roles never read a value they don't have (max(t2v, id_b) runs at B, where both operands live).

Actual output (this is the real simulation result):

$ python examples_algorithms.py
election (A wins): (7, True, False, False)     # ids 7, 3, 5
election (B wins): (9, False, True, False)     # ids 2, 9, 4

You can replay the communication: A → B: 7, B → C: max(7, id_b), C → A: max(..., id_c), then two A-to-peer copies for the broadcast. Klor's Clojure docs show the same message trace for its implementation.

Convergecast aggregation¶

B and C are leaf sensors; A is the aggregation root. Each leaf ships its value to the root, which combines them — a classic convergecast.

@choreography
def aggregate_sum(v_a: A, v_b: B, v_c: C) -> A:
    m_b = move(v_b, B, A)         # B -> A
    m_c = move(v_c, C, A)         # C -> A
    total = A(v_a + m_b + m_c)    # A aggregates locally
    return total

$ python examples_algorithms.py
aggregate: {'A': 60, 'B': NOOP, 'C': NOOP}    # 10 + 20 + 30

Note the erasure: v_a is a parameter only A receives, v_b only B, v_c only C (annotations). The NOOPs are the roles with no result — the root's sum is the only return.

What these show¶

• Moving a value = move. There is no "send a message and hope" — the destination is named in the choreography and the runtime performs it.
• No per-role programs to maintain. The election protocol is one function (~15 lines) instead of three programs plus their coordination rules.
• The simulator is a first-class tool. simulate_chor runs the whole protocol in-process with an in-memory transport, prints the gathered results, and the same choreography runs unchanged over TCP (see Networking) — the transports are swappable.

Both algorithms are covered by tests/test_algorithms.py, so the outputs pinned here are verified on every run of the suite.