Exact Consistency Under Partial Views: Graph Colorability, Capacity, and Equality in Multi-Location Encodings
This work addresses consistency issues in distributed systems and data management, providing foundational insights with broad applications, though it appears incremental in extending graph-theoretic concepts to encoding problems.
The paper tackles the problem of exact consistency in multi-location encodings by developing a structural theory of failure, showing that exact recovery is equivalent to graph colorability and deriving asymptotic capacity bounds using Lovász-ϑ. It applies this theory to systems like programming runtimes and databases, establishing conditions for verifiable structural integrity.
We construct a structural theory of failure for multi-location encodings. Admissible partial views induce a confusability graph on latent tuples; in the exact coordinate-view model, this graph class is exactly characterized by upward-closed families of coordinate-agreement sets, and exact recovery with a $T$-ary tag is equivalent to $T$-colorability. Repeated composition yields strong powers, so the normalized block-rate sequence converges to asymptotic Shannon capacity bounded above by Lovász-$\vartheta$. The upper theory is sharp whenever confusability is transitive; meet-witnessing and fiber coherence provide checkable sufficient conditions for that collapse. Under an affine restriction, the coordinate structure yields a representable matroid whose rank bounds confusability. The theory applies uniformly to programming-language runtimes, databases, and dependency managers: causal propagation together with provenance observability are necessary and sufficient for verifiable structural integrity.