Anti-entropy: locate disagreement before choosing a winner

A leaf digest must cover the information whose equality matters: typically a key, value, and relevant version or deletion metadata. Serialize that information unambiguously. Concatenating unframed strings makes pairs such as (ab,c) and (a,bc) indistinguishable before hashing. Length prefixes, explicit types, and a canonical encoding avoid that particular ambiguity. Agree on field order, number representation, Unicode handling, and schema version; semantically identical objects with different byte encodings otherwise appear different to a byte-oriented hash.

Internal nodes summarize ordered child digests over identical key ranges or tree partitions. Domain separation distinguishes a leaf encoding from an internal-node encoding, and fixed-length child digests remove another framing ambiguity. Both replicas must use the same hash function, encoding, partition boundaries, and tree version. A root mismatch caused by different schemas is not evidence that a customer record changed. Conversely, a matching cryptographic digest is a collision-resistance-based equality check, not a logical impossibility of unequal content.

If roots disagree, compare child digests. Equal children let the repair skip their covered data, while unequal children require further descent or direct record comparison. For a balanced binary tree with one changed leaf, only the ancestor path must be explored. Multiple scattered changes can force much wider traversal. Tree construction and maintenance also cost CPU, reads, and storage, so digest exchange is only one part of the repair budget. A hot range can keep changing during comparison and require snapshot or version handling.

A digest should summarize a consistent state boundary if the repair protocol assumes one. Recomputing half a tree while updates race through the other half can produce misleading comparisons unless the implementation accounts for that concurrency. Once differing records are identified, transfer enough data and metadata to run the actual merge policy. Copying a larger timestamp without understanding its meaning can lose a legitimate concurrent update. Anti-entropy transport can be correct while the chosen conflict semantics are still wrong for the product.

A successful repair round does not mean future replicas can never diverge. Schedule repeated coverage, measure repair lag and bytes, and preserve deletions long enough that old copies cannot resurrect values. Decide how a new replica establishes a baseline and how a returning replica proves its history is compatible. Authentication protects who may participate; hashes alone do not turn an untrusted peer into an authorized source. If malicious behavior is in scope, integrity and membership require additional protocol guarantees.

Use the function lab only to inspect the cost of a naive all-pairs comparison alternative. Reset, set coefficient a to 1 and position x to 0.5, and predict y=0.25 before Step. Change x to 1 at the retained time and predict y=1. The fourfold change illustrates quadratic comparison growth under normalized units. It does not build a Merkle tree, compute digests, or reconcile replicas. The lesson’s explicit tree trace supplies the actual anti-entropy reasoning.