Resilience and Home-Space for WSTS
summary
Paper formalizes six resilience variants (including home-space) and shows many resilience questions are undecidable for general WSTS but become decidable under concrete effectivity and compatibility hypotheses. Key decidable cases: Post-ideal-effective or completion of ideals WSTS with strong compatibility (covers ω2‑WSTS) for Safe =↑ Safe via reduction to finitely many coverability checks, and VASS variants (including lossy, integer, continuous) when Bad and Safe are semilinear Bad and Safe, using reduction to the home‑space problem. Bounded (k) resilience and state‑resilience receive separate decidability boundaries.
AI-written summary · about
chapters (8)
- 0:00Resilience in WSTS
- 1:28Defining resilience variants
- 4:37Well-structured transition systems
- 6:31Decidability for upward-closed sets
- 10:22State resilience and downward-closed sets
- 11:47VASS
- 13:53Summary of decidability
- 15:19Q&A
related talks
15mRethinking Safe Consistency in Distributed Object-Oriented Programming
26mKater: Automating Weak Memory Model Metatheory and Consistency Checking
24mArbitration-Free Consistency Is Available (and Vice Versa)
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction
28mReasoning about Distributed Reconfigurable Systems
13mCharacterizing Implementability of Global Protocols with Infinite States and Data
29mReachability in multi-agent transfer systems
14mBolt-On Strong Consistency: Specification, Implementation, and Verification