Distributed mutual exclusion algorithms in mobile ad hoc networks: an overview

ABSTRACT

The problem of mutual exclusion has been extensively studied in distributed systems. The proposed solutions can be mainly classified in consensus based and token based protocols. Some of the proposed solutions consider the physical topology of the networks and try to provide optimal message exchange and minimal synchronisation delays. Others, impose a logical structure on the network like a ring or a tree. Recently, the mutual exclusion problem received an interest for mobile ad hoc networks. These networks are known as a challenging domain. To our knowledge, few algorithms have been proposed in the literature and all of them are token based approach. In this paper, we review the distributed mutual exclusion algorithms developed for mobile environments and principally for ad hoc networks and discuss some issues.

REFERENCES

• 1: Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
• 2: A. A. Albert And R. Sandier, "An introduction to finite projective planes," Holt, Rinehart and Winston, New York 1968.
• 3: B. R. Badrinath, A. Acharya, and T. Imielinski, "Structuring distributed algorithms for mobile hosts," Proc. of the 14th Intern. Conf. on Distr. Comp., 1994, pp. 21--28.
• 4: R. Baldoni and A. Virgilito, "A Token-based Mutual Exclusion Algorithm for Mobile Ad hoc Networks," Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Via salaria 113, 00198 Roma, Italia, Technical Report 28-01.
• 5: Abdelmadjid Bouabdallah, On mutual exclusion in faulty distributed systems, ACM SIGOPS Operating Systems Review, v.28 n.1, p.80-87, Jan. 1994 [doi>10.1145/164853.164878]
• 6: A. Bouabdallah, J. C. König, "A distributed algorithm for the mutual exclusion problem," Parallel and Distributed Computing in engineering systems. Tzafestas et al. (Editeurs), Elsevier Science Publisher B.V., North-Holland (1992) 285--290.
• 7: A. Bouabdallah., J. C. König, M. B Yagoubi, "A fault-tolerant algorithm for the mutual exclusion in real-time distributed systems," Journal of computing and Information, Vol. 1 No. 1 (1994), pp. 438--454.
• 8: Peter J. Denning, Technical Correspondence, Communications of the ACM, v.26 n.2, p.146-149, Feb. 1983
• 9: Y. Chang, M. Singhal, and M. Liu, "A fault tolerant algorithm for distributed mutual exclusion", In Proc. of 9th IEEE Syrup. On Reliable Dist. Systems, pp. 146--154, 1990.
• 10: Y. Chen and J. Welch, "Self-stabilizing mutual exclusion using tokens in ad hoc networks," Technical Report 2002-4-2, Dept. of Computer Science, Texas A&M Univ., April 2002. url: <<u>http://www.cs.tamu.edu/people/ychen/Research/Paper/sstcSM lrv.pdf</u>
• 11: Dhananjay M. Dhamdhere , Sandeep S. Kulkarni, A token based k-resilient mutual exclusion algorithm for distributed systems, Information Processing Letters, v.50 n.3, p.151-157, May 9, 1994 [doi>10.1016/0020-0190(94)00019-0 ]
• 12: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 13: E. Gafni and D. Bertsekas, "Distributed algorithms for generating loop-free routes in networks with frequently changing topology," IEEE Transactions on Communications, C-29(1):11--18, 1981.
• 14: J. M. Helary , N. Plouzeau , M. Raynal, A distributed algorithm for mutual exclusion in an arbitrary network, The Computer Journal, v.31 n.4, p.289-295, August 1988
• 15: IEEE std. 802.11, "Wireless LAN media access control (MAC) and physical layer(PHY) specification," 1999.
• 16: D. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," In T. Imielinski and H. Korth editors, Mobile Computing. Kluwer Academic Publishers, Boston, 1994, pp. 153--181.
• 17: I. Katzela and M. Naghshineh, "Channel assignment schemes for cellular mobile telecommunication systems: A comprehensive survey", IEEE Personal Communications, June 1996 pp. 10--31.
• 18: L. Kleinrock and F. A. Tobari, "Packet switching in radio channels: Part I- Carrier sense multiple-access modes and their throughput-delay characteristics," IEEE Trans. Commun., Col. Com-23, No. 12, pp. 1417--1433, 1975.
• 19: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 20: G. Le Lann, "Distributed systems, towards a formal approach," IFIP Congress, Toronto, pp. 155--160, 1977.
• 21: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 22: N. Malpani, N. H. Vaidya, J. L. Welch, "Distributed token circulation on mobile ad hoc networks," Technical report, Intel Corporation 505 E. Huntland Dr. Suite 550, Austin TX 78752.
• 23: S. Mishra , P. K. Srimani, Fault-tolerant mutual exclusion algorithms, Journal of Systems and Software, v.11 n.2, p.111-129, Feb. 1990 [doi>10.1016/0164-1212(90)90056-R]
• 24: M. Mizuno, M. L. Neilsen and R. Rao, "A token based distributed mutual exclusion algorithm based on quorum agreements," 11th International Conference on Distributed Computing Systems, 20--24 may 1991, pp. 361--368.
• 25: M. Naimi and M. Trehel, "An improvement of the log n distributed algorithm for mutual exclusion," Proceedings of 7th IEEE International Conference on Distributed Computing Systems (1987), pp. 371--375.
• 26: M. L. Neilsen and M. Mizuno, " A DAG-based algorithm for distributed mutual exclusion," 11th International Conference on Distributed Computing Systems, 20--24 may, 1991, pp. 354--360.
• 27: S. Nesargi and R. Prakash, "MANETConf: Configuration of hosts in a mobile ad hoc network," In the Proceedings of IEEE INFOCOM '02, New York, June 2002.
• 28: V. Park and S. Corson, " Temporally-ordered routing algorithm (TORA) version 1 functional specification," corson-draft-ietf-manet.tora-spec-00.txt, IETF, Internet draft, 1997.
• 29: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 30: M. Raynal, Prime numbers as a tool to design distributed algorithms, Information Processing Letters, v.33 n.1, p.53-58, Oct. 1989 [doi>10.1016/0020-0190(89)90187-7 ]
• 31: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 32: G. Ricart and A. K. Agrawala, "Author response to 'on mutual exclusion in computer networks', by Carvalho and Roucairol," Communication of the ACM, vol. 26, No. 2, Feb. 1983, pp. 147--148.
• 33: E. M. Royer, T. Chai-Keong, "A review of current routing protocols for ad hoc mobile wireless networks," IEEE Personal Communications, Vol. 6, No. 2, pp. 46--55, April 1999.
• 34: Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987 [doi>10.1145/24068.28052]
• 35: Mukesh Singhal, A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems, IEEE Transactions on Computers, v.38 n.5, p.651-662, May 1989 [doi>10.1109/12.24268 ]
• 36: William Su , Sung-Ju Lee , Mario Gerla, Mobility prediction and routing in ad hoc wireless networks, International Journal of Network Management, v.11 n.1, p.3-30, January–February 2001 [doi>10.1002/nem.386 ]
• 37: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• 38: V. P. Team, "The network simulator-ns2," VINT Project Team, Available at <u>http://www.isi.edu/nsnam/ns/</u>, Nov. 2000.
• 39: George Varghese, Self-stabilization by counter flushing, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.244-253, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198102]
• 40: Jennifer Walter , Savita Kini, Mutual Exclusion on Multihop, Mobile Wireless Networks, Texas A & M University, College Station, TX, 1997
• 41: Jennifer E. Walter , Jennifer L. Welch , Nitin H. Vaidya, A mutual exclusion algorithm for ad hoc mobile networks, Wireless Networks, v.7 n.6, p.585-600, November 2001 [doi>10.1023/A:1012363200403 ]
• 42: Xiang Zeng , Rajive Bagrodia , Mario Gerla, GloMoSim: a library for parallel simulation of large-scale wireless networks, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.154-161, May 26-29, 1998, Banff, Alberta, Canada

INDEX TERMS

Keywords:
algorithm, critical section, mobile ad hoc network, mutual exclusion