Proving Distributed Algorithms by Combining Refinement and Local Computations

Abstract

Distributed algorithms are considered to be very complex to design and to prove; our paper contributes to the design of correct-by-construction distributed algorithms. The main idea relies upon the development of distributed algorithms following a top/down approach, which is clearly well known in earlier works of Dijkstra, and to use refinement for proving the correctness of the resulting algorithms. However, the link between the problem and the first model remains to be expressed and the refinement 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 models and refinement to prove the correctness of a large class of distributed algorithms. Local computations models define abstract computing processes for solving problems by distributed algorithms and can be integrated into a the Event-B modelling language to define proof-based patterns for the design of distributed algorithms. We illustrate our approach by examples like the leader election protocol or the distributed coloring algorithm. Our proposal is integrated into an environment called ViSiDiA.