On the expressiveness of timed coordination models

Although very simple and elegant, Linda-style coordination models lack the notion of time, and are therefore not able to precisely model real-life coordination applications. Nevertheless, industrial proposals such as TSpaces and JavaSpaces, inspired from Linda, have incorporated time constructs.This paper aims at a systematic study of the introduction of time in coordination models. It builds upon previous work to study in a coherent framework the expressiveness of Linda extended with two notions of time, relative time and absolute time, and, for each notion, two types of features. On the one hand, with respect to relative time, we describe two extensions: (i) a delay mechanism to postpone the execution of communication primitives, and (ii) explicit deadlines on the validity of tuples and on the duration of suspension of communication operations. On the other hand, for absolute time, we introduce: (iii) a wait primitive capable of waiting till an absolute point of time, and (iv) time intervals, both on tuples in the data store and on communication operations.This expressiveness study points out a most expressive language for which an implementation is described, thereby allowing for the implementation of all the languages presented in the paper.