The FLINT Project








Proving the Correctness of Concurrent Robot Software

Last modified: Tue May 12 15:39:25 2020 GMT.


Peter Kazanzides
Yanni Kouskoulas
Anton Deguet
Zhong Shao


Component-based software has been proposed as a methodology for improving software reuse and has increasingly been adopted by robot software developers. At the same time, robot systems typically have real-time performance requirements and performance gains can often be obtained by multi-threading. It is challenging, however, to create correct multi-threaded software, especially when standard mutual exclusion primitives, such as mutexes and semaphores, are eschewed in favor of more efficient, lock-free mechanisms. It is even more difficult to find these errors, as they can remain dormant for years until triggered by just the “right” conditions. Our approach, therefore, is to apply Formal Methods to reason about the correctness of these mechanisms. As a first step, we adopted a recently-developed program logic called History for Local Rely/Guarantee (HLRG) and applied it to prove the correctness (after first finding and fixing an error) of one such mechanism in the open source cisst software package. This strategy is not specific to cisst and can be applied to other packages.


In Proceedings of the 2012 IEEE International Conference on Robotics and Automation (ICRA'12), Saint Paul, Minnesota, pages 4718-4723, May 2012.

  • Conference Paper [PDF]

  • Copyright © 1996-2022 The FLINT Group <flint at cs dot yale dot edu>
    Yale University Department of Computer Science
    Validate this page