Replicated Transaction Ordering: Clock Synchronisation and Timestamps

The most stringent requirement for ordering of messages in multi-party communication systems is given in Birman's paper[#birman##1#]. A Unicast packet delivery may be used to build up a replicated application. However, if the application requires most stringent consistency, it may be that each transaction from each client be ordered with respect to all other client transactions, as well as with respect to each replicant server. This ordering can be achieved (to a required level of reliability at least, as with all distributed programs) by timestamping requests, and using a receive queue in all hosts within which messages are only allowed to the server in monotonically increasing order after a global synchronisation step. If clocks are synchronised, these protocols may be relaxed, since an message received from source A can be ordered w.r.t a message from source B purely by source timestamp. Care must be taken that we can still detect failure of clock synchronisation so that these protocols fail to safe. Again, with Atomic Broadcast protocols, a level of optimisation may be achieved by actually using network level multicast (and presumably transport level multicast). Here, a packet that must be sent to more than one destination may be simply multicast. Messages have the following control information: As in [#lamport##1#], assume systems advance at least one tick per send or receive message. Given a particular protocol, we would like to establish whether a version using multicast and/or timestamps and clients and servers with synchronised clocks can be shown to have the same semantics, but less packets exchanged. The most common failure is the channel, especially in wide area networks. This means that using multicast will result in the simplest failure mode (no answer from anyone). Real time delivery can be optimised using network level multicast as the message will be delivered at almost the same time (when compared with successive unicasts: of course we cannot ignore things like propagation delay, etc). Thus the buffer time will be less and this in turn save in buffer space and end-end delay. Considering dynamically changing groups, if we can make group join/leave message to be ordered, then multicast group can avoid the problems of different process having different views of group membership. Such problems include the fact that this makes it harder to determine consistently the nature of a majority in a vote, for example. Multicast packet delivery is a useful facility for optimising network efficiency of multipart distributed applications. However, the interactions between the applications and a multicast system are more complex than is obvious at first sight. One consequence of the high bandwidth requirements of multi-party multimedia communication is that we will need an interaction between multicast routing and the application and this may need to be both rapid in terms of switching forwarding down paths on and off, and powerful in terms of allowing many hierarchical paths to allow different media and sub-band codes within a single medium, to be selectively forwarded down sub-trees of a multicast distribution tree. It is clear that if we are to make effective use of multicast in the WAN, we are going to need a large address, flexible multicast address space.