Concurrent Models of Computation (31/3)

The parts of the textbook that pertain to the concurrent models of computation in this course specifically include

Section 6.1 on the general notion of actor-based models and the idea that connections between them represent signals, that actor networks can be viewed as systems of equations between these signals, and that their behavior can (sometimes) be described as the fixed point solution of a function.
Section 6.2 has been introduced here.
Section 6.3 on dataflow (without 6.3.4), a large and varied family of models of computation where the signals connecting the actors are sequences of values, also called tokens. Individual dataflow models of computation differ in how actors operate and how they exchange tokens. In many types of dataflow, the connections between actors are buffered, which means that production and consumption of a token are desynchronized, and the only constraint is that it be consumed after it was produced. In such models, many questions concern the size of the buffers between actors. If they are too small, actors may deadlock, if too big, they may consume undue amounts of resources. A fundamental question about those buffers is whether there is a finite bound to the buffer size required for a given dataflow network to execute --- and also what that size would be. This matter is considerably complicated (and, in general, unanswerable) when the behavior of consumption and production of tokens by an actor depends on the data values of these tokens.
- Synchronous Dataflow (SDF) Download Synchronous Dataflow (SDF) assumes that all actors in the system consume and produce a constant number of tokens at each of their ports whenever they fire, i.e. make a step. This permits full analysis of the buffer sizes required for deadlock-free execution, as well as complete compile-time (static) scheduling of the sequences of actors firings, the resulting buffer sizes, as well as the access patterns to the buffers. A slight generalization of SDF is Cyclo-static Dataflow (CSDF) Download Cyclo-static Dataflow (CSDF), which adds a little expressiveness without losing analyzability Download adds a little expressiveness without losing analyzability.
- By contrast, Dynamic Dataflow (DDF) makes no assumptions about the rates with which actors produce and consume tokens, and in fact allows them to be variable and dependent on the data and the state of an actor. As a result, it is in general undecidable whether a DDF network will deadlock or be able to execute within a finite amount of (buffer) space. However, there are ways of scheduling its actors in such a way Download there are ways of scheduling its actors in such a way that the result will be an execution in finite amount of space, if such an execution exists.
- Process Networks, also often referred to as Kahn Process Networks (after Gilles Kahn who first gave them a rigorous semantics Download first gave them a rigorous semantics) are a model in which independently executing processes are connected by channels with conceptually unbounded buffers. Their only constraint is that, while writing to a channel always immediately succeeds and returns (hence the need for unbounded buffers), reading is blocking, i.e. the execution of a process stalls if it attempts to read from an empty channel. Also, there is no way to test for the presence of a token in a channel. In general, process networks do not provide much foothold for analysis (deadlocks, buffer sizes, schedules etc.), but Kahn showed that the condition of blocking reads is sufficient to guarantee determinate behavior of a network, i.e. given some input, its output will be the same independent of the relative schedule or timing of the processes inside of it.
- Communicating Sequential Processes (CSP) Download Communicating Sequential Processes (CSP), devised by C.A.R. Hoare, is a model in which processes exchange tokens one by one with a handshake, i.e. the reader of a token will wait until a writer is there to accept it, and vice versa. Therefore, even though channels in CSP can be seen as communicating sequences of tokens as in the other dataflow models, they are unbuffered, and thus the execution of processes in CSP is much more tightly coupled. Also, while individual processes in Kahn process networks are assumed to be "regular" sequential, deterministic programs, a CSP process can include an element of non-determinism, by waiting for multiple input channels and picking any one of those on which a token first becomes available for communication.
The inset on page 168 briefly describes Petri Nets (after Carl Adam Petri, 1962), which is another formalism with close connections to dataflow and FSMs. They are often used to model protocols or interactions between entities that require some sort of analysis. For more details, see Murata, 1989 Download Murata, 1989.