Characterization and delivery of directly coupled causal messages in distributed systems
Causal Order (CO) is an important but basic property of message-passing based distributed systems. Violations of causal order delivery normally lead to significant inconsistencies, particularly in distributed virtual environments. However, CO is only a partial order, which captures messages that have cause-effect relations. It does not order concurrent messages which occur independently at different processes. This paper proposes a new relation, i.e., direct-follow relation, to characterize directly coupled causal messages and a corresponding message delivery scheme, i.e., direct-follow order (DFO) delivery. The DFO delivery effectively enforces the delivery order of certain concurrent messages and thus can be used to further eliminate inconsistencies caused by these messages. It is a stronger ordering mechanism than CO. However, as shown in the paper, messages with the direct-follow relation cannot be always delivered according to the DFO, since the ordering of concurrent messages required by the DFO may result in conflicts in message dependency. This paper explains the motivation of defining the DFO, explores its properties and gives the conditions under which direct-follow messages can be delivered according to the DFO.
distributed systems causal order delivery distributed virtual environments direct-follow relation happen-before relationship causal and total order delivery direct-follow order delivery dependency set