Process algebra reconsidered


Paper is here. The following incorrect claim is not unusual in the process algebra literature. Basically, what is missing [in classical automata theory] is the notion of interaction: during the execution from initial state to fi nal state, a system may interact with another system. This is needed in order to…

Deterministic multithreading


An interesting paper appearing in ASPLOS proceedings provides a "deterministic" locking method Kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. The algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time…

Are threads evil? (updated)


This paper by Prof. Edward Lee explains something of why "threads" are such a painful abstraction.  As Prof. Lee notes, threads intrinsically create unspecified program operation (which he calls non-determinism) and resource conflicts which we then attempt to "prune" via synchronization and complex tools. In an earlier note, I argued…