AN ADAPTIVE CAUSAL ORDERING ALGORITHM SUITED TO MOBILE COMPUTING ENVIRONMENTS

Causal message ordering is required for several distributed applicatio ns, In order to preserve causal ordering, only direct dependency infor mation between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be sign ificantly reduced, In this paper we present an algorithm that uses thi s knowledge to efficiently enforce causal ordering of messages, The pr oposed algorithm does not require any prior knowledge of the network t opology or communication pattern, As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dyn amically changing multicast communication groups, and minimizing the c ommunication overheads, With regard to communication overheads, the al gorithm is optimal for the broadcast communication case, Extensive sim ulation experiments demonstrate that the algorithm imposes lower commu nication overheads than previous causal ordering algorithms, The algor ithm can be employed in a variety of distributed computing environment s, Its energy efficiency and low bandwidth requirement make it especia lly suitable for mobile computing systems, We show how to employ the a lgorithm for causally ordered multicasting of messages in mobile compu ting environments. (C) 1997 Academic Press.