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-fallow relation, to characterize directly coupled causal messages and a corresponding message delivery scheme, i.e., direct-fallow 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.