Backend
Stephen: Verifying Sequencer-Aided Coordination Systems with Cross-View Prophecy
arXiv cs.DC0 views
arXiv:2611.23811v1 Announce Type: new Abstract: Many distributed systems achieve high performance by relying on dedicated sequencers to order requests, leaving replicas to commit them in that order. Despite more than a decade of such sequencer-aided coordination (SAC) systems, from Corfu and NOPaxos to LazyLog and SwitchBFT, their correctness has been argued only with pen-and-paper proofs or bounded model checking at the protocol level. In this paper, we formally verify implementations of SAC protocols. The sequencer seems to make this easy: it decides the order of all requests, so the proof can place each request's linearization point at the sequencer using a well-known technique, prophecy variables. Yet a linearization point placed at the sequencer is not durable, because the sequencer orders a request before any replica commits it. Crashes and other rare events may trigger a view change that discards the request, nullifying the earlier decision and the proof that rests on it. Our framework, Stephen, extends prophecy variables to handle view changes, and we make three contributions. (1) We develop cross-view prophecy peek, which lets the proof follow a request across view changes until it is either committed or permanently discarded. (2) Our verification uncovered bugs in existing SAC implementations, including one that can lose committed requests. We fix them and prove the fixes correct. (3) We apply Stephen to NOPaxos, Corfu and LazyLog. We build verified implementations with machine-checked proofs of linearizability. They perform within 17% of their open-source, unverified counterparts. The verified implementations and proofs will be open-sourced.
Source:https://arxiv.org/abs/2611.23811PreviousDexAttention: Distributed Sparse Attention through Rapid Online Planning and Persistent GPU ExecutionNextA Fast, Programmable GPU-to-CPU Invocation Layer for GPU-Initiated Communication
Related posts
Where Was the Author of The Ugly Duckling Born? What 11 LLMs Taught Me About Connecting Facts
0dev.to Machine Learning

Airfoil noise: one model saw the test condition at other frequencies, one did not
0dev.to Machine Learning
Comment BlackRock et les géants de la gestion d'actifs intègrent-ils la blockchain ?
0dev.to Tutorial
How to Download Pinterest GIFs Without Losing the Animation
0dev.to Tutorial
I built a tool that finds the hiring team behind any job link
0dev.to Career
NGO Near Me: Education Support and Community Development in India
0dev.to Career