HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

An Efficient Causal Ordering Algorithm for Mobile Computing Environments

Ravi Prakash 1 Michel Raynal 2 Mukesh Singhal 1
2 ADP - Distributed Algorithms and Protocols
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
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), should 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 or communication topology. As computation proceeds, it acquires knowledge of the logical communication topology and is capable of handling dynamically changing multicast communication groups. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Its energy efficiency and low bandwidth requirement make it suitable for mobile computing systems. We present a strategy that employs the algorithm for causally ordered multicasting of messages in mobile computing environments.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:17:25 PM
Last modification on : Friday, February 4, 2022 - 3:24:59 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:22:03 PM


  • HAL Id : inria-00074011, version 1


Ravi Prakash, Michel Raynal, Mukesh Singhal. An Efficient Causal Ordering Algorithm for Mobile Computing Environments. [Research Report] RR-2680, INRIA. 1995. ⟨inria-00074011⟩



Record views


Files downloads