Lune

PLDI2022Top-tier venue

Adore: atomic distributed objects with certified reconfiguration

Wolf Honoré, Ji-Yong Shin, Jieung Kim, Zhong Shao

Abstract

Finding the right abstraction is critical for reasoning about complex systems such as distributed protocols like Paxos and Raft. Despite a recent abundance of impressive verification work in this area, we claim the ways that past efforts model distributed state are not ideal for protocol-level reasoning: they either hide important details, or leak too much complexity from the network. As evidence we observe that nearly all of them avoid the complex, but important issue of reconfiguration. Reconfiguration's primary challenge lies in how it interacts with a protocol's core safety invariants. To handle this increased complexity, we introduce the Adore model, whose novel abstract state hides network-level communications while capturing dependencies between committed and uncommitted states, as well as metadata like election quorums. It includes first-class support for a generic reconfiguration command that can be instantiated with a variety of implementations. Under this model, the subtle interactions between reconfiguration and the core protocol become clear, and with this insight we completed the first mechanized proof of safety of a reconfigurable consensus protocol.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

7 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • AdoB: Bridging Benign and Byzantine Consensus with Atomic Distributed Objects cites Much ADO about failures: a fault-aware model for compositional verification of strongly consistent distributed systems
  • SandTable: Scalable Distributed System Model Checking with Specification-Level State Exploration cites Grove: a Separation-Logic Library for Verifying Distributed Systems
  • SandTable: Scalable Distributed System Model Checking with Specification-Level State Exploration cites Compiling Distributed System Models with PGo
  • LiDO: Linearizable Byzantine Distributed Objects with Refinement-Based Liveness Proofs cites Grove: a Separation-Logic Library for Verifying Distributed Systems
  • LiDO: Linearizable Byzantine Distributed Objects with Refinement-Based Liveness Proofs cites AdoB: Bridging Benign and Byzantine Consensus with Atomic Distributed Objects
  • LiDO: Linearizable Byzantine Distributed Objects with Refinement-Based Liveness Proofs cites Much ADO about failures: a fault-aware model for compositional verification of strongly consistent distributed systems
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. Grove: a Separation-Logic Library for Verifying Distributed SystemsUpamanyu Sharma, Ralf Jung, Joseph Tassarotti, M. Frans Kaashoek et al.SOSP 2023 · 18 citations
  2. Compiling Distributed System Models with PGoA. Finn Hackett, Shayan Hosseini, Renato Costa, Matthew Do et al.ASPLOS 2023 · 13 citations
  3. LiDO: Linearizable Byzantine Distributed Objects with Refinement-Based Liveness ProofsLongfei Qiu, Yoonseung Kim, Ji-Yong Shin, Jieung Kim et al.PLDI 2024 · 12 citations
  4. SandTable: Scalable Distributed System Model Checking with Specification-Level State ExplorationRuize Tang, Xudong Sun, Yu Huang, Yuyang Wei et al.EuroSys 2024 · 8 citations
  5. AdoB: Bridging Benign and Byzantine Consensus with Atomic Distributed ObjectsWolf Honoré, Longfei Qiu, Yoonseung Kim, Ji-Yong Shin et al.OOPSLA 2024 · 5 citations

Builds on1

  1. Much ADO about failures: a fault-aware model for compositional verification of strongly consistent distributed systemsWolf Honoré, Jieung Kim, Ji-Yong Shin, Zhong ShaoOOPSLA 2021 · 12 citations

Related papers

  1. Bolt-On Strong Consistency: Specification, Implementation, and VerificationNicholas V. Lewchenko, Gowtham Kaki, Bor-Yuh Evan ChangOOPSLA 2025 · 2 citations
  2. PRDTs: Composable Design and Verification of Consensus Protocols using Replicated Data TypesJulian Haas, Ragnar Mogk, Annette Bieniusa, Mira MeziniOOPSLA 2026 · 1 citation
  3. Reasoning about distributed reconfigurable systemsEmma Ahrens, Marius Bozga, Radu Iosif, Joost-Pieter KatoenOOPSLA 2022
  4. I3DP: Neuro-Symbolic Inductive Invariant Inference for Distributed ProtocolsWeining Cao, Guangyuan Wu, Yuan Yao, Hengfeng Wei et al.SOSP 2026
  5. Simplifying Safety Proofs with Forward-Backward Reasoning and ProphecyEden Frenkel, Kenneth L. McMillan, Oded Padon, Sharon ShohamPLDI 2026
Dusk over the sea between two cliffs drawn in fine vertical lines