Causal reversibility blends reversibility and causality for concurrent systems. It indicates that an action can be undone provided that all of its consequences have been undone already, thus making it possible to bring the system back to a past consistent state. Time reversibility is instead considered in the field of stochastic processes, mostly for efficient analysis purposes. A performance model based on a continuous-time Markov chain is time reversible if its stochastic behavior remains the same when the direction of time is reversed. We bridge these two theories of reversibility by showing the conditions under which causal reversibility and time reversibility are both ensured by construction. This is done in the setting of a stochastic process calculus, which is then equipped with a variant of stochastic bisimilarity accounting for both forward and backward directions.
翻译:基于随机过程代数的因果可逆性和时间可逆性的桥接
Translated abstract:
基于随机过程的时间可逆性主要用于进行高效的分析,而并发系统的因果可逆性则将可逆性和因果关系融合在一起。因果可逆性意味着,只要已经撤销了所有后果,就可以撤销动作,从而将系统回溯到先前的一致状态。我们通过展示在何种条件下可以通过建模实现因果可逆性和时间可逆性,对这两种可逆性理论进行了桥接。这在一个随机过程演算的背景下完成,该演算还配备了一种考虑正向和反向的随机等价关系的变体。