Homework Assignment

The purpose of this exercise is to extend the process networks (PN) model of computation with a nondeterministic merge actor. A secondary purpose is to become familiar with the use of Ptolemy II as an extensible framework for experimenting with models of computation. You will need to have set up Ptolemy II so that you can extend it (preferably using Eclipse), as explained in the previous homework. Then see the Designing Actors chapter of the Ptolemy II users manual. You are strongly encouraged to following the Ptolemy II coding style.

The PN director in Ptolemy implements the Kahn/MacQueen process network semantics. Each actor has its own thread of control, implemented as a Java thread, and when it reads from input ports, the thread blocks if there are no tokens on the input port. The hasToken() method of the IOPort class always returns true in PN, so there is no way for an actor to ask the input port whether data is really available. The get() method blocks until there is data. According to Kahn and MacQueen, this is policy yields determinsm in the sense that a process network uniquely defines the sequence of tokens that will flow along any arc.

This assertion, however, relies on the actors to be ``well behaved'' in certain ways. In Ptolemy II, actors are written in Java, which is a rich and expressive programming language, and it is easy to define actors that are not well behaved. Your task is to define an actor that implements a nondeterministic merge. This actor will have two input ports and one output port, and every token that is made available at either input port will be produced on the output port. The tokens on the output port will form a stream that is an arbitrary interleaving of the two input streams. The following properties must be satisfied (demonstrate that they are):

  1. If token t1 appears before token t2 on either input port, then it will appear before t2 on the output port. That is, the ordering at each input is preserved on the output.
  2. Every token that appears at an input port will eventually appear at the output port.

Please answer the following questions:

  1. What happens in your actor code when your model is executing the stop button is pushed on the toolbar?
  2. Create a deadlock in your model. What happens to your code?
  3. Create a feedback path from the output of your nondeterminstic merge back to one of its inputs. Discuss what happens when a stream is presented at the other input.