3541 articles – 5260 references  [version française]

inria-00099531, version 1

A Mechanically Proved and Incremental Development of IEEE 1394 Tree Identify Protocol

Jean-Raymond Abrial a, Dominique Cansell () b1, Dominique Méry () c1

Formal Aspects of Computing 14, 3 (2003) 215-227

Abstract: The \ieee tree identify protocol illustrates the adequacy of the \textit{event-driven approach} used together with the B Method . This approach provides a complete framework for developing mathematical models of distributed algorithms. A specific development is made of a series of more and more refined models. Each model is made of a number of static properties (the invariant), and of a dynamic parts (the guarded events). The internal consistency of each model as well as its correctness with regards to its previous abstraction are proved with the proof engine of Atelier B, which is the tool associated with B. In the case of \ieee, the initial model is very primitive: it provides the basic properties of the graph (symmetry, acyclicity, connectivity), and its dynamic parts essentially contains a single event which \textit{elects the leader} in one shot. Further refinements introduce more events, showing how each node of the graph non-deterministically participates to the leader election. At some stage in the development, message passing is introduced. This raises a specific potential contention problem, whose solution is given. The last stage of the refinement completely localize the events by making them taking decision based on local data only.

  • a –  CONSULTANT - MARSEILLE, FRANCE
  • b –  INRIA
  • c –  UNIVERSITE HENRI POINCARE
  • 1:  MODEL (Méthodes formelles et applications) (LORIA)
  • INRIA – CNRS : UMR7503 – Université Nancy II – Université Henri Poincaré - Nancy I – Institut National Polytechnique de Lorraine (INPL)
  • Domain : Computer Science/Other
  • Keywords : b method – event-driven approach – refinement – proof-based development – proof engine – abstract model – || méthode b – approche événementielle – raffinement – développement fondé par preuve – génie de la preuve – modèle abstrait
  • Internal note : A02-R-338 || abrial02a
  • Comment : Article dans revue scientifique avec comité de lecture.
 
  • inria-00099531, version 1
  • oai:hal.inria.fr:inria-00099531
  • From: 
  • Submitted on: Tuesday, 26 September 2006 09:38:21
  • Updated on: Monday, 18 December 2006 14:53:48