Home > Uncategorized > Event patterns: from process algebra to algorithmic causal sets

Event patterns: from process algebra to algorithmic causal sets

Notions of event and event occurrence play a central role in various areas of computer science and ICT (Information and Communication Technology).

In this proposal we are particularly interested in event concepts from process algebras such as Milner’s Calculus of Communicating Systems (CCS) and Hoare’s Communicating Sequential Processes (CSP), and related languages (e.g. LOTOS), since their high abstraction level makes it possible and attractive to investigate the impact of these event notions, and associated constructions, in the apparently remote field of causal sets, intended as discrete models of spacetime.

While, in line with General Relativity, a spacetime event in a causal set is simply a node in a directed, acyclic graph (DAG), in process algebras events represent the building blocks of more elaborate structures called processes.  Events may occur ‘internally’ – inside a process – or as part of the interaction with another process; they may be atomic or involve the exchange of data items; they may or may not induce changes in the local states of the interacting parties; they may be organized in temporal/causal patterns and be encapsulated in processes to be used, in turn, as building blocks of more complex event patterns.

In spite of the richer event-related constructions offered by process algebras, the formal, ‘true concurrency semantics’ of the latter maps the syntax of an algebraic specification, no matter how complex, into a DAG, thus providing a common basis for comparing the event  patterns arising in the two fields.

In particular, we are interested in exploring algorithmic causal sets – those obtained by deterministic rather than stochastic procedures – and in verifying the extent to which their emergent properties match the structured behavioral patterns typical of process algebra.
One may argue that an event happens when a trace of its occurrence gets recorded somewhere. In process algebra, event occurrences may indeed affect the local states of the interacting processes. Can we meaningfully separate event threads in algorithmic causal sets? Can we detect the emergence of process-like substructures in them – maybe a subgraph with some kind of boundary?  Can such ‘processes’ be stateful too?  Can we distinguish between their internal and external events?  More generally, which subset of the compact set of behavioural operators of process algebras (sequential and parallel composition, choice, etc.) can find a counterpart in the emergent structures of algorithmic causal sets?

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: