Strong fairness and recursive communicating processes

Research output: Contribution to journalConference article

Abstract

Fairness - the guarantee that every process enabled sufficiently often will eventually make progress - provides a convenient and often useful abstraction from timing details that affect how parallel processes interact with one another. For processes that communicate via synchronous message passing, strong fairness is generally accepted as the most reasonable notion of fairness. This paper describes a strongly fair, trace-based semantics for a CCS-like language of communicating processes with full recursion. The semantics is a generalization of previous semantics for fair, imperative communicating processes. Unlike those earlier semantics, however, this semantics is not fully abstract: the combination of synchronous communication, fairness, and full recursion is extremely problematic. We outline the general difficulties encountered and discuss why the fair-trace approach is unlikely to yield full abstraction for this combination of features.

Original languageEnglish (US)
Pages (from-to)433-448
Number of pages16
JournalElectronic Notes in Theoretical Computer Science
Volume20
DOIs
StatePublished - Dec 1 1999
EventMFPS XV, Mathematical Foundations of Programming Semantics, Fifteenth Conference - New Orleans, LA, United States
Duration: Apr 28 1999May 1 1999

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Strong fairness and recursive communicating processes'. Together they form a unique fingerprint.

  • Cite this