Formal Construction of a Non-blocking Concurrent Queue Algorithm

 Jean-Raymond Abrial, Dominique Cansell

https://lib.jucs.org/article/28407/ 

Journal of Universal Computer Science, vol. 11, no. 5 (2005), 744-770
submitted: 30/11/04, accepted: 31/1/05, appeared: 28/5/05

Abstract
This paper contains a completely formal (and mechanically proved) development of some algorithms dealing with a linked list supposed to be shared by various processes. These algorithms are executed in a highly concurrent fashion by an unknown number of such independent processes. These algorithms have been first presented in [MS96] by M.M. Michael and M.L. Scott. Two other developments of the same algorithms have been proposed recently in [YS03] (using the 3VMC Model Checker developed by E. Yahav) and in [DGLM04] (using I/O Automata and PVS).
Keywords
atomicity, concurrency, refinement, formal proof, prover

 

Comments

Post a Comment

Popular posts from this blog

Ce que je dois à Jean-Raymond Abrial

Image
 Quand ai-je découvert Jean-Raymond Abrial ?  Peut-être bien que c'est quand j'ai fait acheter les actes de la conférence de Cargèse et que j'ai lu son article Data Semantics . Ou est-ce lors de la lecture des publications de la DER-IMA d'EDF (située à Clamart) ? Ce qui est sûr c'est que j'ai découvert Z dans le Meyer Baudoin, Méthodes de Programmation chez Eyrolles, puis dans le Delobel Adiba, Bases de données chez Dunod. Quand j'ai débuté en "informatique de gestion" (en I.U.T "Informatique") je trouvais que ce que je lisais était bien peu "scientifique". "Information" "donnée" "rubrique" etc.  Pour "donnée" j'ai appris les théorèmes de Jean-Louis Rigal qui était prof à l'Université Dauphine. Facile : Th1, "Une donnée n'est pas donnée" car c'est le résultat d'une abstraction, Th 2. "Une donnée n'est pas donnée" car une fois donnée, ce n'est...
Read more

Jean-Raymond Abrial (1938, 2025)

Image
  Jean-Raymond Abrial (1938, 2025) Jean-Raymond Abrial est décédé les 26 mai 2025 la vieille de la conférence qui a eu lieu dans le cadre des Journées Scientifiques de l'université de Nantes et qui traitait de ses travaux et de leur mise en oeuvre dans différentes domaines.J.-R Abrial est né en 1938 à Versailles. Après des études au Prytanée militaire de la Flèche, il fera l'Ecole Polytechnique. En 1960 il sera ingénieur du génie maritime. Il sera boursier du gouvernement français à Stanford University puis au Centre de Programmation de la Marine où il travaillera sur une version du langage LTR (Langage Temps Réel). C'est là que Gérard Le Lann, qui a fait partie de l'équipe ayant conçu Internet, l'a connu. J.-R Abrial est pour lui "l'un des plus grands informaticiens français ! Peu enclin à épouser les « modes » qui agitent plus ou moins régulièrement les communautés scientifiques. Liberté de penser, de créer, et liberté d'essaimer !".A Grenoble, d...
Read more

On B, Jean-Raymond Abrial

 Cet article date du temps où Jean-Raymond Abrial habitait rue des plantes à Paris. Digilog était deveni Steria, mais pas encore Clearsy. Donc d'avant 2001. On B Jean-Raymond Abrial Consultant, 26, rue des Plantes, 75014, Paris. abrial@steria.fr In  the B-Book [Abr96], an introduction entitled “What is B ?” presents it in a few pages. There is no point in reproducing this introduction here. There is, however, clearly a need to have in this book a sort of informal presentation of B complementing that of the B-Book for those readers who are not familiar with this approach. This is the purpose of this short text, where the emphasis will be put on the question of the development process with B. At the end of the text, I will also cover some more general problems concerning B (tool, education, research, future). B is o “Debugger”. The aim of B is very practical. Its ambition is to provide to industr...
Read more