Storage and relay orders

At its base, Swarm is a log replication protocol. It relays immutable ops while preserving the causal order. Formally, the protocol's guarantees are:

• every op is delivered to every peer replica,
• it is delivered exactly once and
• in accordance with the happened-before order.

The general op relay rule is that all new ops are stored first, relayed second, in the same order as they were received. In case two replicas were temporarily disconnected, on reconnection the ops must be replayed in the same order (replay order is the relay order). Only concurrent ops can go in different orders at different replicas.

Swarm guarantees are not that much different from TCP guarantees: exactly-once in-order delivery, in a certain scope. Of course, Swarm's scope is higher in the stack than TCP's. From the practical standpoint, 80% of the protocol's effort goes into gluing together segments of continuous TCP-like transmissions and continuous log-structured append-only storage writes. The objective is to give it all an appearance of a single continuous session. That way, Swarm implements the abstraction of a distributed partially-ordered op log.

Swarm is partially-ordered, so there is no single total op order. For a given database, op orders vary at different replicas. Still, there are some useful and important linear orders too.

Replica order is the order of ops generated by a single origin replica. A replica is considered a sequential process, its op ids are monotonous (later ops have higher ids). This order is global (same-origin ops go in exactly the same order at every replica).

Home peer order is the order of client ops as they arrive on their home peer. Essentially, a home peer is used to create a de-facto linear order for all the ops its clients generate. The peer's own ops belong to that order too. This order is consistent at every replica, except client replicas themselves (well, clients don't get the full op log anyway).

Arrival order is the de-facto order of ops as they arrive on a certain replica. When peers sync, they talk in terms of each other's arrival orders. This is the most variable order of all: it is replica-specific. Another term for this is delivery order. It was also addressed earlier as relay and replay order -- they are all the same. A single Swarm replica can be seen as an arrival-order op log.

A Swarm network is peers connected by an arbitrary graph of peering connections. Clients only connect to their respective home peers. Peer connections should form a connected graph, at least most of the time. That graph is not necessarily a tree. Hence, there is some redundancy in op relay. Normally, a peer gets every new op from every of its connected peers. For example, the next picture shows three peers connected in a ring (a-b-c-a) and an op propagation diagram for a new op created by a. Every peer receives the op twice, relays once.

a---b              a b c a      abc  peers
 \ /          |    _            _    op stored
  c           |     \_          \ /  op relayed
              |     / \_
         time V       / \

Even peer's own ops are echoed back by its connected peers; that serves as an acknowledgement. Hence, there is an incentive not to make the graph too dense. That redundancy does not affect the client side: as a client is only connected to its home peer, it gets every operation once.

Op delivery guarantees can be further hardened by crypto. Cryptographic entanglement ensures that no op was corrupted, omitted or injected in transit; it further allows all peers to cross-sign all the data and to ensure that every peer sees exactly the same data.