Ordering is a necessary precondition to ensure causality. Since messages are the only actions in our system, a message can only be caused by a message that preceded it. Causality was first described in [7], using a system of logical clocks.
Ordering can be established by including an authenticated sequence number or virtual time stamp field in each message[14]. This would, however, not be sufficient, since the sequence number in a message would only acknowledge the reception of a certain number of messages prior to the transmission of the message; it would not, however, demonstrate the reception of specific messages, since the inclusion of a sequence number or virtual time stamp does not acknowledge the contents of the previous messages.
What is required is a protocol that provides for proof of message reception. Message reception could be proven by including within each message a copy of all previous messages.[8] While this would certainly be sufficient to prove causality, it would also be inefficient, especially for extended transactions. More importantly, it might also violate the privacy policy for multi-party transactions.
Early versions of the Isis system[1] included message digests or hashes as evidence of causality, and this is sufficient to address both of these concerns. In [10], the authors apply the signature technique from [14] to these message digests in order to provide authentication.
Our protocol uses a similar algorithm, including in each message a cryptographically secure message digest of all previous messages sent or received by the sender of the message. This does not violate any privacy concerns, nor is it inefficient since the size of the digest is relatively small and it can be incrementally computed. We define this message digest as context.
Unfortunately it is not always possible to provide causality in every transaction. A process P that sends two messages to another process Q and then receives a response from Q cannot validate the context since P cannot know whether or not Q received one or both messages prior to sending its response.
Fortunately it is possible to modify the protocol in order to provide causality in situations like this, by employing a half-duplex protocol that allows both processes to track the state of the transaction consistently. While normally this restriction would be a hindrance to performance, transactions requiring negotiation are essentially half-duplex since each process must wait for the other's latest message in order to formulate its response.