To the Best of Knowledge and Belief: On Eventually Consistent Access Control

We are used to the conventional model of linearizable access control (LAC), implemented by a trusted central entity or by a set of distributed entities that coordinate to mimic a central entity.
The strength of LAC is rooted in the dependencies among entities, at the cost of reduced availability, scalability, and resilience under faults.
Systems that cannot afford dependencies among entities, like the ones based on conflict-free replicated data types (CRDTs), must break with the LAC convention, but gain fundamental advantages in availability, scalability, and resilience.
In this paper, we formalize eventually consistent access control (ECAC) that replaces up-front coordination with subsequent reconciliation, and study its theoretical guarantees in Byzantine environment at the practical example of Matrix, a CRDT-based group communication system.
Our core finding is that ECAC implies authorization to the best of knowledge and belief: an entity stores an action only if the action is authorized by immutable knowledge derived from its final set of preceding actions, and executes an action only if it is also authorized by the entity's mutable beliefs derived from the grow-only set of concurrent actions.