Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Trapping mutual exclusion in the box calculus
Esparza J., Bruns G. Theoretical Computer Science153 (1-2):95-128,1996.Type:Article
Date Reviewed: Jul 1 1997

Box calculus is a new process algebra that seems to have a relatively simple Petri net semantics. The purpose of this new algebra is to be able to translate real-life parallel programs into a set of algebraic rules and then to prove interesting properties of the programs in a mathematically rigorous fashion. The authors apply the technique to two traditional well-known mutual exclusion algorithms--Dekkar’s and Dijkstra’s--and rigorously prove that these algorithms are really deadlock-free, starvation-free, and fair. The authors also claim that this new process algebra provides more concise ways of writing parallel programs and makes it easier to make claims about properties without using operational arguments.

The paper is theoretical and should be mildly interesting to Petri net researchers. It is highly readable, lucid, and self-contained; the concepts of S-invariants and traps may be useful in analyzing other parallel programs. You do not need to know box calculus to understand the paper, but general familiarity with Petri nets and process algebras in general will enhance understanding.

Reviewer:  Pradip K. Srimani Review #: CR119930 (9707-0524)
Bookmark and Share
 
Mutual Exclusion (D.4.1 ... )
 
 
Algebraic Algorithms (I.1.2 ... )
 
 
Deadlocks (D.4.1 ... )
 
 
Petri Nets (D.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Mutual Exclusion": Date
Another solution of the mutual exclusion problem
Kowaltowski T., Palma A. Information Processing Letters 19(3): 145-146, 1984. Type: Article
May 1 1985
The mutual exclusion problem
Lamport L. Journal of the ACM 33(2): 313-326, 1986. Type: Article
Apr 1 1987
The mutual exclusion problem
Lamport L. Journal of the ACM 33(2): 327-348, 1986. Type: Article
Apr 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy