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

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.

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:

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)

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                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

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

3.2 Message Types

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:

4.2 Contact Record

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.

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:

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:

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:

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.

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:

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

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

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.

12.2 Map Set

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. 5-tuple hash → consistent hash bucket → backend selection.
6. DNAT rewrite (destination IP/port → backend pod IP/port).
7. bpf_redirect or kernel forwarding to backend.
8. 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:
3. WASI environment from WorkloadSpec.env.
4. Mounted volumes as WASI preopens.
5. Host capabilities per capability_mask.
6. 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:

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:
4. Sender Hardware Address: cell's MAC on the gateway interface.
5. Sender Protocol Address: VIP.
6. Target Protocol Address: VIP (broadcast announcement).
7. The gratuitous ARP is repeated 3 times at 100ms intervals (RFC 5227 style) to overcome packet loss.
8. The colloid_arp_gw eBPF program at the gateway interface intercepts ARP requests for owned VIPs and responds with the cell's MAC.
9. 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:

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:

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

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

17.2 Milestone 2: Kernel Data Plane

17.3 Milestone 3: Stateful & Multi-Runtime

17.4 Milestone 4: L3 Gateway

Appendix A: Protocol Constants

Appendix B: Invariant Traceability