ptides

The introduction of network time protocols such as NTP (at a coarse granularity) and IEEE 1588 (at a fine granularity) gives a relatively consistent global notion of time to distributed systems. A key question that arises in the face of such technologies is how they can change the way that real-time distributed systems are developed.

In [1], we present a programming model called PTIDES (Programming Temporally Integrated Distributed Embedded Systems), which leverages time synchronization over distributed platforms. PTIDES uses discrete-event (DE) models as programming specifications for distributed real-time systems and extends discrete-event models with the capability of mapping certain events to physical time. We use model time to define execution semantics and add constraints that bind certain model time events to physical time. We limit the relationship of model time to physical time to only those circumstances where this relationship is needed. An execution model that permits out of order processing of events without sacrificing determinacy and without requiring backtracking is described in [1]. The formal foundation is based on the concepts of relevant dependency and relevant order.

As the next step, we want to continue our work in the following directions:

1. Design algorithms that statically analyze whether a given model is deployable over a network of nodes, assuming that we have upper bounds on the network delays and lower bounds on the time interval of events.
2. Build a prototype programming environment that combine heterochronous dataflow (HDF) [2] and DE. The overall architecture of an application is a distributed discrete-event model of interactions of concurrent real-time components (which we call actors). The components themselves have functionality that can be specified either by HDF models or conventional programming languages (C, C++ or Java, in this case).

Resources

• March 17, 2008: PTIDES is participating in the Google Summer of Code!
• ptides private forum (Open to ptides workgroup members only)

References:

[1]Y. Zhao, E. A. Lee, and J. Liu, "Programming temporally integrated distributed embedded systems", Technical Report UCB/EECS-2006-82, EECS Department, University of California, Berkeley, May 28 2006.

[2]A. Girault, B. Lee, and E. A. Lee, "Hierarchical finite state machines with multiple concurrency models," IEEE Transactions On Computer-aided Design Of Integrated Circuits And Systems, 18(6):742760, 1999.

Other References

Edward A. Lee, "Is Truly Real-Time Computing Becoming Unachievable?," Talk at the Real-Time and Embedded Technology and Applications Symposium (RTAS), Bellevue, WA, April 3-6, 2007.

Yang Zhao, Jie Liu, Edward A. Lee, "A Programming Model for Time-Synchronized Distributed Real-Time Systems," RTAS, pp. 259-268, 13th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS'07), 2007. Internal Version

Yang Zhao. "PTIDES: Programming Temporally Integrated Distributed Embedded Systems," Seventh Biennial Ptolemy Miniconference, Berkeley, February 13, 2007.

Yang Zhao, Edward A. Lee and Jie Liu, " Application of Programming Temporally Integrated Distributed Embedded Systems", In Proceedings of 2006 IEEE 1588 Conference Gaithersburg, MD, October 2-4, 2006.

References to other people's work we find interesting

• Jeremy Elson, Lewis Girod and Deborah Estrin, Fine-Grained Network Time Synchronization using Reference Broadcasts Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002). Information about RBS, used for timing in wireless systems.
• The work of Binoy Ravindran: "Time/Utility Function Decomposition Techniques for Utility Accrual Scheduling Algorithms in Real-Time Distributed Systems", H. Wu, B. Ravindran, E. D. Jensen, and P. Li, IEEE Transactions on Computers, Volume 54, Number 9, pages 1138 - 1153, September 2005

Mailing lists and discussion forums may be found under the ptides link above.

To modify this page, use CVS.