Deterministic Concurrency

Toward a deterministic treatment of concurrency for the general case.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Synchronic State Diagram

The article mentions Synchronic State Diagrams, overloading the 'SSD' acronym. I'm interested in some more detailed resources on this subject. Google gives me a bunch on history (synchronic charts for US), some on linguistics, not so much on programming.

I've been interested for a long time in deterministic concurrency in various forms such as Kahn Process Networks, single-assignment linear futures, Lightweight Time Warp, and eventual consistency models such as CRDTs.

As the article mentions, it's relatively easy to model external sources of non-determinism as an effect. The article mentions non-deterministic choice being "simulated by reading a specific bit", which I usually call the 'oracle' method based on some paper I read a long, long time ago. Though, it seems awkward to reflect on internal data races this way. I usually model arrival-order non-determinism as being introduced by an abstract scheduler, distinct from an 'amb' effect.

Better search term.

Overloading is hard to avoid sometimes, the first try was ‘Synchronic Net’. A better search term might be ‘Synchronic Computation’. The details of SSD have not been published yet, a pdf summary of the work that led to SSD is here. An external scheduler for non-determinism would indeed be less awkward, I was trying to address the concerns of process algebraists who take non-determinism to be fundamental.

Although I was familiar with Kahn Process Networks (KPN), the other references were less so and am grateful for them. KPNs and other dataflow/datastream models are mid level structures whose nodes are understood to be Turing Machines or Von Neumann processors, and program control is based on data tokens. I felt their level of abstraction was too high and obliged coders to view every task as a stream based program, so developed a more general purpose bit level machine model called the Synchronic A-Ram, where streams can implemented as higher level constructs.

Instances of the motivating examples for static single assignments are not impossible in the interlanguage environment mentioned in the summary, but are rendered far less likely by encoding dataflows as interstrings, which are the basic program syntactic structures. (More overloading -- there is no connection to Selinker’s linguistics concept of an interlanguage as an intermediate form in second language acquisition.) My initial impression is that Lightweight Time Warp is an interesting optimization for running simulations on processor networks, and will need more time to absorb CRDTs, and determine their connections and overlaps with the restrictions in interlanguage.

Youtube & slides links.

There is more comment on deterministic concurrency in a Youtube link to the BCTCS presentation on Alpha-Rams, which is here.

The slides may be downloaded from here.