Project

A project is required for this course. A project will typically have an experimental component (software and/or models) backed by a paper describing the principles being investigated.

Due Dates

February 19: One page project proposal.
March 12: Project update presentations, in class.
April 23: Project update presentations, in class, and One page project status report due.
May 5: Project paper submission due.
May 11: Review of project papers due.
May 13: Project presentations.
May 15: Project papers due.

Guidelines

The paper component will be expected to be roughly conference quality, with appropriately chosen and cited references to the literature. Papers must be scholarly, meaning that they describe original work, critically assess both the advantages and disadvantages of that work, credit external contributions to that work, and compare to other published work. Ideas in the paper should be backed by concrete examples in the form of models and/or software implementations.

Papers should be no more than four pages in length, two column format, as given by the Latex template. Students are required to submit an extended abstract for review by other students in the class. The extended abstract should follow the same format as the paper, but can be shorter. A final presentation will be required.

Project Suggestions

Below is an evolving list of project suggestions:

Peer to Peer Swarmlets. The paper A Vision of Swarmlets Download A Vision of Swarmlets
puts forth a vision of distributed applications where one application (called a swarmlet) provides a service to another through a mechanism called an accessor. This project will develop a mechanism for deploying such services in a persistent and robust way on cloud servers, or more interesting, on the SwarmBox Links to an external site. that is under development.
FMI for Cyber-Physical Systems. The Functional Mockup Interface was originally developed to enable simulators for continuous dynamics (such as Modelica-based simulators) to be able to exchange models (FMI for Model Exchange) or to co-simulation (FMI for Co-Simulation). FMI has a number of weaknesses for modeling cyber-physical systems, where in addition to the continuous dynamics of physical, there is the discrete dynamics of software-based systems. This project will use the emerging CyPhySim simulator to explore the limits of FMI and proposed extensions.
Distributed Discrete-Event Systems for the Internet of Things. The recently proposed Accessors Links to an external site. architecture (see vision paper Download vision paper
) provides an actor-oriented composition mechanism for IoT applications. This project will explore the use of time stamps and distributed clock synchronization to improve determinacy and reliability of such applications. This project could start with a Vert.x-based prototype of such a distributed schema developed by Patricia Derler in Ptolemy II. A reach goal for the project would be to deploy distributed swarmlets on the recently developed SwarmBox architecture.
Quantized-State Solvers. A recently proposed modeling and simulation strategy for continuous dynamics called quantized-state solvers (QSS) shows considerable promise of providing a better modeling paradigm for cyber-physical systems than conventional numerical ODE solvers. Specifically, QSS systems are built on top of a deterministic discrete-event simulation strategy and obviate the need for backtracking. For some kinds of systems, they are also potentially much more efficient. This project will explore their strengths and weaknesses with specific CPS examples. The project can use (and possibly extend) the recently created CyPhySim simulator, which provides a prototype QSS simulator.
Completeness of Determinism: A recent paper Links to an external site. studies modeling of discrete physical phenomena such as collisions and friction and conjectures a connection between the limitations of such models and the nondeterminism introduced in physical models by quantum mechanics. This project will study the theory and investigate this possible connection.
Textual syntaxes for block diagrams: Visual syntaxes for actor-oriented models have a certain appeal for pedagogy, but many people feel that visual syntaxes will never scale sufficiently to be able to deal with complex designs. This project will explore textual syntaxes that are compact, readable, and capable of expressing (at least) the Ptolemy II abstract syntax for actor-oriented models. Specifically, this project should explore recently developed meta-programming tools such as Chisel that use modern language features.
Actor Languages. The low-level Java programming currently used to create actors in Ptolemy II is far from satisfactory. Earlier efforts to create domain-specific languages (DSLs) for developing actors, such as Cal
, are promising, but have not caught on. Modern languages such as Scala
that embed DSLs within Java seem promising. The purpose of this project is to explore how actors should be best designed. The project should examine prior actor languages, including at least StreamIT
and Cal
.
Shared Data Structures. Asynchronous deterministic concurrent models of computation such as process networks and dataflow have difficulty with shared data structures. Naive implementations trigger a great deal of copying of data. Optimizations such as reference counts, and more interesting, the recently emerged differential dataflow
techniques, promise to be much better. Differential dataflow encodes related versions of a data structure by encoding their differences rather than making copies. This project will build models of such encodings, formulate optimization problems, provide implementation strategies, and perform experiments to assess the strategies. The UpdatedArrayToken class in Ptolemy II has a very rudimentary start on such an effort. The immutable sets and hash maps of Vert.x are also relevant.
BigActors. The BigActors
model of computation leverages Milner's Bigraphs
, where two superimposed graphs represent locality and connectivity. This is related to the Diposet
structure introduced by Davis, which superimposes partially ordered sets representing hierarchy and connectivity. There are a number of possible projects that would build on these models, either exploring their theory, or analyzing their utility in practical design of location-aware distributed systems and services.
Discrete-Event Variants. A number of variants of discrete-event semantics have appeared over time. The recently introduced P language
, for example, has been used effectively to synthesize device drivers. Simulink has recently been extended with SimEvents. The much older DEVS [Zeigler et al., Theory of Modeling and Simulation, Academic Press, 2000] is widely use in large scale simulation. Network simulators such as NS-3 and Opnet also use a DE variant. Hardware description languages VHDL, Verilog, and System-C all use DE variants. This project will study these variants, compare them using concrete models implemented using real tools, and analyze them according to the semantic principles discussed in the course.
Distributed Timed Systems. A number of programming model have been developed for realizing distributed real-time systems. Recent developments include physically-asynchronous, logically synchronous (PALS
) designs and Ptides
. These appear to be related to the older concept of latency-insensitive design
and many prior efforts to desynchronize implementations of synchronous languages. The purpose of this project is to compare these approaches by seeking concrete examples that illustrate the strengths and weaknesses of each, and to analyze them according to the semantic principles of the course.
Modal Models. A number of techniques for constructing modal models have been developed, including Statecharts, Hybrid Bond graphs, Simulink/Stateflow, Ptolemy II, and others. There are also some specification styles that focus on parameterizing models and switching parameter values according to mode changes, including Scenarios
and SPDF
. The purpose of this project is to study and analyze these alternatives through concrete examples of models with mode changes.
Threads. Threads are well understood to be problematic as a concurrent programming model. A number of more disciplined and patterned uses of threads have been proposed, including Protothreads
, Cilk
, and Behavioral Programming
. The purpose of this project is to analyze these techniques for determinism and expressiveness in light of the analysis techniques given in this course.
Concurrent user interfaces: Concurrency models for user interface design have been a mixed bags. Attempts to use threads, as in Java, have failed miserably. Prevailing methods are event based, but rather ad-hoc and unprincipled. An old but recently enhanced event-based model of computation called Event Relationship Graphs (ERG) seems to hold considerable promised to improve the situation. This project would explore this idea through prototypes and analysis.
Actor-oriented security models: Study the problem of security in distributed actor-oriented models and implement a security toolkit for building secure distributed models. This project would build on concepts like capabilities and leverage the fact that actor libraries can be more flexibly designed than programming languages. Recently emerging ideas like opacity
(for preserving privacy) could also be relevant.
Static analysis of continuous-time models: The theory of control systems has a rich set of formal analysis techniques for continuous-time feedback systems. This project will develop analysis tools that apply that theory to Ptolemy II models in the Continuous domain to perform, for example, stability or robustness analyses. A key element will be to handle modal models.
Dataflow with time stamps: Dataflow models may benefit from using time stamps. A starting point for researching this is to look at Naiad
.