Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Directed algebraic topology and concurrency
Fajstrup L., Goubault E., Haucourt E., Mimram S., Raussen M., Springer International Publishing, New York, NY, 2016. 167 pp. Type: Book (978-3-319153-97-1)
Date Reviewed: Jul 19 2016

Introducing the use of ideas from algebraic topology in the study of concurrency is the primary contribution of this book. The basic idea is as follows: suppose that one has a collection of processes that are to run concurrently and that each process makes use of a number of resources that must restrict access to the resource to no more than some fixed number of processes at any one time. For example, one might have two processes and a single resource that requires mutual exclusion. If each process requires access to the shared resource just once, the progress of these parallel processes can be visualized as taking place in a square region that has a forbidden region within it. This forbidden region can be visualized as a rectangle in the interior of the square. There are then two paths that the combined processes can take depending on whether the path passes below or above the forbidden region. In the language of algebraic topology, these two paths are not homotopic.

On the other hand, all of the alternate paths are homotopic to one of these two. Using homotopy to implement this attractive scenario fails to take into account the fact that processes run forward in time. Thus, as is the case when the forbidden region has the shape of a cross, which can happen when there are two resources requiring mutual exclusion, there are regions into which the combined processes can enter but from which they cannot leave. To take this into account, one needs to introduce a notion of directedness into the paths and into the homotopies between the paths. The authors therefore spend the first part of the book setting up the notion of directedness for paths and homotopies. The main definitions here are those of dihomotopy and d-space. It should be noted that a dihomotopy between two directed paths requires that the end points of the path remain fixed. Dihomotopy clearly implies homotopy.

Armed with an appropriate definition of directed homotopy, the authors, who are computer scientists and mathematicians, proceed to consider the question of determining how many nondirectedly homotopic paths there are in the space that describes the behavior of a set of concurrent processes. They give an algorithm that is able to determine in an efficient manner the set of dihomotopy classes for parallel processes for a simple language that uses neither loops nor conditionals. There is a brief discussion of the unrollings that would be required to deal with programs that contain loops. It would have been good if the discussion of these required modifications were more comprehensive, perhaps in an appendix. By making use of category theory, the authors are able to give a formal definition for the dihomotopy classes of paths in the space that represents the evolution of a set of concurrent processes.

The outline of the book is as follows. Chapter 1 introduces the book, and chapter 2 describes a toy language for discussing concurrency. This is extended in chapter 3 with the introduction of resources and the important notion of asynchronous graphs and precubical sets: think of three processes where the alternative choices of the flow of the processes can be thought of as describing the edges of a cube. Chapter 4 introduces directed topological spaces and the corresponding notion of homotopy between paths in the models of process evolution. Chapter 5 describes algorithms for representing regions, computing deadlocks, and factorizing processes. According to the book’s introduction, “chapter 6 introduces a notion of ’connected components’ in directed topology, which can be used to obtain a compact representation of the category of directed paths up to homotopy.” Chapter 7 “constructs combinatorial models for the space of directed paths with fixed endpoints up to homotopy, which lead to efficient computations.” Finally, chapter 8 concludes with comments on topics not covered in the book and suggestions for future development.

The book contains a large number of illustrative examples along with many diagrams that serve to illustrate the ideas and make the book quite easy to follow. Indeed the diagrams are an essential guide to the geometrical ideas on which the book is based. While knowledge of algebraic topology would be helpful for the reader, it is not necessary for understanding the major ideas of the book. Only the category theory material requires some familiarity with categorical notions. The book certainly suggests a possible fruitful approach to reasoning about concurrency. The book can be recommended to both mathematicians and computer scientists as presenting an introduction to an area where further collaboration could be fruitful.

Reviewer:  J. P. E. Hodgson Review #: CR144600 (1610-0726)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Concurrent Programming Structures (D.3.3 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Concurrent Programming Structures": Date
Wait-free synchronization
Herlihy M. ACM Transactions on Programming Languages and Systems 13(1): 124-149, 1991. Type: Article
Jan 1 1992
Parallel expression in the APL2 language
Willhoft R. IBM Systems Journal 30(4): 498-512, 1991. Type: Article
Dec 1 1993
Actors: a conceptual foundation for concurrent object-oriented programming
Agha G., Hewitt C., MIT Press, Cambridge, MA, 1987. Type: Book (9780262192644)
Jul 1 1989
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