Tag: Concurrency

Categories
Drafts in Press News

Posets with Interfaces

After quite some time, we have released a long version of our work on “Posets with Interfaces for Concurrent Kleene Algebra“, co-authored with Uli Fahrenberg, Georg Struth, and Krzysztof Ziemiański, which is now being reviewed for a journal.

Abstract:

We introduce posets with interfaces (iposets) and generalise the serial composition of posets to a new gluing composition of iposets. In partial order semantics of concurrency, this amounts to designate events that continue their execution across components. Alternatively, in terms of decomposing concurrent systems, it allows cutting through some events, whereas serial composition may cut through edges only.

We show that iposets under gluing composition form a category, extending the monoid of posets under serial composition, and a 2-category when enriched with a subsumption order and a suitable parallel composition as a lax tensor. This generalises the interchange monoids used in concurrent Kleene algebra.

We also consider gp-iposets, which are generated from singletons by finitary gluing and parallel compositions. We show that the class includes the series-parallel posets as well as the interval orders, which are also well studied in concurrency theory. Finally, we show that not all posets are gp-iposets, exposing several posets that cannot occur as induced substructures of gp-iposets.

Categories
Accepted Papers News

Sculptures in Concurrency

Logical Methods in Computer Science, the most prestigious journal managed solely by the theoretical computer science community, has published our work on Sculptures in Concurrency, co-authored with Uli Fahrenberg, Christopher A. Trotter, and Krzysztof Ziemiański.

Abstract:

We give a formalization of Pratt’s intuitive sculpting process for higher-dimensional automata (HDA). Intuitively, an HDA is a sculpture if it can be embedded in (i.e., sculpted from) a single higher dimensional cell (hypercube). A first important result of this paper is that not all HDA can be sculpted, exemplified through several natural acyclic HDA, one being the famous “broken box” example of van Glabbeek. Moreover, we show that even the natural operation of unfolding is completely unrelated to sculpting, e.g., there are sculptures whose unfoldings cannot be sculpted. We investigate the expressiveness of sculptures, as a proper subclass of HDA, by showing them to be equivalent to regular ST-structures (an event-based counterpart of HDA) and to (regular) Chu spaces over 3 (in their concurrent interpretation given by Pratt). We believe that our results shed new light on the intuitions behind sculpting as a method of modeling concurrent behavior, showing the precise reaches of its expressiveness. Besides expressiveness, we also develop an algorithm to decide whether an HDA can be sculpted. More importantly, we show that sculptures are equivalent to Euclidean cubical complexes (being the geometrical counterpart of our combinatorial definition), which include the popular PV models used for deadlock detection. This exposes a close connection between geometric and combinatorial models for concurrency which may be of use for both areas.

Categories
Honors and Awards

5th most downloaded paper in JLAMP


My work with Håkon Normann and Thomas Hildebrandt was published in Elsevier’s Journal of Logical and Algebraic Methods in Programming and became the 5th most downloaded paper of 2016.

The paper is entitled “Declarative event based models of concurrency and refinement in psi-calculi”.