Paper Info
Title
Grounding Synchronous Deterministic Concurrency in Sequential Programming.
Abstract
Using a new domain-theoretic characterisation we show that Berry's constructive semantics is a conservative approximation of the recently proposed sequentially constructive (SC) model of computation. We prove that every Berry-constructive program is deterministic and deadlock-free under sequentially admissible scheduling. This gives, for the first time, a natural interpretation of Berry-constructiveness for shared-memory, multi-threaded programming in terms of synchronous cycle-based scheduling, where previous results were cast in terms of synchronous circuits. This opens the door to a direct mapping of Esterel's signal mechanism into boolean variables that can be set and reset under the programmer's control within a tick. We illustrate the practical usefulness of this mapping by discussing how signal reincarnation is handled efficiently by this transformation, which is of linear complexity in program size, in contrast to earlier techniques that had quadratic overhead.
Year
DOI
Venue
2014
10.1007/978-3-642-54833-8_13
Lecture Notes in Computer Science
Keywords
Field
DocType
Concurrency,Constructiveness,Determinism,Mealy Reactive Systems,Synchronous Programming,Esterel
Programming language,Programmer,Scheduling (computing),Concurrency,Constructive,Computer science,Quadratic equation,Algorithm,Theoretical computer science,Model of computation,Esterel,Boolean data type
Conference
Volume
ISSN
Citations 
8410
0302-9743
7
PageRank 
References 
Authors
0.46
31
4
Name
Order
Citations
PageRank
Joaquin Aguado1414.65
Michael Mendler231434.60
Reinhard von Hanxleden341247.20
Insa Fuhrmann4161.68