Distributed token circulation in mobile ad hoc networks

Navneet Malpani, Yu Chen, Nitin H. Vaidya, Jennifer L. Welch

Research output: Contribution to journalArticlepeer-review


This paper presents several distributed algorithms that cause a token to continually circulate through all the nodes of a mobile ad hoc network. An important application of such algorithms is to ensure total order of message delivery in a group communication service. Some of the proposed algorithms are aware of, and adapt to changes in, the ad hoc network topology. When using a token circulation algorithm, a round is said to complete when every node has been visited at least once. Criteria for comparing the algorithms include the average time required to complete a round, number of bytes sent per round, and number of nodes visited per round. Comparison between the proposed algorithms is performed using simulation results obtained from a detailed simulation model (with ns-2 simulator). We also give a rigorous worst-case analysis of the proposed LR algorithm, which gives the best overall performance in the simulation.

Original languageEnglish (US)
Pages (from-to)154-165
Number of pages12
JournalIEEE Transactions on Mobile Computing
Issue number2
StatePublished - Mar 2005


  • Distributed system
  • Mobile ad hoc networks
  • Token circulation

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Distributed token circulation in mobile ad hoc networks'. Together they form a unique fingerprint.

Cite this