path: root/README.md

# 0. License

Contact `<mailto:colloid@romanilin.is>` to discuss a commercial license if:

* Your use case exceeds the production-use thresholds described in `LICENSE.txt`.
* You wish to embed or distribute the Licensed Work in a proprietary product.
* Your corporate policy prohibits the use of BUSL-1.1 or AGPL-3.0-or-later software and requires a standard commercial software agreement.

Commercial licenses remain available for all versions of the software even after they have transitioned to the Change License.

# 1. Invariants & Guarantees

This section defines the formal promises and explicit limitations of Colloid. Every mechanism described in sections 2–15 must trace back to an invariant defined here. If a mechanism cannot be justified by an invariant, it does not belong in the system.

## 1.1 Notation

| Symbol | Definition |
|:---|:---|
| $N$ | Total nodes in the cluster |
| $D$ | Diameter of the reachable overlay graph |
| $W_K$ | Number of distinct actors (daemons) that have ever written to key $K$ |
| $V_A$ | Version vector (causal context) of state $A$ |
| $A \parallel B$ | Mutations $A$ and $B$ are concurrent: $\neg(V_A \le V_B) \land \neg(V_B \le V_A)$ |
| $V_A \le V_B$ | Component-wise dominance: $\forall i,\ V_A[i] \le V_B[i]$ |
| $\text{dom}(d, V)$ | Dot $d = (\text{actor}, \text{seq})$ is dominated by context $V$: $V[\text{actor}] \ge \text{seq}$ |

## 1.2 Consistency Model

Colloid is an **AP system** under the CAP theorem: it prioritizes Availability and Partition tolerance over strong Consistency during network splits, except "no failover" workloads.

The consistency model is **Strong Eventual Consistency (SEC)**: if any two nodes have received the same set of mutations (regardless of order or duplication), their computed local states are identical.

SEC is a mathematical property of the CRDT merge function (commutativity, associativity, idempotency). It holds unconditionally, regardless of network behavior.

## 1.3 Safety Invariants

**SAFE-1 — Conflict Blocking.** A CRDT key whose MV-Register holds concurrent values is in `CONFLICT` state. No actuator on any node may act on a *configuration* key in `CONFLICT` state. The cluster preserves the current physical reality until a human operator resolves the conflict.

A key $K$ is in `CONFLICT` if and only if $|\text{K.entries}| > 1$. While $K$ is in `CONFLICT`, the actuator treats $K$ as absent from the desired state. Workloads already running under a previous non-conflicting value continue unchanged.

**SAFE-2 — Local Conflict Detection.** Every node detects `CONFLICT` independently by examining the entry count of its local MV-Register. Zero inter-node coordination is required.

**SAFE-3 — Local Resolution Verification.** A resolving mutation $R$ clears `CONFLICT` on key $K$ if and only if $\text{dom}(d_i, V_R)$ for every dot $d_i$ in the MV-Register's entries. Every node verifies this independently.

**SAFE-4 — No Silent Data Loss.** The MV-Register never discards a concurrent value. All concurrent values are preserved and surfaced to the operator. LWW-Registers are explicitly rejected for configuration state.

**SAFE-5 — Stateful Workload Affinity.** A stateful workload's state volume binds its execution to a deterministic cell selection. A stateful workload is never executed concurrently on different cells in the same partition (still possible across partitions per EXEC-1). Replicas of stateful workloads use an explicit volume replication protocol (Section 13.6), not implicit re-scheduling.

**SAFE-6 — Sandbox Determinism.** WebAssembly workloads are executed in a deterministic sandbox: identical bytecode + identical inputs yield identical outputs. Side effects are gated by an explicit host capability set declared in the WorkloadSpec.

## 1.4 Availability Invariants

**AVAIL-1 — Partition Independence.** During a network partition, every connected sub-network continues to accept mutations and actuate non-conflicting desired state.

**AVAIL-2 — Partition Healing.** Upon reconnection, CRDT merge automatically resolves divergent state without human intervention — unless the partition caused concurrent mutations to the same key, which surfaces as `CONFLICT` per SAFE-1.

**AVAIL-3 — No Single Point of Failure.** No master, leader, or coordinator exists. The loss of any individual node does not degrade functionality for surviving nodes.

**AVAIL-4 — Protocol Quiescence.** A cluster with no pending mutations, no active failures, and no in-flight anti-entropy generates zero gossip and probe traffic. Between anti-entropy timer ticks and SWIM probes, a stable cluster is silent on the state plane. NAT keepalives (Section 6.4) are a separate, bounded traffic class.

**AVAIL-5 — NAT Transparency.** Two cells may form a mesh adjacency across symmetric NAT, full-cone NAT, and CGNAT environments, provided at least one publicly reachable cell exists in the cluster to serve as a rendezvous (Section 6).

**AVAIL-6 — Gateway Continuity.** The cluster advertises service IPs (Virtual IPs) such that external traffic continues to reach the service when the previously-advertising cell fails. Cells negotiate gateway responsibility without a central load balancer (Section 14).

## 1.5 Convergence Bounds

**CONV-1 — Topology-Bound Propagation.** State propagation resolves in $O(D)$ overlay hops.

| Physical Topology | Overlay Diameter | Convergence |
|:---|:---|:---|
| Well-connected datacenter | $D \sim \log N$ | $O(\log N)$ |
| Sparse WAN with bottlenecks | $D > \log N$ | $O(D)$ |
| Linear chain | $D = N - 1$ | $O(N)$ |

This is an information-theoretic lower bound.

**CONV-2 — Guaranteed Eventual Convergence.** If the network is eventually connected (every node can transitively reach every other node at some future time), all nodes converge to identical state in finite time. Gossip provides fast propagation; anti-entropy guarantees completeness.

**CONV-3 — Gateway Convergence Bound.** Following a cell failure that held a Virtual IP, external reachability is restored within $T_{\text{gw}} = T_{\text{SWIM}} + T_{\text{ARP}} + T_{\text{BGP}}$, where $T_{\text{SWIM}}$ is the failure detection time (Section 9), $T_{\text{ARP}}$ is the gratuitous ARP propagation time on the local segment, and $T_{\text{BGP}}$ is the BGP withdrawal/advertisement convergence time at the upstream router.

## 1.6 Architectural Boundaries

**ARCH-1 — Traffic Class Separation.** All data belongs to exactly one of two classes:

| Class | Examples | Transport | Scope | Persistence |
|:---|:---|:---|:---|:---|
| State | CRDT mutations (config, health, placement, volume metadata) | Gossip broadcast | All nodes | Replicated |
| Stream | Logs, exec sessions, metrics, volume bytes | Point-to-point | Source → requester | Ephemeral / out-of-band |

No mechanism may store stream data in the CRDT or propagate state data through the streaming path.

*Justification:* This prevents unbounded state growth. If Colloid's CRDT accepted streaming data, replicated state would grow unboundedly; if state mutations were routed point-to-point, convergence would break.

**ARCH-2 — Unified State Ingress.** The sole mechanism for modifying desired cluster state is a CRDT mutation injected into the mesh. No separate API server, configuration endpoint, or management plane exists.

**ARCH-3 — Push-Based Propagation.** Mutations propagate immediately upon injection via gossip. No node polls any other node. Anti-entropy exists solely to repair state missed during failures.

**ARCH-4 — Local Queryability.** Every node holds complete state (RES-3). Querying cluster state generates zero network traffic. `colloid status` reads local memory.

**ARCH-5 — Kernel-Offloaded Data Plane.** Where the Linux kernel provides a verified, programmable in-kernel path (eBPF, XDP, sockmap, sk_lookup), Colloid uses it for the data plane (service VIPs, load distribution, observability counters, packet filtering). The control plane (CRDT, gossip, routing, scheduling) remains in user space. Kernel programs are loaded by the daemon and their state is exposed to the control plane through eBPF maps.

**ARCH-6 — Submission-Queue I/O.** All user-space I/O (UDP, UDS, file, timerfd, eventfd, accept) is submitted through a single `io_uring` instance per daemon. The reactor thread interacts with the kernel through submission and completion queue rings; no `read`/`write`/`recvmsg`/`sendmsg` syscalls are issued from the hot path.

## 1.7 Bootstrap Guarantees

**BOOT-1 — Zero-Configuration Genesis.** A single node forms a functional cluster with no external dependencies, no configuration files, no tokens, and no preexisting state. `colloid` with no arguments is a valid and complete bootstrap.

**BOOT-2 — Single-Contact Join.** Joining an existing cluster requires exactly one network address of any reachable member, or a publicly resolvable rendezvous address (see Section 6). No join tokens, certificates, shared secrets, or configuration files. Authentication during join is deferred to the enterprise extension (NON-5).

**BOOT-3 — Ephemeral Participation.** A CLI tool may join the mesh as a temporary single-peer cell, inject or query state, and depart without affecting cluster health tracking or routing table stability.

**BOOT-4 — NAT-Bound Bootstrap.** A node behind NAT may join the mesh by performing a STUN-style address discovery against any reachable peer (Section 6.2). The discovered observed address is published in the cell's contact record and used by other cells for hole-punched direct connections.

## 1.8 Execution Semantics

**EXEC-1 — At-Least-Once Execution.** If a workload is present in converged, non-conflicting desired state and at least one healthy node exists, the workload will be executed by at least one node. During partitions, the same workload may execute simultaneously in different partitions.

**EXEC-2 — Deterministic Placement.** Given identical inputs (workload set $W$, healthy node set $H$, replica count $R$, runtime class), every node independently computes identical placement. Zero inter-node communication required.

**EXEC-3 — Minimal Disruption on Failure.** When a node is declared dead, Rendezvous hashing redistributes only that node's workloads. Other workloads are unaffected.

**EXEC-4 — Multi-Runtime Workloads.** A workload declares its runtime class: `oci` (containers), `wasm` (WebAssembly), or `process` (host-native binary). The actuator dispatches to the appropriate runtime backend (Section 13). Placement scoring is uniform across runtime classes.

**EXEC-5 — Stateful Anchoring.** A workload declared `stateful` is anchored: its score is biased toward the cell(s) currently holding its state volume (Section 10.5). A stateful workload migrates only when the anchored cell is declared dead, and only after volume re-replication completes on the target cell.

## 1.9 Routing Properties

**ROUTE-1 — Logarithmic Degree.** Each node maintains $O(\log N)$ routing table entries.

**ROUTE-2 — Logarithmic Lookup.** Any key or node can be located in $O(\log N)$ overlay hops in a well-connected topology.

**ROUTE-3 — Graceful Degradation.** Constrained devices may maintain fewer connections (smaller bucket size). Lookup latency increases; correctness is preserved.

**ROUTE-4 — Physical Awareness.** Within the XOR-determined bucket structure, peer selection prefers lower-RTT, higher-reliability, NAT-traversable contacts. Routing respects physical network topology without breaking the mathematical overlay geometry.

**ROUTE-5 — Reachability Classes.** Each contact carries a reachability class: `PUBLIC` (directly addressable), `PUNCHED` (reachable after STUN coordination), `RELAYED` (only reachable through a relay), or `UNKNOWN`. Peer selection prefers `PUBLIC > PUNCHED > RELAYED` after RTT ties are broken.

## 1.10 Stream Guarantees

**STREAM-1 — Target Resolution Is Local.** Resolving which cell(s) host a given workload requires zero network traffic.

**STREAM-2 — Direct When Reachable.** If the target cell is reachable directly (`PUBLIC` or `PUNCHED`), the stream is established without an intermediate node.

**STREAM-3 — Relay When Not Reachable.** If the target cell is only reachable as `RELAYED`, the stream is forwarded through the DHT overlay. Intermediate nodes forward stream packets without inspecting or storing payload content beyond the relay header.

**STREAM-4 — Ordered Delivery.** Stream packets carry a sequence number. The receiver reorders at the application layer.

**STREAM-5 — No Persistence.** Stream data is never written to the CRDT, never persisted on relay nodes (ARCH-1).

**STREAM-6 — Hole-Punched First.** Before falling back to relay, two cells attempt UDP hole punching coordinated through a third cell that is reachable to both (Section 6.3).

## 1.11 Resource Contracts

**RES-1 — No Heap Allocation in Hot Path.** The reactor loop (submit → reap → parse → merge → respond) performs zero `malloc`/`free`/`realloc`/`calloc` calls. All variable-size state is served from pre-allocated arenas sized at startup. `io_uring` SQE/CQE buffers are mmap'd at initialization.

**RES-2 — Bounded Packet Size.** Every UDP datagram is ≤ 1200 bytes, guaranteeing fragmentation-free delivery across common paths including tunnel/VPN encapsulations.

**RES-3 — Full State Replication.** Every node holds a complete replica of the global CRDT state. Any node can answer any query, detect any conflict, or compute placement locally.

For clusters where total CRDT state exceeds available memory, RES-3 becomes the binding constraint on cluster size. Sharding is a future extension that would relax RES-3 and modify ARCH-4, SAFE-2, and EXEC-2. This specification assumes RES-3 holds.

**RES-4 — Probabilistic Node Identity Uniqueness.** Node IDs are 64-bit values. For $N < 2^{32}$:

$$P(\text{collision}) \sim \frac{N^2}{2^{65}}$$

For $N = 100{,}000$, $P \sim 5.4 \times 10^{-11}$.

**RES-5 — Bounded Kernel Footprint.** eBPF programs loaded by Colloid are sized at compile time. Map sizes are sized at startup based on cluster scale parameters. No kernel allocation in the steady state.

## 1.12 CRDT Identity Rule

**CRDT-ACTOR — Actor Identity Binding.** The actor ID in any version vector entry is the Cell ID of the *daemon* that injected the mutation into the mesh. CLI tools and automation agents do not possess their own actor IDs; they delegate to their connected daemon.

*Justification:* Without this rule, each ephemeral CLI invocation generates a new actor ID, causing version vectors to grow with the number of CLI invocations (unbounded). With this rule, version vectors grow with $W_K$, the number of distinct *daemons* that have written to key $K$. In an orchestration system, $W_K$ is small: health keys have $W_K = 1$ (the cell itself); configuration keys have $W_K \le$ the number of operational endpoints (typically 1–5).

## 1.13 Explicit Non-Guarantees

**NON-1 — No Linearizability.** Operations are not globally ordered.

**NON-2 — No Exactly-Once Execution.** Duplicate workload execution is possible during partitions (EXEC-1). For stateful workloads, partition-time concurrent execution may produce divergent state branches that surface as `CONFLICT` on the volume metadata key after healing (Section 10).

**NON-3 — No Bounded Convergence Time.** Convergence depends on network conditions.

**NON-4 — No Causal Message Delivery.** A receiver may observe mutations out of causal order. Correctness is maintained by SEC.

**NON-5 — No Access Control.** Any node reaching the mesh can join and inject mutations. Authentication and RBAC are enterprise extensions.

**NON-6 — No Durable CRDT Storage by Default.** Colloid does not `fsync` CRDT state to disk on every mutation. Nodes recover CRDT state from peers via anti-entropy. Total cluster power-loss is unrecoverable for the CRDT; the operator re-applies configuration from source files (ARCH-2). Volume contents (Section 10) are persisted separately and do `fsync`.

**NON-7 — No L7 Load Balancing.** Colloid provides L3/L4 service VIPs only. HTTP-level routing, TLS termination, and host-header dispatch are out of scope.

**NON-8 — No Wasm Linearizability.** Wasm workloads with capability-granted state access participate in the same CRDT model as native workloads. No additional ordering guarantees beyond SEC.

---

# 2. Node Identity & Lifecycle

*Implements: RES-4, BOOT-1, BOOT-2, BOOT-3, AVAIL-3.*

## 2.1 Cell ID Generation

Each Colloid daemon generates a 64-bit Cell ID on first boot using Xoshiro256\*\*, seeded from the operating system's cryptographic entropy source (`getrandom(2)`).

The ID is generated once and persisted to a local file (`$COLLOID_DIR/cell_id`). Subsequent daemon restarts reuse the persisted ID, preserving the node's identity for version vector continuity.

If no persisted ID exists, the daemon generates a new one.

## 2.2 Cell States

```
BOOTING ──→ ACTIVE ──→ LEAVING ──→ GONE
                │
                └──(crash)──→ DEAD (declared by peers)
                                │
                                └──(restart)──→ BOOTING (resurrection)
```

| State | Description | Entry Condition |
|:---|:---|:---|
| `BOOTING` | Generating ID, performing STUN discovery, contacting seed peer, populating routing table, performing initial anti-entropy. Not yet scheduling. | Daemon start |
| `ACTIVE` | Full mesh participant. Gossips, routes, schedules, actuates, advertises VIPs. | Bootstrap complete |
| `LEAVING` | Graceful shutdown initiated. Sends `LEAVE` to all K-bucket peers. Withdraws BGP advertisements and gratuitous-ARPs VIP reassignment. Stops accepting new workloads. Drains running workloads. | `colloid shutdown` or SIGTERM |
| `GONE` | Daemon process has exited cleanly. Peers received `LEAVE` and exclude from scheduling immediately. | `LEAVE` acknowledged |
| `DEAD` | Declared dead by peers via failure detection (Section 9). The cell did not send `LEAVE`. | SWIM timeout + corroboration |

## 2.3 Ephemeral Cells

The CLI is an ephemeral single-peer cell. It:

1. Does **not** generate a persistent Cell ID. It uses a temporary in-memory ID.
2. Connects to the local daemon via UDS (Section 5.2), not UDP.
3. Reads CRDT state from the daemon's local replica.
4. Injects mutations by instructing the daemon to perform the CRDT write.
5. Departs without sending `LEAVE` on the mesh.

Ephemeral cells are excluded from routing tables, health tracking, scheduling, and tombstone watermark calculations.

## 2.4 Reachability Class Discovery

On bootstrap, the daemon determines its own reachability class by STUN-style probing (Section 6.2):

- **PUBLIC** — observed source address equals bound socket address.
- **PUNCHED** — observed source address differs from bound socket address, but the NAT preserves the mapping across multiple probes (cone-like).
- **RELAYED** — observed source address varies per destination, indicating symmetric NAT; direct reachability impossible.

The reachability class is published in the cell's contact record (Section 4.4) and updated whenever it changes (e.g., upstream reconfiguration).

## 2.5 Collision Handling

During the bootstrap handshake (Section 6.6), if a joining node discovers its generated Cell ID already exists in the cluster, it regenerates the ID and restarts the bootstrap.

---

# 3. Wire Protocol

*Implements: RES-2. Defines the byte-level encoding for all inter-node communication.*

## 3.1 Common Header

Every UDP datagram begins with a 16-byte header:

```
 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    version    |   msg_type    |         payload_len           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+                         sender_id                             +
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                         msg_nonce                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
```

| Offset | Size | Field | Description |
|:---|:---|:---|:---|
| 0 | 1 | `version` | Protocol version. `0x01`. |
| 1 | 1 | `msg_type` | Message type (Section 3.2). |
| 2 | 2 | `payload_len` | Length of payload after the header. Big-endian. |
| 4 | 8 | `sender_id` | Cell ID of the sending node. Big-endian. |
| 12 | 4 | `msg_nonce` | Opaque value for ACK correlation and deduplication. Big-endian. |

**Total header: 16 bytes. Maximum payload: 1184 bytes (1200 − 16).**

## 3.2 Message Types

| Code | Name | Direction | Purpose |
|:---|:---|:---|:---|
| `0x01` | `PING` | Request | Liveness probe; carries observed address (STUN response payload) |
| `0x02` | `PONG` | Response | Liveness ack; carries observed address |
| `0x03` | `FIND_NODE` | Request | DHT node lookup |
| `0x04` | `NODES` | Response | Return K closest nodes |
| `0x05` | `CRDT_DELTA` | Push | Single CRDT mutation (gossip) |
| `0x06` | `CRDT_DELTA_ACK` | Response | Acknowledgment of `CRDT_DELTA` |
| `0x07` | `AE_BEGIN` | Request | Initiate anti-entropy exchange |
| `0x08` | `AE_STATE` | Push | Full MV-Register state for one key |
| `0x09` | `AE_END` | Signal | Terminate anti-entropy batch |
| `0x0A` | `PING_REQ` | Request | Indirect liveness probe (SWIM) |
| `0x0B` | `PING_REQ_ACK` | Response | Indirect probe result |
| `0x0C` | `LEAVE` | Broadcast | Graceful departure announcement |
| `0x0D` | `PUNCH_REQ` | Request | Request third-party hole-punch coordination |
| `0x0E` | `PUNCH_SYN` | Push | Synchronized punching packet (both sides) |
| `0x0F` | `PUNCH_KEEPALIVE` | Push | NAT pinhole maintenance |
| `0x10` | `STREAM_OPEN` | Request | Open point-to-point stream |
| `0x11` | `STREAM_DATA` | Push | Stream payload chunk |
| `0x12` | `STREAM_CLOSE` | Signal | Close stream |
| `0x13` | `STREAM_ACK` | Response | Stream flow control acknowledgment |
| `0x14` | `RELAY_OFFER` | Request | Offer to relay a stream |
| `0x20` | `VOL_REPL_REQ` | Request | Request stateful volume snapshot |
| `0x21` | `VOL_REPL_CHUNK` | Push | Snapshot chunk (out-of-band stream type) |
| `0x22` | `VOL_REPL_DONE` | Signal | Snapshot transfer complete |
| `0x30` | `GW_CLAIM` | Push | Claim ownership of a Virtual IP (informational) |

## 3.3 Serialization Rules

1. **Byte order:** All multi-byte integers are big-endian.
2. **Alignment:** No alignment assumptions. Receivers extract fields via `memcpy`, then convert with `be16toh`/`be64toh`.
3. **No padding:** Payloads are packed; no implicit padding.
4. **Validation order:** (a) datagram length ≥ 16, (b) `version == 0x01`, (c) `msg_type` known, (d) `payload_len ≤ (datagram length − 16)`, (e) type-specific validation. Any failure drops the datagram silently.
5. **No dynamic allocation:** All parsing writes into pre-allocated stack or arena buffers.

## 3.4 Shared Structures

**NodeContact** (28 bytes):

```
0    cell_id            8 bytes (uint64)
8    addr              16 bytes (IPv6 or IPv4-mapped-IPv6)
24   port               2 bytes (uint16)
26   reach_class        1 byte  (0=UNKNOWN, 1=PUBLIC, 2=PUNCHED, 3=RELAYED)
27   flags              1 byte  (bit 0: BGP-speaker, bit 1: gateway-capable)
```

**VVEntry** (16 bytes):

```
0    actor_id   8 bytes
8    seq        8 bytes
```

**ObservedAddr** (18 bytes) — used in PING/PONG payloads for STUN:

```
0    addr      16 bytes
16   port       2 bytes
```

## 3.5 Message Payloads

### 3.5.1 PING (0x01) / PONG (0x02)

**Payload:** 18 bytes — `ObservedAddr` of the *peer* as observed by the sender. PONG echoes the PING `msg_nonce`.

The observed address is consumed by the receiver to update its own reachability class (Section 6.2).

### 3.5.2 FIND_NODE (0x03)

```
0    target_id    8 bytes
```

### 3.5.3 NODES (0x04)

```
0    count          2 bytes
2    NodeContact[count]
```

Max contacts per message: $\lfloor 1184 / 28 \rfloor = 42$.

### 3.5.4 CRDT_DELTA (0x05)

```
0    key_hash         8 bytes
8    dot_actor        8 bytes
16   dot_seq          8 bytes
24   ctx_count        1 byte
25   value_len        2 bytes
27   key_name_len     1 byte
28   context          ctx_count × 16 bytes (VVEntry[])
...  value            value_len bytes
...  key_name         key_name_len bytes
```

**Semantic constraint:** A `CRDT_DELTA` contains exactly one entry. This is guaranteed because only fresh writes generate deltas (Section 7.4).

### 3.5.5 CRDT_DELTA_ACK (0x06)

```
0    key_hash    8 bytes
```

The header `msg_nonce` correlates the ACK to the original delta.

### 3.5.6 AE_BEGIN (0x07)

```
0    key_count        4 bytes
4    merkle_root      8 bytes  (truncated SipHash of sorted state digest)
12   gvv_count        1 byte
13   global_vv        gvv_count × 16 bytes
```

Carries a Merkle digest (Section 8.7) and the sender's global version vector (Section 8.6).

### 3.5.7 AE_STATE (0x08)

Carries the complete MV-Register for one key:

```
0    key_hash         8 bytes
8    entry_count      1 byte
9    ctx_count        1 byte
10   key_name_len     1 byte
11   entries          entry_count × (8 + 8 + 2 + value_len)
...  context          ctx_count × 16 bytes
...  key_name         key_name_len bytes
```

### 3.5.8 AE_END (0x09)

**Empty payload.**

### 3.5.9 PING_REQ (0x0A) / PING_REQ_ACK (0x0B)

```
PING_REQ:        target NodeContact (28 bytes)
PING_REQ_ACK:    target_id (8) + reachable (1) + observed (18)
```

### 3.5.10 LEAVE (0x0C)

**Empty payload.**

### 3.5.11 PUNCH_REQ (0x0D)

Asks the receiver (a publicly reachable third party) to coordinate hole-punching between sender and a target:

```
0    target NodeContact     28 bytes
4    rendezvous_nonce        8 bytes (echoed in both sides' PUNCH_SYN)
```

### 3.5.12 PUNCH_SYN (0x0E)

```
0    rendezvous_nonce    8 bytes
```

Sent simultaneously by both peers at the time instructed by the coordinator. Carries no semantic payload beyond the nonce; its purpose is to open NAT pinholes in both directions.

### 3.5.13 PUNCH_KEEPALIVE (0x0F)

**Empty payload.** Sent to a `PUNCHED` peer at `PUNCH_KEEPALIVE_INTERVAL` to maintain the NAT mapping.

### 3.5.14 STREAM_OPEN (0x10)

```
0    stream_id        4 bytes
4    target_id        8 bytes
12   stream_type      1 byte   (0x01=logs, 0x02=exec, 0x03=metrics, 0x04=volrepl)
13   key_name_len     1 byte
14   key_name         key_name_len bytes
```

### 3.5.15 STREAM_DATA (0x11)

```
0    stream_id        4 bytes
4    seq_num          4 bytes
8    payload_len      2 bytes
10   payload          payload_len bytes
```

Max payload per chunk: 1174 bytes.

### 3.5.16 STREAM_CLOSE (0x12)

```
0    stream_id    4 bytes
```

### 3.5.17 STREAM_ACK (0x13)

```
0    stream_id    4 bytes
4    ack_seq      4 bytes
```

### 3.5.18 RELAY_OFFER (0x14)

Sent by a cell offering to act as a relay for a stream that cannot be hole-punched:

```
0    stream_id     4 bytes
4    source_id     8 bytes
12   target_id     8 bytes
```

### 3.5.19 VOL_REPL_REQ (0x20)

```
0    volume_key_hash    8 bytes
8    base_generation    8 bytes   (0 for full snapshot, else incremental)
```

### 3.5.20 VOL_REPL_CHUNK (0x21) / VOL_REPL_DONE (0x22)

Volume replication uses the same flow-control framing as `STREAM_DATA`/`STREAM_ACK`/`STREAM_CLOSE`. `VOL_REPL_CHUNK` and `STREAM_DATA` are structurally identical when `stream_type = 0x04`; the dedicated message codes exist for relay-node accounting (these streams may be large and are tracked separately).

### 3.5.21 GW_CLAIM (0x30)

```
0    vip               16 bytes (IPv6 or IPv4-mapped)
16   claim_priority     2 bytes (lower = stronger)
```

Informational announcement that the sender is currently advertising `vip` to upstream routers. Used for distributed gateway awareness (Section 14.4); the authoritative claim is the CRDT `gateway.<vip>` key.

---

# 4. Routing Table & Contact Records

*Implements: ROUTE-1..5, AVAIL-5.*

## 4.1 K-Bucket Structure

Each node maintains a routing table of at most 64 K-buckets, indexed by the position of the most-significant differing bit between the local Cell ID and a contact's Cell ID.

Each bucket holds at most $k$ entries:

| Node Type | Default $k$ | Minimum $k$ |
|:---|:---|:---|
| Standard (datacenter) | 20 | 4 |
| Constrained (edge/IoT) | 8 | 4 |

## 4.2 Contact Record

```c
struct Contact {
    uint64_t            cell_id;
    struct sockaddr_in6 addr;             // direct address from FIND_NODE/PING
    struct sockaddr_in6 observed_addr;    // STUN-discovered public address
    uint64_t            last_seen_ns;
    uint64_t            rtt_ewma_us;
    uint16_t            success_count;
    uint16_t            failure_count;
    uint8_t             reach_class;      // PUBLIC | PUNCHED | RELAYED | UNKNOWN
    uint8_t             flags;            // BGP-speaker, gateway-capable
    uint64_t            punched_at_ns;    // last successful hole-punch
};
```

## 4.3 Insertion Policy

When a new contact is discovered:

1. If the bucket has fewer than $k$ entries, insert.
2. If full, compare new entry against the worst existing entry: rank by (reach_class better) > (failure_count lower) > (rtt_ewma_us lower).
3. Entries with recent successful exchanges are not evicted regardless of discovery order.

## 4.4 Contact Record Lifecycle

- Every received message refreshes `last_seen_ns`.
- Every PONG with an `ObservedAddr` updates `observed_addr` and possibly `reach_class`.
- Successful hole-punch updates `reach_class = PUNCHED` and `punched_at_ns`.
- $\ge$ `FAILURE_THRESHOLD` consecutive failures mark the contact stale; it may be evicted.

## 4.5 Iterative Lookup

```
PROCEDURE iterative_lookup(target_id):
    candidates ← k local nodes closest to target_id by XOR
    queried   ← {}
    REPEAT:
        pick α unqueried nodes from closest_k, prioritized by reach_class then RTT
        send FIND_NODE(target_id) in parallel
        merge NODES responses into closest_k; keep k closest
        add responders to queried
    UNTIL no closer node observed in last round OR all closest_k queried
    RETURN closest_k
```

Parameters: $k = 20$, $\alpha = 3$.

## 4.6 RTT Annealing

EWMA: $\text{rtt} = \alpha \cdot \text{sample} + (1 - \alpha) \cdot \text{prev}$, with $\alpha = 0.25$. RTT influences eviction, gossip peer selection, and lookup parallelism. It never influences bucket assignment.

## 4.7 Network Size Estimation

$$\hat{N} \approx k \cdot 2^{64-i}$$

where $i$ is the index of the nearest non-empty bucket. Used for display only.

---

# 5. Transport & I/O Architecture

*Implements: RES-1, RES-2, AVAIL-4, ARCH-5, ARCH-6.*

## 5.1 UDP Transport

All inter-node communication uses UDP.

- **Port:** 12421 default, configurable.
- **MTU:** Every datagram ≤ 1200 bytes (RES-2).
- **No TCP.** TCP's head-of-line blocking and connection-state overhead are unacceptable for one-off messages.

## 5.2 UDS Interface

Intra-node communication (CLI ↔ daemon) uses `SOCK_STREAM` Unix Domain Socket at `$COLLOID_DIR/colloid.sock`.

Framing: 1-byte command + 3-byte length + payload.

| Code | Command | Notes |
|:---|:---|:---|
| `0x01` | `SET` | Inject CRDT write |
| `0x02` | `GET` | Read MV-Register |
| `0x03` | `DELETE` | Tombstone write |
| `0x04` | `LIST` | Prefix scan |
| `0x05` | `STATUS` | Cluster summary |
| `0x06` | `RESOLVE` | Resolve `CONFLICT` |
| `0x07` | `EXEC` | Start exec stream |
| `0x08` | `LOGS` | Stream stdout/stderr |
| `0x09` | `WASM_INVOKE` | Synchronous Wasm RPC over UDS |
| `0x0A` | `VOL_LIST` | Enumerate local volumes |

Response framing: 1-byte status + 3-byte length + payload. Status: `OK`, `ERROR`, `NOT_FOUND`, `CONFLICT`.

## 5.3 io_uring Reactor

The daemon runs a **single-threaded, non-blocking event loop** backed by a single `io_uring` instance.

**Initialization:**

- `io_uring_setup(SQ_DEPTH=4096, IORING_SETUP_SQPOLL | IORING_SETUP_COOP_TASKRUN | IORING_SETUP_SINGLE_ISSUER)`.
- Submission queue (SQ) and completion queue (CQ) rings are mmap'd into user space.
- Buffer pool registered via `IORING_OP_PROVIDE_BUFFERS` with `BUFFER_POOL_SIZE` (default 1024) entries of 1200 bytes each. Inbound datagrams are written directly into pool buffers selected by the kernel.
- File descriptors are registered via `IORING_REGISTER_FILES_UPDATE`, eliminating fd table lookups per submission.

**Operations submitted:**

| Op | Purpose |
|:---|:---|
| `IORING_OP_RECVMSG_MULTISHOT` | Continuous UDP receive on the mesh socket; consumes registered buffers |
| `IORING_OP_SENDMSG_ZC` | Zero-copy UDP send for state and stream datagrams |
| `IORING_OP_ACCEPT_MULTISHOT` | UDS listener |
| `IORING_OP_READ` / `IORING_OP_WRITE` | UDS client sockets (fixed-buffer where possible) |
| `IORING_OP_TIMEOUT` / `IORING_OP_TIMEOUT_UPDATE` | Software timers (replaces a separate `timerfd`) |
| `IORING_OP_READ` on eventfd | Worker thread → reactor notifications |
| `IORING_OP_OPENAT`, `IORING_OP_READ`, `IORING_OP_FSYNC` | Volume persistence I/O (Section 10) — submitted from worker via shared SQ when applicable; otherwise from a dedicated worker `io_uring` |

**Submission discipline:**

- Reactor batches submissions; one `io_uring_enter` (or zero, with `SQPOLL`) per loop iteration.
- The reactor never blocks. On an empty completion queue, it issues `io_uring_enter(min_complete=1)` and yields to the kernel.

**RES-1 enforcement:** All submission buffers are pre-registered. Completion handling parses in place from registered receive buffers, runs CRDT merge into the arena, and returns the buffer to the pool via `IORING_OP_PROVIDE_BUFFERS` (or implicit re-arm).

## 5.4 Timer Management

Software timers are programmed as `IORING_OP_TIMEOUT` submissions tagged with a 64-bit user_data identifying the callback. The reactor maintains a min-heap of scheduled callbacks; when a TIMEOUT completion fires, the heap is consulted and the appropriate callback dispatched.

Scheduled timers:

| Timer | Interval | Purpose |
|:---|:---|:---|
| Anti-entropy | 30s | Random peer state exchange |
| Probe | 1s | SWIM direct probe |
| Heartbeat | 5s | Local heartbeat increment + gossip |
| Punch keepalive | 20s | NAT pinhole maintenance |
| Retry | exponential | Unacked CRDT_DELTA retransmit |
| eBPF stats reap | 1s | Aggregate per-VIP counters from kernel maps |
| Gateway re-affirm | 10s | Re-emit gratuitous ARP / BGP keepalive |

## 5.5 Worker Threads

The reactor offloads blocking or CPU-intensive work to worker threads via SPSC ring buffers:

- **Actuator worker:** OCI image pull/unpack, process spawn, container lifecycle.
- **Wasm worker:** Wasm compilation (one-shot, on workload SET) and short-RPC execution.
- **Volume worker:** snapshot, snapshot-receive, replication chunk hashing.
- **eBPF worker:** program load, map updates outside the hot path, perf-buffer drain.

Workers signal the reactor via `eventfd` reads driven by `IORING_OP_READ`. No worker holds a CRDT lock; CRDT mutations are produced by submitting messages back to the reactor.

## 5.6 Mock Transport

For deterministic testing, the reactor's `io_uring` interface is wrapped behind a thin abstraction layer. In the test harness, submissions are intercepted and routed to an in-memory delivery queue with configurable loss, duplication, and reorder policies. CRDT correctness tests run against this harness.

---

# 6. NAT Traversal & Reachability

*Implements: AVAIL-5, BOOT-4, ROUTE-5, STREAM-6.*

## 6.1 Reachability Model

Each cell publishes its `reach_class` in routing table responses and in the `health.<id>.contact` CRDT key:

| Class | Definition | Direct send possible? |
|:---|:---|:---|
| `PUBLIC` | Observed public address equals bound socket address; reachable from any peer. | Yes |
| `PUNCHED` | Behind cone-like NAT. Reachable after a hole has been punched. | Yes, after PUNCH_SYN exchange |
| `RELAYED` | Behind symmetric NAT or restrictive firewall. Direct UDP impossible. | No; uses relay |
| `UNKNOWN` | Not yet probed. | Treated as `RELAYED` until classified |

## 6.2 STUN-Style Address Discovery

Every PING carries an `ObservedAddr` payload containing the *receiver's* address as seen by the *sender*. When the daemon receives a PONG (or any other message containing an `ObservedAddr`), it:

1. Records the observed `(addr, port)` mapping.
2. If the observed mapping equals the locally bound socket address → `PUBLIC`.
3. If the observed mapping differs but is consistent across at least 3 peers → `PUNCHED`.
4. If the observed mapping varies per peer (varying ports across peers) → `RELAYED`.

Reclassification is performed at most every `REACH_REPROBE_INTERVAL` (60s) to avoid CRDT churn.

## 6.3 Hole Punching

When cell A wants to communicate with cell B, both behind NAT:

1. A consults its routing table for B. If B's `reach_class == PUBLIC`, send directly.
2. If B is `PUNCHED`, send to B's `observed_addr`. If recent `punched_at_ns` is fresh (< `PUNCH_TTL`), the pinhole is open.
3. If B is `PUNCHED` but pinhole is stale, or B is `RELAYED` and A is `PUBLIC`, A initiates punch:
   a. A finds a coordinator C: a `PUBLIC` cell present in both A's and B's routing tables (selected from A's K-bucket entries by lowest RTT). If none exists, fall back to relay (Section 11.4).
   b. A sends `PUNCH_REQ(target=B, nonce=R)` to C.
   c. C forwards `PUNCH_REQ(target=A, nonce=R)` to B.
   d. Both A and B, upon receiving the coordination message, simultaneously send `PUNCH_SYN(R)` to each other's `observed_addr`. The first packets are typically dropped by the other side's NAT; the *outbound* packets create pinholes.
   e. Subsequent packets traverse the pinholes. Both sides update `reach_class = PUNCHED` and `punched_at_ns` on receipt of any post-PUNCH_SYN datagram.
4. If both A and B are `RELAYED` (symmetric NAT on both ends), hole punching is impossible. A uses a `RELAYED` path through C (Section 11.4).

## 6.4 Pinhole Maintenance

For every `PUNCHED` peer with `now - last_sent_ns >= PUNCH_KEEPALIVE_INTERVAL`, the daemon sends a `PUNCH_KEEPALIVE`. Keepalive frequency is set conservatively (20s default) to outlive UDP mapping timeouts on common consumer NATs (≈30s).

Keepalives are the **only** state-plane traffic that violates AVAIL-4 in a quiescent cluster. They are bounded: $O(\text{PUNCHED contacts})$ per cell per `PUNCH_KEEPALIVE_INTERVAL`.

## 6.5 Bootstrap with NAT

`colloid connect <seed>`:

1. Generate Cell ID.
2. Send `PING` to seed. The seed's PONG carries the joiner's observed address.
3. Joiner classifies itself per Section 6.2 (initial classification uses just the seed; refined as more peers are contacted).
4. Joiner records its observed address. This is the address it will advertise.
5. Joiner performs iterative lookup for its own ID; encountered peers learn the joiner's `observed_addr` from PONGs they receive back.
6. Standard bootstrap continues (anti-entropy, ACTIVE).

If the seed itself is behind NAT, only `RELAYED` joins are possible until a `PUBLIC` cell is discovered through the seed.

## 6.6 Public Rendezvous

A cluster intended to span NAT boundaries must contain at least one `PUBLIC` cell. The CLI command `colloid connect <hostname>` accepts DNS-resolvable hostnames; operators are expected to expose at least one such cell via a stable DNS name (`seed.colloid.example.com`).

This is the only deployment constraint; it does not introduce a SPOF because once a NAT'd cell has joined and discovered other `PUBLIC` cells, it does not depend on the original seed.

---

# 7. State Model (CRDTs)

*Implements: SAFE-1..6, AVAIL-1, AVAIL-2, CONV-2, CRDT-ACTOR, RES-1, RES-3.*

## 7.1 MV-Register Structure

The global state is a map from **key hash** (uint64) to **MV-Register**.

```c
struct MVRegister {
    uint64_t key_hash;
    char     key_name[MAX_KEY_NAME];
    uint8_t  key_name_len;

    uint8_t  entry_count;
    struct {
        uint64_t dot_actor;
        uint64_t dot_seq;
        uint16_t value_len;
        uint8_t  value[MAX_VALUE_SIZE];
    } entries[MAX_ENTRIES];

    uint8_t  ctx_count;
    struct {
        uint64_t actor_id;
        uint64_t seq;
    } context[MAX_CTX_ENTRIES];
};
```

Compile-time limits:

| Constant | Value | Rationale |
|:---|:---|:---|
| `MAX_KEY_NAME` | 128 | Longest reasonable key path |
| `MAX_VALUE_SIZE` | 512 | Sufficient for WorkloadSpec + volume metadata |
| `MAX_ENTRIES` | 4 | Conflicts beyond 3-way are operationally improbable |
| `MAX_CTX_ENTRIES` | 32 | Upper bound on $W_K$ |
| `MAX_KEYS` | 16384 | Arena pre-allocation |

## 7.2 Version Vectors

A **version vector** is a map from Cell IDs to sequence numbers, representing observed causal history for a key. A **dot** is `(actor_id, seq)` identifying a single write.

Dominance: $\text{dom}(d, V) \iff V[d.\text{actor}] \ge d.\text{seq}$.

Per CRDT-ACTOR, actors are daemon Cell IDs. Per-key vectors grow with $W_K$, typically 1–5 entries (16–80 bytes).

## 7.3 State-Based Merge (Anti-Entropy)

Given two complete states $S_A, S_B$ for the same key:

$$E_A' = \{(v, d) \in S_A \mid \neg\text{dom}(d, S_B.\text{ctx}) \lor (v, d) \in S_B\}$$
$$E_B' = \{(v, d) \in S_B \mid \neg\text{dom}(d, S_A.\text{ctx}) \lor (v, d) \in S_A\}$$
$$\text{merge}(S_A, S_B).\text{entries} = E_A' \cup E_B'$$
$$\text{merge}(S_A, S_B).\text{ctx} = \text{pointwise\_max}(S_A.\text{ctx}, S_B.\text{ctx})$$

Merge is commutative, associative, idempotent → SEC.

## 7.4 Delta Merge (Gossip)

A delta is a `CRDT_DELTA` carrying exactly one entry and the writer's full context for the key. It is structurally a single-entry state and merges by the formula in 7.3.

**Local write at daemon X for key K with value V:**

```
PROCEDURE write(K, V):
    X.seq ← X.seq + 1
    dot   ← (X.cell_id, X.seq)
    K.entries ← [(V, dot)]              // replaces all entries
    K.ctx[X.cell_id] ← X.seq            // update context
    delta ← CRDT_DELTA(K.key_hash, dot, K.ctx, V, K.key_name)
    gossip(delta)                        // Section 8.1
```

The write supersedes everything X has observed; if K was conflicted, the write resolves the conflict because the new context dominates all existing dots.

## 7.5 Conflict Detection

K is in `CONFLICT` iff $|K.\text{entries}| > 1$. Checked locally after every merge. The actuator skips conflicted configuration keys (SAFE-1).

## 7.6 Key Categories and Conflict Policy

| Category | Key pattern | Conflict policy | Rationale |
|:---|:---|:---|:---|
| Configuration | `spread.*`, `stateful.*`, `vip.*` | **Block** (SAFE-1) | Silent resolution unsafe |
| Health status | `health.<id>.status` | **Auto-resolve to ALIVE** | Empirical proof of liveness |
| Heartbeat | `health.<id>.heartbeat` | **Never conflicts** ($W_K = 1$) | Single writer |
| Contact | `health.<id>.contact` | **Latest by dot.seq from owner** | Owner-only writes |
| Volume metadata | `volume.<id>.meta` | **Block** (SAFE-1) | Divergent volume state is unsafe |
| Gateway claim | `gateway.<vip>` | **Block** (SAFE-1) | Concurrent claims must surface |
| String table | `_str.<hash>` | **Auto-resolve to longest** | Cosmetic |

The health auto-resolution is a read-time policy applied by the actuator, not a CRDT merge rule. All values are preserved on disk per SAFE-4.

## 7.7 Key Hashing

`key_hash = SipHash-2-4(k0, k1, key_name_bytes)`. $(k_0, k_1)$ is a fixed 128-bit constant; configurable for namespace isolation in the enterprise extension. The same SipHash key is used for Rendezvous hashing (Section 11.1).

## 7.8 Arena Allocation

```c
static struct MVRegister crdt_arena[MAX_KEYS];
static size_t            crdt_count;
```

Hash table with open addressing maps `key_hash → arena_index`. Exhaustion of `MAX_KEYS` rejects insertion and logs an error; the operator must resize and restart.

---

# 8. Anti-Entropy & Protocol Reliability

*Implements: CONV-2, AVAIL-2, AVAIL-4.*

## 8.1 Gossip

When a `CRDT_DELTA` is produced (local write or received from a peer), forward to `GOSSIP_FANOUT = 3` peers selected as:

1. The K-bucket nearest to `key_hash XOR local_cell_id`.
2. Within that bucket, prefer `reach_class = PUBLIC` over `PUNCHED` over `RELAYED`, then lowest RTT.
3. If fewer than `GOSSIP_FANOUT` candidates, spill to adjacent buckets.

Forwarding terminates via the dedup ring (Section 8.4).

## 8.2 Anti-Entropy Exchange

Every `AE_INTERVAL` (30s):

1. Select a random K-bucket entry $B$.
2. Send `AE_BEGIN(key_count, merkle_root, global_vv)`.
3. If $B$'s `merkle_root` matches local, skip state exchange.
4. Otherwise, perform Merkle drill-down (Section 8.7) and send `AE_STATE` for differing keys only.
5. Send `AE_END`.
6. $B$ responds symmetrically.

Rate-limit: `AE_RATE_LIMIT` (100 msg/s per exchange).

## 8.3 ACK and Retry

Each `CRDT_DELTA` is enqueued in a retry ring as `(msg_nonce, target, attempt, next_retry_ns)`. On matching `CRDT_DELTA_ACK`, the entry is removed. On timeout `RETRY_BASE × 2^attempt`, retransmit and increment. After `RETRY_MAX = 3` attempts, abandon; anti-entropy is the backstop.

The retry ring is a pre-allocated fixed-size structure; eviction policy: drop oldest untried.

## 8.4 Deduplication

Each node maintains a fixed-size dedup ring of fingerprints:

$$\text{fp} = \text{key\_hash} \oplus \text{dot\_actor} \oplus (\text{dot\_seq} \times \text{0x9E3779B97F4A7C15})$$

Ring size: 4096 entries, linear probing, oldest overwritten on collision. Re-merge of an evicted-and-resent delta is harmless (idempotent).

## 8.5 Tombstones

A delete is a write with `value_len = 0`. The MV-Register handles this as a regular write; the actuator treats empty values as "no workload."

Tombstones cannot be freed until proven received globally (Section 8.6).

## 8.6 Watermark Calculation

Each node maintains a **global version vector**:

$$G_X[a] = \max_{K} K.\text{ctx}[a]$$

Global VVs are piggybacked on `AE_BEGIN`. The local watermark is:

$$W[a] = \min_{X \in \text{known}} G_X[a]$$

A tombstone with dot $(a, s)$ is GC'd when $W[a] \ge s$. Stale anti-entropy participation conservatively keeps the watermark low.

## 8.7 Merkle Anti-Entropy

The state arena is augmented with a Merkle tree over the sorted key-hash space. Tree depth: 16 (covers up to $2^{16} = 65536$ leaves, where each leaf may bucket multiple keys for clusters > 16K keys).

Each leaf digest is `SipHash(sorted key_hashes ∥ each MV-Register dot_set digest)`. Internal nodes hash their children.

On `AE_BEGIN`, the sender includes `merkle_root` (64 bits, truncated). The receiver:

1. Compares roots; if equal, skip (no traffic).
2. If different, sends `AE_MERKLE_REQ(depth, prefix_bits)` (a sub-message type embedded in a follow-up `AE_STATE`-like frame) to identify divergent subtrees.
3. Sends `AE_STATE` for keys within divergent leaves only.

The Merkle tree is updated incrementally on every CRDT write (the leaves containing the touched key are re-hashed; the path to the root is updated; total cost $O(\log \text{leaves})$ per write).

This reduces anti-entropy bandwidth from $O(|S|)$ to $O(\Delta)$ where $\Delta$ is divergent key count.

---

# 9. Failure Detection & Health

*Implements: EXEC-3, AVAIL-3.*

## 9.1 SWIM Probing

Every `PROBE_INTERVAL` (1s): select a random K-bucket entry as the probe target. Send `PING`. Wait `PROBE_TIMEOUT` (500ms) for `PONG`.

## 9.2 Indirect Probing

On direct probe failure, send `PING_REQ(target)` to `INDIRECT_PROBE_COUNT = 3` random K-bucket peers. Each peer attempts its own `PING` and returns `PING_REQ_ACK(reachable, observed_addr)`.

If any positive ACK arrives within `PROBE_TIMEOUT`, the target is alive. Otherwise, the target enters local `SUSPECTED` state with a `SUSPECT_TIMEOUT` (5s) timer.

## 9.3 Death Declaration

If `SUSPECT_TIMEOUT` expires with no successful contact:

1. Detecting node writes `health.<target_id>.status = DEAD`.
2. Mutation gossips; all nodes learn of the death.
3. All nodes:
   a. Remove the dead cell from the healthy set $H$.
   b. Recompute placement (Section 11).
   c. If the dead cell held any VIP, the new VIP owner per CRDT initiates ARP/BGP takeover (Section 14).
4. The dead cell's contact remains in routing tables but is marked stale; it may be evicted.

## 9.4 Resurrection

A restarted node, on observing `health.<self>.status = DEAD`, immediately writes `ALIVE`. Any node receiving a valid UDP message from a `DEAD`-marked cell writes `ALIVE` on its behalf.

## 9.5 Health Auto-Resolution

If `health.<id>.status` is conflicted with at least one `ALIVE` entry, the read-time policy treats the cell as alive. SAFE-4 still holds: all entries persist in the MV-Register.

## 9.6 Resource Hysteresis

Resource metrics (`health.<id>.cpu`, `.mem`, `.disk`) are gossiped only when:

$$\left|\frac{\text{new} - \text{last\_gossiped}}{\text{last\_gossiped}}\right| \ge 0.15$$

This suppresses minor fluctuations while propagating meaningful changes.

## 9.7 eBPF-Assisted Liveness

A loaded eBPF program (Section 12.3) increments per-peer ingress counters on every received datagram from a recognized Cell ID. The daemon reads these counters at probe time; if a counter has incremented since the last probe, the peer is implicitly alive and a synthetic PONG is treated as received. This reduces probe traffic in steady-state clusters and validates ARCH-5.

---

# 10. Stateful Workloads & Volumes

*Implements: SAFE-5, EXEC-5.*

## 10.1 Volume Model

A **volume** is a named directory tree owned by a workload. The volume lifecycle is tied to a `stateful` workload but is conceptually independent in the CRDT.

Volumes are identified by `volume_id = SipHash(workload_key_name ∥ replica_index)`. Volume metadata is published in the CRDT key `volume.<volume_id>.meta`:

```
struct VolumeMeta {
    uint64_t volume_id;
    uint64_t owner_cell;        // current anchor cell
    uint8_t  replica_index;     // 0..R-1
    uint64_t generation;        // monotonically increasing per snapshot
    uint64_t content_hash;      // SipHash of canonical snapshot at generation
    uint64_t size_bytes;
    uint8_t  replication_factor; // RF, including the owner
    uint64_t replicas[7];        // peer cell IDs holding replicas (RF ≤ 8)
};
```

Volume contents are **not** stored in the CRDT (would violate ARCH-1 and explode state size). Contents live on local disk at `$COLLOID_DIR/volumes/<volume_id>/`.

## 10.2 Storage Layout

```
$COLLOID_DIR/volumes/<volume_id>/
├── meta              (mirrors VolumeMeta, fsync'd on write)
├── current/          (live filesystem)
└── snapshots/<generation>/   (read-only snapshots for replication)
```

Snapshots use the host filesystem's native mechanism (overlayfs lower layer + `reflink` copy on supporting filesystems, or `mount --bind` + `cp --reflink=auto`). On filesystems without reflink, a full copy is performed by the volume worker.

Volume metadata writes are `fsync`'d (departing from NON-6 specifically for volumes, since volume contents are externally persisted).

## 10.3 Stateful Placement

A workload declared `stateful` carries `replication_factor = RF` and `replicas = R`. Placement proceeds as:

1. Compute the candidate placement for each replica index $i \in [0, R)$ using Rendezvous hashing on the tuple `(workload_key_hash, replica_index=i)`.
2. The cell with the highest score becomes the **owner** for replica $i$.
3. The next $RF - 1$ highest-scoring cells become **followers** holding additional copies of the volume.

The owner runs the workload; followers hold the data but do not execute. Followers exist to allow rapid takeover on owner failure.

## 10.4 Volume Replication

When a stateful workload is created:

1. Owner cell creates an empty local volume.
2. Owner publishes `volume.<volume_id>.meta` with `generation = 0`.
3. Follower cells observe the meta key (via CRDT gossip).
4. Each follower opens a `STREAM_OPEN` with `stream_type = 0x04 (volrepl)` to the owner.
5. Owner sends the empty initial state via `VOL_REPL_CHUNK`/`VOL_REPL_DONE`.

On each volume mutation:

1. Owner snapshots the current state into `snapshots/<generation+1>/`.
2. Owner writes `volume.<volume_id>.meta` with `generation = generation + 1` and updated `content_hash`.
3. Followers detect the generation bump, issue `VOL_REPL_REQ(volume_id, base_generation=current_local_gen)` to the owner.
4. Owner sends a delta (file additions, modifications, deletions between the two generations) via stream messages.
5. Followers apply the delta atomically (write to a staging tree, swap via rename, fsync).

Snapshots older than $G$ generations behind any known replica are GC'd (default $G = 4$).

## 10.5 Anchored Placement Adjustment

Because volumes are expensive to migrate, Rendezvous scores for stateful workloads are biased toward the current owner:

$$\text{adjusted\_score}(W, C) = \begin{cases} \text{score}(W, C) + \text{ANCHOR\_BIAS} & \text{if } C = \text{current owner in CRDT} \\ \text{score}(W, C) & \text{otherwise}\end{cases}$$

`ANCHOR_BIAS` is set to a value larger than any plausible Rendezvous score difference (in practice, `0x4000_0000_0000_0000`). This guarantees the owner does not change unless the owner is removed from $H$.

## 10.6 Owner Failover

When the owner is declared `DEAD`:

1. The Rendezvous calculation, with the owner removed from $H$, selects a new owner — by construction the highest-scoring follower (because followers were the next-RF-1 cells in the original ranking).
2. The new owner verifies it holds a recent local copy (within `MAX_FAILOVER_LAG_GENERATIONS = 2`).
3. If yes, it writes `volume.<volume_id>.meta` with itself as `owner_cell`, advancing the dot for that key. This claim acts as the takeover declaration.
4. The actuator on the new owner reconciles: the stateful workload appears in desired state on the new owner, which starts the workload pointed at the local volume.
5. New followers are selected and begin replication from the new owner.

If no follower has a sufficiently recent copy, the meta key may go to `CONFLICT` (if two cells concurrently attempt to claim ownership during a partition). The operator resolves via `colloid resolve`.

## 10.7 Partition Behavior

During a partition that splits owner from followers:

- The owner's partition continues writing to the volume; generation advances.
- Followers in the other partition see no updates.
- If the failure detector in the follower partition declares the owner dead, a new owner is elected from the followers. **Both sides now have divergent volume state.**
- On heal, both `volume.<volume_id>.meta` entries surface as `CONFLICT` (different owners, different generations). SAFE-1 holds: the actuator stops writing to the volume on all cells.
- The operator inspects both branches and resolves manually (`colloid resolve volume.<id>.meta`). One branch's data is lost; this is the inescapable consequence of AP partition tolerance for stateful workloads (NON-2).

## 10.8 Wasm Workload State

Wasm workloads with `runtime_class = wasm` declare which volumes they mount (if any). State access from Wasm is limited to:

- WASI filesystem APIs scoped to the mounted volume directories.
- WASI clock and random APIs (deterministic when configured per SAFE-6).
- Colloid-specific host functions (Section 13.5).

No raw filesystem or network access; capabilities are explicit.

---

# 11. Scheduling (Rendezvous Hashing)

*Implements: EXEC-1, EXEC-2, EXEC-3, EXEC-4, EXEC-5.*

## 11.1 Hash Function

$$\text{score}(W, C, i) = \text{SipHash}_{k_0, k_1}(W.\text{key\_hash}\ \|\ C.\text{cell\_id}\ \|\ i)$$

where $i$ is the replica index. The same SipHash key as Section 7.7.

## 11.2 Healthy Set

$$H = \{\ C\ :\ \text{health.}C\text{.status auto-resolves to ALIVE or is absent}\ \}$$

## 11.3 Placement

```
PROCEDURE compute_placement(W, R, H):
    if W.runtime_class == wasm:
        H' ← {C ∈ H : C.flags.wasm_capable}
    else:
        H' ← H

    placement ← []
    for i in 0..R-1:
        scores ← {C : adjusted_score(W, C, i) for C in H'}
        if W.stateful:
            owner ← argmax_C (scores[C] biased per Section 10.5)
        else:
            owner ← argmax_C scores[C]
        placement.append(owner)
    return placement
```

For non-stateful workloads, picking R independent argmaxes per replica index may select the same cell multiple times in tiny clusters; the actuator runs at most one instance per cell unless the workload explicitly opts in to oversubscription.

## 11.4 Failover

When a cell is removed from $H$:

1. Every surviving node recomputes placement.
2. Workloads whose top replica was the dead cell get a new owner (the next-highest scorer).
3. The new owner's actuator detects "desired but not running" and starts the workload (after volume re-replication completes, for stateful).
4. Workloads unaffected by the failure see no placement change (EXEC-3).

## 11.5 Replica Semantics

Workload types supported in M1:

- `spread` — run $R$ replicas across the cluster.
- `stateful` — run $R$ replicas with anchored volumes.

A workload key encodes its type via the key prefix (`spread.*` or `stateful.*`).

---

# 12. Kernel Data Plane (eBPF / XDP)

*Implements: ARCH-5, RES-5, NON-7 boundary.*

## 12.1 Program Set

Colloid loads the following eBPF programs at daemon startup. Each is compiled into the binary as bytecode and loaded via `bpf(2)` `BPF_PROG_LOAD`.

| Program | Type | Attach Point | Purpose |
|:---|:---|:---|:---|
| `colloid_vip_xdp` | `BPF_PROG_TYPE_XDP` | Egress interface (host) | VIP DNAT: rewrite destination IP/port for service VIPs to a selected backend pod IP |
| `colloid_vip_tc_egress` | `BPF_PROG_TYPE_SCHED_CLS` | `clsact` egress | SNAT return path: rewrite source back to VIP for outbound replies |
| `colloid_sock_lookup` | `BPF_PROG_TYPE_SK_LOOKUP` | per-netns | Steer connections matching VIP+port to the local daemon's socket if backend is local |
| `colloid_peer_counter` | `BPF_PROG_TYPE_XDP` | Mesh interface | Per-peer ingress packet/byte counters for liveness assist (Section 9.7) |
| `colloid_arp_gw` | `BPF_PROG_TYPE_XDP` | Gateway interface | Intercept gratuitous ARP and ARP requests for VIPs we own (Section 14) |
| `colloid_observe_tc` | `BPF_PROG_TYPE_SCHED_CLS` | `clsact` ingress | L4 flow counters per workload (metrics surface) |

## 12.2 Map Set

| Map | Type | Key | Value | Purpose |
|:---|:---|:---|:---|:---|
| `vip_backends` | `BPF_MAP_TYPE_HASH` | `(vip, port)` | array of `(backend_ip, backend_port, weight)` | VIP load distribution |
| `vip_consistent_hash` | `BPF_MAP_TYPE_ARRAY` | hash bucket | backend index | Maglev-style consistent hash for L4 stickiness |
| `peer_counters` | `BPF_MAP_TYPE_PERCPU_HASH` | `cell_id` | `(pkts, bytes, last_ns)` | Liveness assist |
| `vip_owned` | `BPF_MAP_TYPE_HASH` | `vip` | `(owner_cell, claim_priority)` | Local view of VIP ownership |
| `flow_table` | `BPF_MAP_TYPE_LRU_HASH` | 5-tuple | backend index | Connection tracking |
| `workload_stats` | `BPF_MAP_TYPE_PERCPU_HASH` | `workload_id` | flow stats | Per-workload observability |

Map sizes are computed at daemon startup from cluster scale parameters (`MAX_VIPS`, `MAX_BACKENDS_PER_VIP`, `MAX_PEERS`) and never resized at runtime, satisfying RES-5.

## 12.3 Service VIP Data Path

When a workload declares a VIP (in `WorkloadSpec.vip` field), the daemon:

1. Writes the CRDT key `vip.<vip>` containing the VIP definition (backends, port, mode).
2. On observing the key, every cell updates its local `vip_backends` map with all backend endpoints (cell-local backends marked with a "local" flag).
3. The cell that holds gateway responsibility (Section 14) advertises the VIP via gratuitous ARP / BGP.
4. Incoming packets to the VIP hit `colloid_vip_xdp` at line rate:
   - 5-tuple hash → consistent hash bucket → backend selection.
   - DNAT rewrite (destination IP/port → backend pod IP/port).
   - `bpf_redirect` or kernel forwarding to backend.
5. Return packets hit `colloid_vip_tc_egress`, which SNATs the backend address back to the VIP.

The consistent hash map is rebuilt by the daemon (user space, via the eBPF worker thread) whenever backends change, then swapped atomically by replacing the map content. Existing flows in `flow_table` are preserved during the swap to avoid breaking established connections.

## 12.4 Connection Tracking

The `flow_table` LRU map stores `5-tuple → backend_index` for the lifetime of a connection. Entries auto-expire by LRU pressure (default 65536 entries). For long-lived connections, the entry is refreshed on each packet.

When a backend is removed from `vip_backends` (workload stopped or cell died), existing flows continue routing to the (now-stale) backend index until LRU eviction or explicit invalidation; new flows are routed to the new backend set. This trades brief disruption for sustained connection stability — acceptable for the AP model.

## 12.5 Observability

`colloid_observe_tc` populates `workload_stats` with packet/byte counters keyed by destination workload. The daemon reads this map every `STATS_REAP_INTERVAL` (1s) and:

- Aggregates into local rolling windows.
- Surfaces in `colloid status --metrics` and over the stream protocol with `stream_type = 0x03 (metrics)`.
- Optionally publishes summary CRDT keys (`metric.<workload>.rate`) at coarse intervals.

## 12.6 Program Verification & Compatibility

All programs are compiled with `clang -target bpf` and embedded as a section in the daemon binary. On startup, each program is loaded with `BPF_PROG_LOAD` and verified by the kernel verifier; if any program fails to load (older kernel without required features), the daemon logs a warning and falls back to a user-space implementation of the same function (slower, but functionally identical for the cluster).

Minimum kernel: 5.15 (for `BPF_PROG_TYPE_SK_LOOKUP`, `IORING_OP_SENDMSG_ZC`, `IORING_SETUP_SINGLE_ISSUER`).

## 12.7 Map Updates from User Space

Map updates are submitted via `BPF_MAP_UPDATE_ELEM` ioctls from the eBPF worker thread. The reactor thread never blocks on map updates: it enqueues an `UPDATE_VIP` or `UPDATE_PEER` command on the eBPF worker's ring, and the worker executes the syscall.

For reads (e.g., per-peer counters), the worker periodically polls maps and pushes aggregated results back to the reactor via eventfd.

---

# 13. Actuator & Runtime Backends

*Implements: EXEC-1, EXEC-4, SAFE-6.*

## 13.1 Architecture

The actuator dispatches workloads by `runtime_class`:

```
.───────────────.       Ring Buffer        .─────────────────.
| Reactor       |─── WorkloadCommand[] ───>| Actuator Worker |
| (epoll        |                          | (dispatches by  |
|  via io_uring)|<── eventfd notify ──────| runtime_class) |
'───────────────'                          '────────┬────────┘
                                                    │
                                ┌───────────────────┼──────────────────┐
                                ▼                   ▼                  ▼
                       .────────────────.  .────────────────.  .──────────────.
                       | OCI Runtime    |  | Wasm Runtime   |  | Process      |
                       | (namespaces,   |  | (in-process    |  | (direct      |
                       |  cgroups, OCI) |  |  Wasm engine)  |  |  exec)       |
                       '────────────────'  '────────────────'  '──────────────'
```

## 13.2 WorkloadSpec

A workload specification stored in the CRDT:

```
0    runtime_class    1 byte   (0x01=oci, 0x02=wasm, 0x03=process)
1    flags            1 byte   (bit 0: stateful, bit 1: requires_vip)
2    replicas         2 bytes
4    cpu_millicores   2 bytes
6    mem_mb           2 bytes
8    image_len        1 byte
9    image            UTF-8 (OCI ref or Wasm module URL or binary path)
...  port_count       1 byte
...  ports            port_count × 4 bytes (host:container)
...  vip_count        1 byte
...  vips             vip_count × 18 bytes (vip + port)
...  capability_mask  4 bytes  (Wasm host capability bitfield)
...  volume_count     1 byte
...  volumes          volume_count × (16 bytes: id + mount_len + mount_path)
```

Maximum size: 512 bytes (fits in `MAX_VALUE_SIZE`).

## 13.3 OCI Backend

For `runtime_class = oci`, the actuator worker:

1. **Image pull:** HTTP/1.1 client against the OCI registry (Docker Hub, GHCR, etc.). OAuth2 bearer token retrieval. Manifest + layer blobs downloaded to `$COLLOID_DIR/images/`.
2. **Unpack:** Layers extracted with overlayfs `lowerdir` chain. `mount(2)` with `overlay` type.
3. **Namespace setup:** `clone(2)` with `CLONE_NEWPID | CLONE_NEWUTS | CLONE_NEWNS | CLONE_NEWNET | CLONE_NEWUSER`.
4. **Filesystem:** `pivot_root(2)` into the overlay mount.
5. **Cgroups v2:** Write CPU and memory limits to `/sys/fs/cgroup/colloid/<workload_id>/`.
6. **Networking:** `netlink(7)` creates veth pair (`vethX` on host, `eth0` in container); bridge to `colloid0`; assign pod IP from per-cell pool; NAT via nftables.
7. **Exec:** Runs the entrypoint from the OCI config.

Image storage is content-addressed by layer digest; common layers are deduplicated across workloads.

## 13.4 Process Backend

For `runtime_class = process`, the actuator executes a host-native binary directly under a cgroup with the declared CPU/memory limits. No filesystem or network isolation. Intended for system-level workloads (sidecars, observability agents) that need full host access.

## 13.5 Wasm Backend

For `runtime_class = wasm`, the actuator worker invokes the embedded Wasm runtime. The runtime is statically linked into the daemon (no external `wasmtime`/`wasmer` dependency); the engine implements a subset of:

- Wasm 1.0 core spec.
- WASI Preview 1 (clocks, env, fd_* for mounted volumes, args, random_get).
- Colloid host functions (see below).

**Lifecycle:**

1. On workload SET, the worker downloads the Wasm module (HTTP) and compiles it to native code once. Compiled artifacts are cached in `$COLLOID_DIR/wasm-cache/<sha256>.so`.
2. For each replica, the worker instantiates the compiled module with:
   - WASI environment from `WorkloadSpec.env`.
   - Mounted volumes as WASI preopens.
   - Host capabilities per `capability_mask`.
3. The module runs in a dedicated thread with cooperative scheduling. CPU and memory limits enforced by cgroup membership of the Wasm worker thread.

**Host capability bitfield:**

| Bit | Capability | Description |
|:---|:---|:---|
| 0 | `KV_READ` | Read CRDT keys matching workload-scoped prefix |
| 1 | `KV_WRITE` | Write CRDT keys (mutations performed by daemon, attributed to daemon Cell ID) |
| 2 | `STREAM` | Open streams to other workloads |
| 3 | `NET_OUTBOUND` | Outbound TCP/UDP via host network namespace |
| 4 | `VOL_RW` | Read/write declared volumes |
| 5 | `TIMER` | Schedule callback invocations |
| 6 | `METRICS` | Emit per-invocation metrics |

Capabilities not granted return WASI `errno = EPERM`.

**Wasm host ABI (selected functions):**

```
colloid_kv_get(key_ptr, key_len, out_buf, out_buf_len) → out_len or -errno
colloid_kv_set(key_ptr, key_len, val_ptr, val_len) → 0 or -errno
colloid_stream_open(target_workload_ptr, target_workload_len, stream_type) → stream_fd or -errno
colloid_metric_emit(name_ptr, name_len, value: f64) → 0 or -errno
```

**Determinism:** When `WorkloadSpec.flags.deterministic` is set, the runtime forbids access to `random_get`, system clock (substituted with a logical clock incremented per-invocation), and capability bits incompatible with determinism. This supports SAFE-6.

**Wasm RPC invocation:** `colloid wasm invoke <name> <args>` issues a synchronous `WASM_INVOKE` command over UDS. The daemon dispatches to the Wasm worker, which executes the module's exported `colloid_invoke` function and returns the result. Useful for short, deterministic compute.

## 13.6 Reconciliation

The reactor runs reconciliation whenever:

- A CRDT merge changes any `spread.*` or `stateful.*` key.
- A health key changes (alters $H$).
- A volume meta key changes.
- The worker reports a workload exit.

```
PROCEDURE reconcile():
    desired ← {}
    for each K matching "spread.*" or "stateful.*":
        if K is CONFLICT: skip
        if K.value is empty: skip
        W ← deserialize WorkloadSpec from K.value
        for i in 0..W.replicas-1:
            placement ← compute_placement(W, i, H)
            if placement == my_cell_id:
                if W.stateful and volume not yet replicated locally:
                    enqueue VOL_REPLICATE command; skip
                desired.add((K.key_hash, i))

    for each (k, i) in desired but not in running:
        enqueue START command with appropriate runtime backend
    for each (k, i) in running but not in desired:
        enqueue STOP command
```

---

# 14. Gateway Continuity (ARP / BGP)

*Implements: AVAIL-6, CONV-3.*

## 14.1 Gateway Problem

When a service VIP is associated with the cluster, external traffic destined for that VIP must arrive at *some* cell hosting (or able to forward to) the backend workloads. If that cell fails, traffic must redirect to a surviving cell within bounded time and without external load balancer involvement.

Colloid provides two mechanisms, used singly or in combination based on network environment:

- **L2 mode (gratuitous ARP):** for VIPs in the same broadcast domain as cluster cells.
- **L3 mode (BGP):** for VIPs announced to upstream routers via BGP (eBGP to a top-of-rack router, or BGP unnumbered).

## 14.2 VIP Ownership Election

For each VIP defined in `vip.<vip>` CRDT key, ownership is computed deterministically:

$$\text{owner}(\text{vip}) = \underset{C \in H_{\text{gw}}}{\arg\max}\ \text{SipHash}(\text{vip}\ \|\ C.\text{cell\_id})$$

where $H_{\text{gw}} \subseteq H$ is the set of gateway-capable cells (flag bit set in their contact record). If $H_{\text{gw}}$ is empty, the VIP is unowned and traffic to it is dropped — operator misconfiguration.

The owner is computed locally by every cell (EXEC-2). Only the elected owner advertises the VIP externally.

## 14.3 L2 Mode (Gratuitous ARP)

When a cell becomes VIP owner:

1. The daemon writes `gateway.<vip> = (my_cell_id, claim_priority, generation)`.
2. The daemon sends a `GW_CLAIM` informational message to all K-bucket peers (for fast convergence; the CRDT is the source of truth).
3. The daemon constructs and emits a gratuitous ARP response on the configured gateway interface:
   - `Sender Hardware Address`: cell's MAC on the gateway interface.
   - `Sender Protocol Address`: VIP.
   - `Target Protocol Address`: VIP (broadcast announcement).
4. The gratuitous ARP is repeated 3 times at 100ms intervals (RFC 5227 style) to overcome packet loss.
5. The `colloid_arp_gw` eBPF program at the gateway interface intercepts ARP requests for owned VIPs and responds with the cell's MAC.
6. The cell binds the VIP as a secondary IP on the gateway interface (so the kernel accepts inbound traffic).

When the previous owner is declared dead:

1. The new owner (computed deterministically) writes `gateway.<vip>` with the new owner_cell.
2. Upon observing the CRDT key change locally, the new owner performs steps 3–6 above. Switches and other hosts on the segment learn the new MAC ↔ VIP binding from the gratuitous ARP.
3. The previous owner, if still alive (false positive death declaration), observes the CRDT key change, releases the VIP binding, and stops responding to ARP for it. The conflict (if any) surfaces as a `CONFLICT` on `gateway.<vip>` (per Section 7.6, gateway claims block).

If `gateway.<vip>` is in `CONFLICT`, all cells release the VIP binding (SAFE-1). External traffic stops until the operator resolves. This is preferable to flapping or split-brain advertisement.

## 14.4 L3 Mode (BGP)

For VIPs that must be announced beyond the L2 segment, gateway-capable cells maintain an eBGP session with an upstream router. The daemon embeds a minimal BGP speaker:

- BGP-4 (RFC 4271) speaker, advertise-only (does not consume routes from the peer for cluster routing).
- TCP/179 session to the configured peer router.
- Capability negotiation: IPv4 + IPv6 unicast; no multiprotocol extensions beyond these.
- Hold time: 30s default.

**Operation:**

1. On daemon startup, if the cell has BGP configuration (`bgp.peer_address`, `bgp.peer_asn`, `bgp.local_asn` in local config or CRDT), establish the BGP session.
2. On becoming VIP owner (per Section 14.2), advertise the VIP as a /32 (or /128 for IPv6) route via `UPDATE` messages.
3. On ceasing to be owner, send a withdrawal `UPDATE`.
4. The next-hop attribute is the cell's own interface address on the BGP session peer subnet.

BGP convergence is bounded by the upstream router's BGP timers and routing table propagation; typically 1–5 seconds on a single-hop eBGP session.

## 14.5 Mode Selection

Each VIP in `vip.<vip>` declares its mode (`L2`, `L3`, or `BOTH`). The owner cell:

- For `L2`: performs gratuitous ARP (Section 14.3) only.
- For `L3`: performs BGP advertisement (Section 14.4) only.
- For `BOTH`: performs both. ARP handles same-segment hosts; BGP handles routed traffic.

## 14.6 Convergence Sequence

Failure → restoration timeline:

| t | Event |
|:---|:---|
| 0 | VIP owner cell crashes |
| 0 → $T_{\text{SWIM}}$ | Failure detection (Section 9): probe → indirect probe → suspect → death declaration |
| $T_{\text{SWIM}}$ | `health.<dead>.status = DEAD` written and gossiped |
| $T_{\text{SWIM}} + T_{\text{gossip}}$ | All cells observe the death; new owner computed locally |
| $T_{\text{SWIM}} + T_{\text{gossip}} + \epsilon$ | New owner writes `gateway.<vip>` and begins ARP/BGP takeover |
| ... + $T_{\text{ARP}}$ | L2 hosts updated (typically < 1s) |
| ... + $T_{\text{BGP}}$ | Upstream router converges (typically 1–5s) |

Total: typically 6–10s for end-to-end gateway recovery. This is CONV-3.

## 14.7 Pre-emption Protection

To avoid VIP flapping under marginal network conditions, a new owner waits `GW_TAKEOVER_DEBOUNCE` (2s) after writing `gateway.<vip>` before emitting ARP/BGP. If during the debounce the CRDT key changes again (e.g., the previous owner self-corrected), the new owner aborts the takeover.

## 14.8 Anti-Spoofing Discipline

The ARP/BGP mechanisms here are *cooperative* among Colloid cells — they are not adversarial spoofing of unrelated hosts. The `colloid_arp_gw` eBPF program responds to ARP requests **only** for VIPs whose ownership the local CRDT confirms. Cells never respond for IPs they do not own, and never on interfaces not configured as gateway interfaces.

In hostile network environments where ARP-based VIP migration is forbidden by policy, operators should configure L3-only mode.

---

# 15. Configuration & CLI

*Implements: ARCH-2, BOOT-1, BOOT-3, CRDT-ACTOR.*

## 15.1 Pipeline

```
.───────────────.     .───────────────.     .──────────────.
| Config file   |─────| CLI process   |─UDS─| Local daemon |─UDP─> mesh
| (human text)  |     | (parse, ser.) |     | (CRDT write) |
'───────────────'     '───────────────'     '──────────────'
```

The CLI validates input, serializes to binary `WorkloadSpec`, and issues `SET` over UDS. The daemon performs the CRDT write using its own Cell ID as actor (CRDT-ACTOR).

## 15.2 Config Format (Illustrative)

```
spread nginx {
    image docker.io/nginx:latest
    replicas 3
    port 80:8080
    port 443:8443
    vip 10.0.0.100:80 mode=both
    cpu 500m
    mem 256mb
}

stateful redis {
    image docker.io/redis:7
    replicas 1
    replication_factor 3
    port 6379:6379
    volume data /data
    cpu 1000m
    mem 1024mb
}

wasm transformer {
    module https://wasm.example.com/transform.wasm
    replicas 5
    capabilities kv_read,metrics
    deterministic true
}
```

Each block becomes a CRDT key: `spread.nginx`, `stateful.redis`, `wasm.transformer`.

## 15.3 Conflict Resolution Workflow

```
$ colloid status
CONFLICT on spread.nginx:
  Value (replicas=5, image=nginx:1.25)   by Cell 0x1A2B at {0x1A2B:3, 0x3C4D:1}
  Value (replicas=2, image=nginx:1.24)   by Cell 0x5E6F at {0x5E6F:1, 0x3C4D:1}

$ colloid resolve spread.nginx --from-file nginx.colloid
OK
```

## 15.4 Volume Inspection

```
$ colloid volumes
VOLUME              OWNER       GEN   SIZE     REPLICAS
redis-0             cell-0x1A   42    1.2GB    [0x3C, 0x5E]
postgres-0          cell-0x3C   118   8.7GB    [0x1A, 0x5E, 0x7F]
```

## 15.5 Installation

```
curl -sfL https://colloid.net/install.sh | sh
```

Single statically linked binary. eBPF bytecode embedded.

---

# 16. Stream Protocol

*Implements: STREAM-1..6.*

## 16.1 Lifecycle

```
STREAM_OPEN → [STREAM_DATA / STREAM_ACK]* → STREAM_CLOSE
```

Stream IDs are 32-bit, source-generated. `(source_cell_id, stream_id)` is globally unique.

## 16.2 Target Resolution

Local: read CRDT, compute placement, identify target cell. Zero network traffic.

## 16.3 Path Selection

For target cell $T$:

1. If $T$ is in local routing table with `reach_class = PUBLIC` → direct send.
2. If $T$ is `PUNCHED` and pinhole is fresh → direct send.
3. If $T$ is `PUNCHED` but pinhole stale, or $T$ is `RELAYED`, attempt hole-punch (Section 6.3). If success, direct send.
4. If hole-punch fails or both ends symmetric → relay (Section 16.4).

## 16.4 Relay

When direct send is impossible, the source uses DHT-routed forwarding: `STREAM_OPEN` is sent to the K-closest peer to $T$ that the source can reach. That peer either forwards to $T$ directly (if $T$ is reachable from it) or forwards to its own K-closest peer to $T$. At each hop, an entry is added to the relay table:

```c
struct StreamRelay {
    uint32_t            stream_id;
    uint64_t            source_id;
    struct sockaddr_in6 inbound_peer;
    struct sockaddr_in6 outbound_peer;
    uint64_t            created_ns;
    uint64_t            last_activity_ns;
};
```

`MAX_STREAM_RELAYS = 256` per node, pre-allocated.

## 16.5 Flow Control

Sliding window of `STREAM_WINDOW = 8` unacknowledged chunks. Receiver sends `STREAM_ACK(ack_seq)` for highest contiguous. Timeout `STREAM_TIMEOUT = 2s`, retry up to `STREAM_RETRY_MAX = 5`.

## 16.6 Relay Cleanup

Relay entries idle for `RELAY_IDLE_TIMEOUT = 30s` are GC'd.

---

# 17. Milestones & Implementation Plan

## 17.1 Milestone 1: Mesh Foundation

| Task | Deliverable |
|:---|:---|
| 1. io_uring reactor | Single-threaded loop, registered buffers, multishot recvmsg, timeout submission |
| 2. Kademlia overlay | XOR distance, K-buckets with reach-class awareness, iterative lookup |
| 3. Wire protocol | All M1 message types, validation state machine |
| 4. CRDT engine | MV-Register, version vectors, state and delta merge, conflict detection |
| 5. Gossip & anti-entropy | Epidemic forwarding, dedup, Merkle anti-entropy |
| 6. SWIM failure detection | Direct/indirect probing, suspicion, death CRDT writes |
| 7. STUN + hole punching | Address discovery, three-party punch coordination, keepalives |
| 8. Rendezvous scheduling | Placement, healthy set derivation, reconciliation |
| 9. OCI runtime backend | clone(), pivot_root, cgroups v2, netlink, OCI registry client |
| 10. CLI | UDS, config parser, conflict resolution workflow |

**External dependencies: none** (Wasm engine and BGP speaker embedded as later milestones; OCI handled natively in M1).

## 17.2 Milestone 2: Kernel Data Plane

| Task | Deliverable |
|:---|:---|
| 1. eBPF program set | XDP VIP DNAT, TC egress SNAT, sk_lookup, peer counters |
| 2. eBPF map management | User-space updates, atomic swap for consistent hash |
| 3. Service VIP integration | CRDT `vip.*` keys drive map state; eBPF intercepts traffic |
| 4. Gratuitous ARP for VIPs | `colloid_arp_gw` program + user-space ARP emit |
| 5. eBPF-assisted liveness | `colloid_peer_counter` integration into SWIM (Section 9.7) |
| 6. Observability | Per-workload stats via `colloid_observe_tc` |
| 7. User-space fallback | If eBPF load fails, equivalent user-space DNAT path |

## 17.3 Milestone 3: Stateful & Multi-Runtime

| Task | Deliverable |
|:---|:---|
| 1. Volume engine | Local volume storage, snapshots (reflink + fallback), generation tracking |
| 2. Volume replication | `VOL_REPL_*` messages, delta computation, atomic apply |
| 3. Stateful placement | Anchored Rendezvous, owner failover, conflict on divergent meta |
| 4. Embedded Wasm runtime | Wasm 1.0 core + WASI Preview 1 + Colloid host functions |
| 5. Wasm capability gating | Capability bitfield enforcement, deterministic mode |
| 6. Process runtime backend | Cgroup-only execution for host-native workloads |

## 17.4 Milestone 4: L3 Gateway

| Task | Deliverable |
|:---|:---|
| 1. Embedded BGP speaker | BGP-4 advertise-only, TCP/179 session, IPv4+IPv6 unicast |
| 2. VIP announcement | UPDATE generation on ownership change, withdrawal on departure |
| 3. Mode selection | L2/L3/BOTH per VIP, debounce, conflict handling |
| 4. Convergence testing | Failover timing instrumentation, CONV-3 validation |

---

# Appendix A: Protocol Constants

| Constant | Default | Section |
|:---|:---|:---|
| `PROTOCOL_VERSION` | 1 | 3.1 |
| `DEFAULT_PORT` | 12421 | 5.1 |
| `MAX_DATAGRAM` | 1200 | 5.1 |
| `HEADER_SIZE` | 16 | 3.1 |
| `PAYLOAD_MAX` | 1184 | 3.1 |
| `K_BUCKET_SIZE` | 20 | 4.1 |
| `K_BUCKET_MIN` | 4 | 4.1 |
| `ALPHA` | 3 | 4.5 |
| `GOSSIP_FANOUT` | 3 | 8.1 |
| `AE_INTERVAL` | 30s | 8.2 |
| `AE_RATE_LIMIT` | 100 msg/s | 8.2 |
| `RETRY_BASE` | 200ms | 8.3 |
| `RETRY_MAX` | 3 | 8.3 |
| `DEDUP_RING_SIZE` | 4096 | 8.4 |
| `PROBE_INTERVAL` | 1s | 9.1 |
| `PROBE_TIMEOUT` | 500ms | 9.1 |
| `INDIRECT_PROBE_COUNT` | 3 | 9.2 |
| `SUSPECT_TIMEOUT` | 5s | 9.2 |
| `HYSTERESIS_THRESHOLD` | 0.15 | 9.6 |
| `HEARTBEAT_INTERVAL` | 5s | 5.4 |
| `REFRESH_INTERVAL` | 15min | 4.4 |
| `FAILURE_THRESHOLD` | 5 consecutive | 4.4 |
| `RTT_EWMA_ALPHA` | 0.25 | 4.6 |
| `PUNCH_KEEPALIVE_INTERVAL` | 20s | 6.4 |
| `PUNCH_TTL` | 60s | 6.3 |
| `REACH_REPROBE_INTERVAL` | 60s | 6.2 |
| `STREAM_WINDOW` | 8 | 16.5 |
| `STREAM_TIMEOUT` | 2s | 16.5 |
| `STREAM_RETRY_MAX` | 5 | 16.5 |
| `MAX_STREAM_RELAYS` | 256 | 16.4 |
| `RELAY_IDLE_TIMEOUT` | 30s | 16.6 |
| `MAX_KEYS` | 16384 | 7.1 |
| `MAX_KEY_NAME` | 128 | 7.1 |
| `MAX_VALUE_SIZE` | 512 | 7.1 |
| `MAX_ENTRIES` | 4 | 7.1 |
| `MAX_CTX_ENTRIES` | 32 | 7.1 |
| `MAX_VIPS` | 1024 | 12.2 |
| `MAX_BACKENDS_PER_VIP` | 256 | 12.2 |
| `MAX_PEERS` | 4096 | 12.2 |
| `STATS_REAP_INTERVAL` | 1s | 12.5 |
| `ANCHOR_BIAS` | 0x4000_0000_0000_0000 | 10.5 |
| `MAX_FAILOVER_LAG_GENERATIONS` | 2 | 10.6 |
| `GW_TAKEOVER_DEBOUNCE` | 2s | 14.7 |
| `SQ_DEPTH` | 4096 | 5.3 |
| `BUFFER_POOL_SIZE` | 1024 | 5.3 |
| `MIN_KERNEL` | 5.15 | 12.6 |

# Appendix B: Invariant Traceability

| Invariant | Implementing Sections |
|:---|:---|
| SAFE-1 | 7.5, 7.6, 13.6 |
| SAFE-2 | 7.5 |
| SAFE-3 | 7.4, 15.3 |
| SAFE-4 | 7.3 |
| SAFE-5 | 10.3, 10.5, 11.3 |
| SAFE-6 | 13.5 |
| AVAIL-1 | 7.3 |
| AVAIL-2 | 8.2 |
| AVAIL-3 | 4, 9, 11 |
| AVAIL-4 | 5.3, 5.4 |
| AVAIL-5 | 6 |
| AVAIL-6 | 14 |
| CONV-1 | 4 |
| CONV-2 | 8.1, 8.2 |
| CONV-3 | 14.6 |
| ARCH-1 | 7, 16 |
| ARCH-2 | 15.1 |
| ARCH-3 | 8.1 |
| ARCH-4 | 7.8, 15 |
| ARCH-5 | 12 |
| ARCH-6 | 5.3 |
| BOOT-1 | 6.5 |
| BOOT-2 | 6.5, 6.6 |
| BOOT-3 | 2.3, 15 |
| BOOT-4 | 6.2, 6.5 |
| EXEC-1 | 11.3, 13.6 |
| EXEC-2 | 11.3 |
| EXEC-3 | 11.4 |
| EXEC-4 | 13.2, 13.3, 13.4, 13.5 |
| EXEC-5 | 10.5, 10.6 |
| ROUTE-1 | 4.1 |
| ROUTE-2 | 4.5 |
| ROUTE-3 | 4.1 |
| ROUTE-4 | 4.3, 4.6 |
| ROUTE-5 | 4.2, 6.1 |
| STREAM-1..6 | 16, 6.3 |
| RES-1 | 5.3, 7.8 |
| RES-2 | 3.1, 5.1 |
| RES-3 | 7.8, 8.2 |
| RES-4 | 2.1, 2.5 |
| RES-5 | 12.2 |
| CRDT-ACTOR | 7.4, 5.2 |