Paper: Partial Order Models of Concurrency and the Computation of Functions (at LICS 1987)

Authors: Haim Gaifman Vaughan R. Pratt

Abstract

We shall describe an abstract approach, based on structures of partially ordered events, for specifying and analyzing concurrent processes. Within this approach, one framework is the pomset model. Another is based on structures called "prossets" (preorder specification sets) which include, in addition to the < - relation, a relation for denoting simultaneity of events. Some of the results apply to both, with almost identical proofs, others necessitate the use of prossets. We show how within a framework of this kind general abstract definitions can be given to concepts such as: fairness, input event, a location of the process (which can store members of some given, arbitrary cpo), input-location, and the relation computed by the process in a given location. Process composition and formation of loops are defined using a fusion operation, by which several locations are fused into one. Kahn's network sematics turns out to be a rather particular case, derived from an abstract theorem which etablishes a connection between operations on processes and the least fixpoint operator on the functions defined by them.

BibTeX

  @InProceedings{GaifmanPratt-PartialOrderModelso,
    author = 	 {Haim Gaifman and Vaughan R. Pratt},
    title = 	 {Partial Order Models of Concurrency and the Computation of Functions},
    booktitle =  {Proceedings of the Second Annual IEEE Symposium on Logic in Computer Science (LICS 1987)},
    year =	 {1987},
    month =	 {June}, 
    pages =      {72--85 },
    location =   {Ithaca, NY, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }