Proving Distributed Algorithms by Combining Refinement and Local Computations Abstract: Our approach is directly related to the design of correctbyconstruction programs. The main idea relies upon the development of distributed algorithms fol lowing a topdown approach, which is clearly well known in earlier works of Dijkstra, and to use the refinement for controlling the correctness of the resulting algorithm. It relies on a more fundamental question related to the notion of problem to solve. The methodology can be based on incremental proofbased developments. However, the link between the problem and the first model remains to be expressed and the refine ment is a real help to justify in a very progressive way the choices of design. We propose in this work a framework combining local computations and refinement to prove the correctness of a large class of distributed algorithms.

Dijkstra Monads for All This paper proposes a general semantic framework for verifying programs with arbitrary monadic sideeffects using Dijkstra monads, which we define as monadlike structures indexed by a specification monad. We prove that any monad morphism between a computational monad and a specification monad gives rise to a Dijkstra monad, which provides great flexibility for obtaining Dijkstra monads tailored to the verification task at hand. We moreover show that a large variety of specification monads can be obtained by applying monad transformers to various base specification monads, including predicate transformers and Hoarestyle pre and postconditions. For simplifying the task of defining correct monad transformers, we propose a language inspired by Moggiu0027s monadic metalanguage that is parameterized by a dependent type theory. We also develop a notion of Plotkin and Poweru0027s algebraic operations for Dijkstra monads, together with a corresponding notion of effect handlers. We implement our framework in both Coq and F*, and illustrate that it supports a wide variety of verification styles for effects such as partiality, exceptions, nondeterminism, state, and inputoutput.