Modeling Timed Concurrent Systems using Generalized Ultrametrics

Xiaojun Liu, Eleftherios Matsikoudis and Edward A. Lee

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-45
May 1, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-45.pdf

Timed concurrent systems are used in concurrent and distributed real-time software, modeling of hybrid systems, design of hardware systems (using hardware description languages), discrete-event simulation, and modeling of communication networks. They consist of concurrent components that communicate using timed signals, which are sets of (semantically) time-stamped events. The denotational semantics of such systems is traditionally formulated in a metric space. In this metric space, causal components are modeled by contracting functions. We show that this formulation excessively restricts the models of time that can be used. In particular, it cannot handle super-dense time, commonly used in hardware description languages and hybrid systems modeling, finite time lines, and time with no origin. Moreover, if we admit continuous-time and mixed signals (essential for hybrid systems modeling) or certain Zeno signals, then causality is no longer equivalent to its formalization in terms of contracting functions. In this paper, we offer an alternative semantic framework using a generalized ultrametric that overcomes these limitations.


BibTeX citation:

@techreport{Liu:EECS-2006-45,
    Author = {Liu, Xiaojun and Matsikoudis, Eleftherios and Lee, Edward A.},
    Title = {Modeling Timed Concurrent Systems using Generalized Ultrametrics},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-45.html},
    Number = {UCB/EECS-2006-45},
    Abstract = {Timed concurrent systems are used in concurrent and distributed real-time software, modeling of hybrid systems, design of hardware systems (using hardware description languages), discrete-event simulation, and modeling of communication networks. They consist of concurrent components that communicate using timed signals, which are sets of (semantically) time-stamped events. The denotational semantics of such systems is traditionally formulated in a metric space. In this metric space, causal components are modeled by contracting functions. We show that this formulation excessively restricts the models of time that can be used. In particular, it cannot handle super-dense time, commonly used in hardware description languages and hybrid systems modeling, finite time lines, and time with no origin. Moreover, if we admit continuous-time and mixed signals (essential for hybrid systems modeling) or certain Zeno signals, then causality is no longer equivalent to its formalization in terms of contracting functions. In this paper, we offer an alternative semantic framework using a generalized ultrametric that overcomes these limitations.}
}

EndNote citation:

%0 Report
%A Liu, Xiaojun
%A Matsikoudis, Eleftherios
%A Lee, Edward A.
%T Modeling Timed Concurrent Systems using Generalized Ultrametrics
%I EECS Department, University of California, Berkeley
%D 2006
%8 May 1
%@ UCB/EECS-2006-45
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-45.html
%F Liu:EECS-2006-45