Entailment-based actions for coordination

• Type: Article in International Scientific Journal
• Date: 1998

Authors

Monteiro, L (Author) Other; Porto, A (Author) Other

Journal

Title: Theoretical Computer Science

Vol. 192

Pages: 259-286

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 2 Citations

Scopus - 2 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-001-8G9

DOI: 10.1016/s0304-3975(97)00152-7

Abstract (EN): Coordination seems to require (at least in part) a persistent repository of information that concurrent agents can query and update. Indeed, most coordination languages are based on a shared data space model. They differ in the details of how actions and processes are defined, but most assume the data space to have a multiset structure, and actions to be rewritings. We find this view too particular and not expressive enough in many practical cases, and set out in this paper to develop a more general theory of actions, abandoning the syntactic rewriting paradigm in favour of a more abstract notion of update based on entailment. Actions may impose certain properties to be entailed or not entailed, and the corresponding update is the minimal change, possibly by removing information and adding new one, that satisfies the (dis)entailment requirements. We work with abstract situations (standing for information states) ordered under entailment. We show that if a situation space is a coherent, prime algebraic, consistently complete poset then a suitable class of its subsets, which we call definite, corresponds to update operations with suitable generality (any situation can be obtained by an update of any other) and good compositional properties (closure under sequential and synchronous composition). These updates can be seen as unconditional determinate actions, i.e. total functions from situations to situations; these functions are always a composition of a restriction (losing information) and an expansion (adding consistent information). We show that the space of updates is itself an ordered structure similar to a situation space. Then we consider general actions, which may be conditional and nondeterministic. They thus represent arbitrary relations between situations, but are actually more specific, coding the intensional rather than extensional behaviour, this being relevant for the synchronous composition. We formulate general actions as (suitably restricted) relations between situations and definite sets, define their synchronous, sequential and choice compositions, and show them to be fully abstract with respect to observing situation transitions under any compositional context. The synchronous and sequential, compositions give rise to an intrinsic notion of independence of actions, that reflects their ability to be truly concurrent.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 28