Detection of orthogonal interval relations

The complete set R of orthogonal temporal interactions between pairs of intervals, formulated by Kshemkalyani, allows the detailed specification of the manner in which intervals can be related to one another in a distributed execution. This paper presents a distributed algorithm to detect whether pre-specified interaction types between intervals at different processes hold. Specifically, for each pair of processes i and j, given a relation r(i,j) from the-set. of orthogonal relations R, this paper presents a distributed (on-line) algorithm to determine the intervals, if they exist, one from each process, such that each relation r(i,j) is satisfied for that (i, j) process pair. The algorithm uses O(n min (np, 4mn)) messages of size O(n) each, where n is the number of processes, m is the maximum number of messages sent, by any process, and p is the maximum number of intervals at any process. The average time complexity per process is O(min(np, 4mn)), and the total space complexity across all the processes is min(4pn(2) - 2np, 10mn(2)).