Home

Papers

Pomsets

• The pomset model of parallel processes: Unifying the temporal and the spatial - V. Pratt (1984).

  • Introduction to the pomsets , basic definitions, examples.

• Pomsets with Boxes: Protection, Separation, and Locality in Concurrent Kleene Algebra - Paul Brunet, David Pym (FSCD 2020).

  • Interesting concept of boxes over pomsets which are used to enforce certain forms of non-interference and prohibit some interleavings. Can be useful to model various atomicity primitives.
  • Pomset logic as a specification language for properties of programs and its relationship to CKA.

• Trade-offs in true concurrency: Pomsets and Mazurkiewicz traces - Bard Bloom and Marta Kwiatkowska (ICMFPS 1991)

  • Relationship between pomset languages and Mazurkiewicz traces.

Event Structures

• Event Structures - Markus Hoffmann.

  • A very gentle introduction to prime and stable event structures.

• Event Structures - Glynn Winskel (1986).

  • Definition of event structures (through consistency predicate and enabling relation).
  • Definition of stable event structures, motivation, examples.
  • Family of configurations, prime algebraic domains, connection to Scott domains.
  • Denotational semantics of CCS.

• Event Structure Semantics For CCS and Related Languages - Glynn Winskel (1983).

  • General definition of event structures as a family of configurations.
  • cpo (chain-complete partial order) on event structures.
  • Denotational semantics of CCS.

• Bundle Event Structures and CCSP - Rob van Glabbeek and Frits Vaandrager (CONCUR 2003).

  • Definition of bundle event structures.
  • Denotational semantics of CCSP (CCS + CSP).

• Flow models of distributed computations: event structures and nets - Gérard Boudol, Ilaria Castellani (1991).

  • Flow event structures, connection to prime, bundle, and stable event structures, connection to Petri Nets.

• Flow models of distributed computations: three equivalent semantics for CCS - Gérard Boudol, Ilaria Castellani (1994).

  • Denotational semantics of CCS in terms of flow event structures.

• Global types and event structure semantics for asynchronous multiparty sessions - Ilaria Castellani, Mariangiola Dezani-Ciancaglini, Paola Giannini (2021).

  • Application of flow event structures to session types.

• Reversibility and Models for Concurrency - Iain Phillips, Irek Ulidowski (ENTCS 2007).

  • Prime event structures as a non-interleaving model for reversible computations.
  • Definition of prime event structures with general conflict.

• A Complete Theory of Deterministic Event Structures - Arend Rensink (CONCUR 1995).

  • Subclass of deterministic prime event structures.
  • Sound and complete equational theory for deterministic event structures (the signature of the theory is similar to CKA).
  • Definition of prime event structure with consistency predicate (dual to general conflict).

• Minimisation of Event Structures - Paolo Baldan, Alessandra Raffaetà (2019).

  • Theory of minimization of event structures, that is construction of a minimal event structure equivalent to the original (by hereditary history preserving bisimilarity).
  • Formal definitions of various classes of event structures: poset, prime, asymmetric, bundle, flow.
  • Formal definition of (hereditary) history preserving bisimulation.

• Language Inclusion for Finite Prime Event Structures - Andreas Fellner, Thorsten Tarrach, Georg Weissenbacher (VMCAI 2020).

  • Study of a word membership and language inclusion problems for finite prime event structures.
  • Application to mutation-based test case generation.

• Conflict vs causality in event structures - Daniele Gorla, Ivano Salvo, Adolfo Piperno (JLAMP 2021).

  • Study of various types of equivalences between event structures.
  • Definition of elementary event structures and coherence spaces.
  • Definition of various types of bisimulations: interleaving bisimulation, step bisimulation, pomset bisimulation, history preserving bisimulation.

• Event Structure Semantics of Parallel Extrusionin the pi-calculus - Silvia Crafa, Daniele Varacca, and Nobuko Yoshida (FSTTCS 2012).

  • Denotational semantics of pi-calculus in terms of prime event structures with bound names.
  • Interesting insights on the modeling name (and data?) passing in event structures, might be relevant for modeling read-from relation in weak memory models.

• Prime algebraicity - G. Winskel

  • Theory of prime algebraic domains, its relationship to prime event structures with consistency predicate.

• Domains and Event Structures for Fusions - Paolo Baldan, Andrea Corradini, Fabio Gadducci (LICS 2017).

  • Definition of connected event structures and weak prime domains which generalize stable event structures and allow to directly encode disjunctive causality. Example of application to the semantics of pi-calculus.

• Denotational Causal and Operational Determinism in Event Structures - Arend Rensink (CTAP 1996).

  • Definitions of operationally deterministic event structure, causally deterministic event structure, autoconcurrency.

• Determinism -> (event structure isomorphism = step sequence equivalence) - Frits Vaandrager (TCS 1991).

  • Proofs that for operationally deterministic event structures various equivalence relations (language, pomset, bisimulation, isomorphism) coincide.

Concurrent Kleene Algebra

• Brzozowski Goes Concurrent: A Kleene Theorem for Pomset Languages - T. Kappé, P. Brunet, B. Luttik, A. Silva, F. Zanasi (CONCUR 2017).

  • Operational and denotational model (based on series-parallel pomset languages) for the bi-Kleene Algebra.
  • Kleene Theorem for weak bi-Kleene Algebra (i.e. CKA without parallel star and exchange law).

• On Decidability of Concurrent Kleene Algebra - Paul Brunet, Damien Pous, Georg Struth (CONCUR 2017)

  • Yet another operational model for bi-Kleene Algebras based on Petri nets.
  • Decidability results of equivalence and refinement checking for bi-Kleene Algebras.

Relaxed Concurrency

• Making Linearizability Compositional for Partially Ordered Executions - Simon Doherty, Brijesh Dongol, Heike Wehrheim, John Derrick (iFM 2018).

  • Defines a notion of causal linearizability, an adoption of linearizability to relaxed memory models (i.e. when there is no total order on the events of the system). Proves that causal linearizability is composable.

• Causal Consistency: Beyond Memory - Matthieu Perrin, Achour Mostefaoui, Claude Jard (PPoPP 2016)

  • Defines sequential consistency, causal consistency, causal convergence weak causal consistency, and pipelined conistency with respect to (sequential) transition system.

• Eventual Consistency for CRDTs - Radha Jagadeesan and James Riely (ESOP 2018)

  • Defines validity of conflict-free replicated datatypes with respect to (sequential) transition system.

• Weak Memory Bibliography list

Misc

• Relationships between models of concurrency - M. Nielsen, V. Sassone, G. Winskel. (another version)

  • Very useful paper that establishes a connection between several models of concurrency: labelled transition systems, asynchronous labelled transition systems, synchronisation trees, trace languages, Mazurkiewicz trace languages (a.k.a trace languages with independence relation), prime event structures, Petri nets.

• Deterministic Behavioural Models for Concurrency - V. Sassone, M. Nielsen, G. Winskel

  • Paper establishes a connection between deterministic event structures, deterministic pomset languages, and generalized Mazurkiewicz trace languages (where independence relation is parametrized by a context).

Tools

• The SAV-Science LaTeX Package