Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The Signal synchronous multiclock approach to the design of distributed embedded systems
Gamatié A., Gautier T. IEEE Transactions on Parallel and Distributed Systems21 (5):641-657,2010.Type:Article
Date Reviewed: Jan 7 2011

This is a very insightful paper on how to use Signal, a multi-clocked synchronous (polychronous) language, to model an embedded application to be deployed distributively across asynchronous communication channels. Benveniste et al.’s previous work [1] on the theory of endochrony and isochrony often baffled embedded system designers; this paper offers a much more intuitive explanation, though not as rigorous. For the formal definitions, readers should refer to the original paper [1].

Gamatié and Gautier consider a flight warning system from a previously published Airbus A340 case study. The warning system is abstracted into two processes: an alarm manager process and an alarm notifier process. In the fully synchronous model, the communication between them is instantaneous. But such instantaneous communication cannot be guaranteed in a distributed deployment, not even if we are referring to logical instants, because one cannot construct a logical instant correctly in a distributed system, due to the absence of a global time synchronization mechanism. Therefore, one has to be able to guarantee some property of the communication between the two processes, such that their asynchronous communication preserves the order of messages between the components. This, along with an additional property that each process can tolerate unspecified delays between messages as long as they arrive in the correct order, can guarantee that the distributed deployment preserves the same properties as those of the synchronous model.

The first property pertaining to the communication is isochrony, and the second property of individual processes is endochrony. Thus, if the designer can show that each process is endochronous and that the communication is isochronous, he or she can show that a first in, first out (FIFO)-based communication channel (order preserving) that desynchronizes the system will preserve correctness.

The Signal compiler has inbuilt clock calculus that establishes endochrony through a heuristic procedure. Also, Benveniste et al.’s original theorems [1] show that proving the isochrony of communication between two endochronous processes can be reduced to proving the endochrony of a projection of the two processes on their communicating variables and their fan-in cones. This can also be done using an automated heuristic procedure.

Thus, the authors can show, with the Signal compiler, that the fully synchronous model of the flight warning system can be deployed on a distributed architecture while preserving correctness. “Correctness” here means that any property proven on the synchronous model is preserved in the desynchronized model. The authors go one step further and use the SIGALI model checker to prove that their FIFO model has an order-preserving property. This is crucial: the endochrony of individual processes and the isochrony of communication would not be useful if the FIFO model was not order preserving. However, no assumptions are made regarding the delay in message delivery due to the FIFO.

Unlike many previous publications on Signal and polychrony, this paper is very well and lucidly written. As a result, it could be used as reference material for a class on software synthesis from polychronous models, or even as an example of refinement-based design of software from formal models.

One caveat in the paper is the section on Signal and its semantics. The definitions, theorems, and semantic concepts are based on Lee and Sangiovanni-Vincentelli’s tagged signal model [2]. This formalism makes it possible to explain concepts of endochrony in a unified semantic framework, but it obfuscates them for regular practitioners who want to learn how to use the methodology; much simpler semantic frameworks exist--for example, Nowak’s work [3] uses synchronous structures (akin to event structures) that would make it much easier to understand.

The second issue is that not all models are endo/isochronous. This means that the methodology is applicable to a very special class of polychronous models. The requirement must be relaxed before this methodology is widely accepted. Potop-Butucaru et al.’s notion of weak endochrony [4] is one relaxation of the strict requirements of endochrony. It would be nice to see some methodological development based on weak endochrony and distribution. Recently, Talpin et al. started working on a methodology for detecting weak endochrony with heuristic algorithms [5], but this work is not discussed here.

Reviewer:  Sandeep Shukla Review #: CR138695 (1107-0726)
1) Benveniste, A.; Caillaud, B.; Le Guernic, P. CONCUR 99: concurrency theory: 10th International Conference (LNCS 1664). Springer, , 1999.
2) Lee, E.; Sangiovanni-Vincentelli, A.; , A framework for comparing models of computation. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 17, 12(1998), 1217–1229.
3) Nowak, D. Synchronous structures. Information and Computation 204, 8(2006), 1295–1324.
4) Potop-Butucaru, D.; Caillaud, B.; Benveniste, A. Concurrency in synchronous systems. Formal Methods in System Design 28, 2(2006), 111–130.
5) Talpin, J.-P.; Ouy, J.; Besnard, L.; Le Guernic, P. Compositional design of isochronous systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE ’08) ACM, 2008, 928–933.
Bookmark and Share
 
Distributed Networks (C.2.1 ... )
 
 
Modeling Techniques (C.4 ... )
 
 
Real-Time And Embedded Systems (C.3 ... )
 
 
Distributed Systems (C.2.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Distributed Networks": Date
Data communications and distributed networks (2nd ed.)
Black U., Prentice-Hall, Inc., Upper Saddle River, NJ, 1987. Type: Book (9789780835913416)
Sep 1 1988
Fault-tolerant routing in DeBruijn communication networks
Esfahanian A., Hakimi S. IEEE Transactions on Computers 34(9): 777-788, 1985. Type: Article
Jun 1 1986
SAA/LU6.2: distributed networks and applications
Edmunds J., McGraw-Hill, Inc., New York, NY, 1992. Type: Book (9780070190221)
Jan 1 1994
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy