Message duplication and reordering causes violation of causal consistency

[pfons]

The algorithm 2 produces results that violate causal consistency when messages are duplicated and reordered by the network. This situation can occur in practice because the UDP protocol, which is used for the server-server communication, does not guarantee in-order delivery nor does it guarantee at-most once delivery.

The following steps are sufficient to reproduce the bug, with Client A, Client B and Client C running on different servers:

    Req 1: Client A: PUT key, “NA”
    Req 2: Client A: PUT key, “Request”

    Req 3: Client B: GET key -> “Request”
    Req 4: Client B: PUT key-effect, “Reply”

   <replay packets sent by Req 1>

    Req 5: Client C: GET key-effect -> “Reply” 
    Req 6: Client C: GET key -> “NA”

The steps above show that client C can see the effect event (“Reply”), produced by Client B, without seeing the cause event (“Request”), produced by Client A.

[MohsenLesani]

The semantics in the paper models reordering of messages but not message duplication. Duplication can be modularly handled by transformers presented in Verdi paper. http://verdi.uwplse.org/verdi.pdf