Concurrency Control for Large-Scale MLS: A Hybrid Distributed Sequencer for RFC 9420

Abstract

Messaging Layer Security (MLS) in RFC 9420 scales cryptographically, but overlapping group-state updates are still committed against a single epoch, and stale attempts must be retried. This is tolerable in small groups but creates avoidable delay and extra fan-out traffic in large, bursty deployments. We propose a Decentralised MLS Sequencer (DMS), a deployment-compatible overlay that preserves MLS transcript semantics while decentralising commit admission. DMS partitions the ratchet tree into leaf clusters, elects short-lived sub-tree sequencers with leases, admits branch-compatible updates locally, and deterministically coalesces them with a timestamp-based optimistic-concurrency-control Meld operator. We prove that, under crash faults and eventual synchrony, DMS cannot produce partitioned committed views among honest members that accept valid certificates, derive message-complexity bounds and a breakeven condition, and evaluate the design in a custom discrete-event simulation up to 10,000 members. DMS removes stale retries in the simulated workload, reduces mean intent-to-synchronisation latency by 24.6% and 59.8% relative to ordinary RFC 9420 sequencing at 5,000 and 10,000 members, respectively, and stays within 0.7–4.5% of a strong centralised batching baseline in control traffic for groups of 1,000–10,000 members.