Dumitru Potop-Butucaru
ABSTRACT
Synchronous reactive formalisms associate concurrent behaviors to precise schedules on global clock(s). This allows a non-ambiguous notion of "absent" signal, which can be reacted upon. But in desynchronized (possibly distributed) implementations, absent values must be explicitely exchanged, unless behaviors were already provably independent and asynchronous (a property formerly introduced as endochrony).
We provide further criteria restricting "reaction to absence" to allow correct desynchronized implementation. We also show that these criteria not only depend on the desired correctness properties, but also on the desired structure of the implementation.
- P. Amagbégnon, L. Besnard, and P. L. Guernic. Implementation of the data-flow synchronous language signal. In Proceedings PLDI'95, La Jolla, CA, USA, June 1995. Google Scholar
Digital Library
- H. Attiya. Distributed Computing. McGraw-Hill Publishing Company, 1998.Google Scholar
- A. Benveniste, B. Caillaud, and P. L. Guernic. Compositionality in dataflow synchronous languages: Specification and distributed code generation. Information and Computation, 163:125--171, 2000. Google ScholarDigital Library
- A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. L. Guernic, and R. de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1):64--83, Jan. 2003.Google ScholarCross Ref
- F. Boussinot and R. de Simone. The SL synchronous language. Research Report RR-2510, INRIA, Sophia Antipolis, France, March 1995. http://www.inria.fr/rrrt/rr-2510.html.Google Scholar
- P. Caspi, A. Girault, and D. Pilaud. Distributing reactive systems. In Proceedings PDCS '94, Las Vegas, USA, October 1994.Google Scholar
- T. Grandpierre and Y. Sorel. From algorithm and architecture specification to automatic generation of distributed real-time executives: a seamless flow of graphs transformations. In Proceedings of First ACM and IEEE International Conference on Formal Methods and Models for Codesign, MEMOCODE '03, Mont Saint-Michel, France, June 2003. Google ScholarDigital Library
- P. L. Guernic, J.-P. Talpin, and J.-C. L. Lann. Polychrony for system design. Journal for Circuits, Systems and Computers, April 2003. Special Issue on Application Specific Hardware Design.Google Scholar
- N. Halbwachs. Synchronous Programming of Reactive Systems. Kluwer academic Publishers, 1993. Google ScholarDigital Library
- N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 79(9):1305--1320, 1991.Google ScholarCross Ref
- G. Kahn. The semantics of a simple language for parallel programming. In J. Rosenfeld, editor, Information Processing '74, pages 471--475. North Holland, 1974.Google Scholar
- E. Lee and T. Park. Dataflow process networks. In Proceedings of the IEEE, volume 83, pages 773--799, 1995.Google ScholarCross Ref
- D. Potop-Butucaru and B. Caillaud. Correct-by-construction asynchronous implementation of modular synchronous specifications. Fundamenta Informaticae, 78(1):131--159, 2007. Google ScholarDigital Library
- D. Potop-Butucaru, B. Caillaud, and A. Benveniste. Concurrency in synchronous systems. Formal Methods in System Design, 28(2):111--130, March 2006. Google ScholarDigital Library
- M. Singh and M. Theobald. Generalized latency-insensitive systems for single-clock and multi-clock architectures. In Proceedings DATE'04, Paris, France, 2004. Google ScholarDigital Library
Index Terms
- Necessary and sufficient conditions for deterministic desynchronization
Recommendations
From Concurrent Multi-clock Programs to Deterministic Asynchronous Implementations
Application of Concurrency to System Design, the Eighth Special IssueWe propose a general method to characterize and synthesize correctness-preserving asynchronous wrappers for synchronous processes on a globally asynchronous locally synchronous (GALS) architecture. While a synchronous process may rely on the absence of ...
Desynchronization: Synthesis of Asynchronous Circuits From Synchronous Specifications
Asynchronous implementation techniques, which measure logic delays at runtime and activate registers accordingly, are inherently more robust than their synchronous counterparts, which estimate worst case delays at design time and constrain the clock ...
Correct Execution of Transactions at Different Isolation Levels
Many transaction processing applications execute at isolation levels lower than SERIALIZABLE in order to increase throughput and reduce response time. However, the resulting schedules might not be serializable and, hence, not necessarily correct. The ...
Comments