Affordable Access

Publisher Website

An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments

Journal of Parallel and Distributed Computing
Publication Date
DOI: 10.1006/jpdc.1996.1300
  • Communication
  • Computer Science
  • Mathematics


Abstract Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information 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 significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

Performance analysis of adaptive caching algorithm...

on Information Sciences Jan 01, 1996

A note on the correctness of the causal ordering a...

on Artificial Intelligence Jan 01, 2008

Distributed computing in mobile environments

on Computers & Graphics Jan 01, 1996

Real-time broadcast algorithm for mobile computing

on Journal of Systems and Softwar... Jan 01, 2004
More articles like this..