Desynchronization: From Macro-step to Micro-step
Yu Bai · 2018
Desynchronization is a central technique for the deployment of synchronous models in distributed environments. In the past decade, various notions of desynchronization as well as concurrency of synchronous systems have been developed. However most works consider only the macro-step semantics of the synchronous systems, therefore are not applicable to those with micro-step semantics like Esterel and Statechart. In particular, macro-step notations lack of the capability to describe deadlocks which are available only via micro-step level modeling. In this paper, we present a desynchronization framework that covers both abstract levels of macro-step and micro-step. In particular, we use labeled transition system to model the operational semantics of general process networks, and further developed the macro-step synchronous modeling. Based on this notion, each transition relation is further decorated with causal pre-orders to model micro-steps within a macro-step, which are then explicitly modeled as transition relations after a desynchronization transformation. Based on this framework, we re-examined some previous macro-step level desynchromzation techniques and established new theories that are necessary for their micro-step level adaptation.