In Search of a Compositional Theory of Self-Stabilization
Summary
This blog post surveys a compositional theory of self-stabilization for distributed systems, exploring how rely-guarantee contracts, parametric contracts, and small-gain reasoning can be used to analyze stability and metastability in multi-queue systems. It critiques memoryless, single-scalar models and demonstrates the importance of considering backlog memory when predicting system behavior. The piece includes detailed derivations and a critique of practical composition for real systems.