A consensus-based ℓ-Exclusion algorithm for mobile ad hoc networks

Salahuddin Mohammad Masum; Mohammad Mostofa Akbar; Amin Ahsan Ali; Mohammad Ashiqur Rahman

doi:10.1016/j.adhoc.2009.03.002

Journal Article2010Cited by 7

A consensus-based ℓ-Exclusion algorithm for mobile ad hoc networks

Salahuddin Mohammad Masum, Mohammad Mostofa Akbar, Amin Ahsan Ali, Mohammad Ashiqur Rahman

Ad Hoc Networks

Elsevier, Vol. 8, Issue 1, pp. 30–45, ISBN: 1570-8705

DOI: 10.1016/j.adhoc.2009.03.002 URL

Keywords

Mutual exclusionComputer scienceMobile ad hoc networkCritical sectionWireless ad hoc networkNode (physics)Distributed computingAlgorithmNetwork topologyComputer networkGeneralizationTopology (electrical circuits)Consensus algorithmVehicular ad hoc networkDistributed algorithm

References

1.David B. Johnson, David A. Maltz. (2007). Dynamic Source Routing in Ad Hoc Wireless Networks. , 153–181[10.1007/978-0-585-29603-6_5]
2.Leslie Lamport. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558–565[10.1145/359545.359563]
3.Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva. (1998). A performance comparison of multi-hop wireless ad hoc network routing protocols. , 85–97[10.1145/288235.288256]
4.Edsger W. Dijkstra. (1974). Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11), 643–644[10.1145/361179.361202]
5.Young-Bae Ko, Nitin H. Vaidya. (1998). Location-aided routing (LAR) in mobile ad hoc networks. , 66–75[10.1145/288235.288252]
6.Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, Barry A. Woodward. (1998). A distance routing effect algorithm for mobility (DREAM). , 76–84[10.1145/288235.288254]
7.Elizabeth M. Royer, Charles E. Perkins. (1999). Multicast operation of the ad-hoc on-demand distance vector routing protocol. , 207–218[10.1145/313451.313538]
8.Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, Mikael Degermark. (1999). Scenario-based performance analysis of routing protocols for mobile ad-hoc networks. , 195–206[10.1145/313451.313535]
9.Tomasz Imieliński, Henry F. Korth. (1996). Mobile Computing.
10.E. W. Dijkstra. (1983). Solution of a problem in concurrent programming control. Communications of the ACM, 26(1), 21–22[10.1145/357980.357989]
11.Edsger W. Dijkstra, C.S. Scholten. (1980). Termination detection for diffusing computations. Information Processing Letters, 11(1), 1–4[10.1016/0020-0190(80)90021-6]
12.E. W. Dijkstra. (1965). Solution of a problem in concurrent programming control. Communications of the ACM, 8(9), 569[10.1145/365559.365617]
13.R. Bagrodia, R. Meyer, M. Takai, Yu-An Chen, Xiang Zeng, J. Martin, Ha Yoon Song. (1998). Parsec: a parallel simulation environment for complex systems. Computer, 31(10), 77–85[10.1109/2.722293]
14.Kerry Raymond. (1989). A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1), 61–77[10.1145/58564.59295]
15.E. Gafni, D. Bertsekas. (1981). Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. IRE Transactions on Communications Systems, 29(1), 11–18[10.1109/tcom.1981.1094876]
16.Divyakant Agrawal, Amr El Abbadi. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1), 1–20[10.1145/103727.103728]
17.Leslie Lamport. (1986). The mutual exclusion problem. Journal of the ACM, 33(2), 327–348[10.1145/5383.5385]
18.Jennifer E. Walter, Jennifer L. Welch, Nitin H. Vaidya. (2001). A Mutual Exclusion Algorithm for Ad Hoc Mobile Networks. Wireless Networks, 7(6), 585–600[10.1023/a:1012363200403]
19.Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin. (1979). Resource allocation with immunity to limited process failure. , 234–254[10.1109/sfcs.1979.37]
20.Robert Castañeda, Samir R. Das. (1999). Query localization techniques for on-demand routing protocols in ad hoc networks. , 186–194[10.1145/313451.313534]
21.M. Singhal. (1989). A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Transactions on Computers, 38(5), 651–662[10.1109/12.24268]
22.N. Malpani, Yu Chen, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 4(2), 154–165[10.1109/tmc.2005.25]
23.George Varghese. (1994). Self-stabilization by counter flushing. , 244–253[10.1145/197917.198102]
24.B.R. Badrinath, A. Acharya, T. Imielinski. (2002). Structuring distributed algorithms for mobile hosts. , 21–28[10.1109/icdcs.1994.302386]
25.Vassos Hadzilacos. (2001). A note on group mutual exclusion. , 100–106[10.1145/383962.383997]
26.R. Baldoni, A. Virgillito, R. Petrassi. (2003). A distributed mutual exclusion algorithm for mobile ad-hoc networks. , 539–544[10.1109/iscc.2002.1021727]
27.M. Benchaïba, A. Bouabdallah, N. Badache, M. Ahmed-Nacer. (2004). Distributed mutual exclusion algorithms in mobile ad hoc networks. ACM SIGOPS Operating Systems Review, 38(1), 74–89[10.1145/974104.974111]
28.Yu Chen, Jennifer L. Welch. (2002). Self-stabilizing mutual exclusion using tokens in mobile ad hoc networks. , 34–42[10.1145/570810.570815]
29.Yu Chen, Jennifer L. Welch. (2005). Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 65(9), 1072–1089[10.1016/j.jpdc.2005.03.009]
30.Y.-I. Chang, M. Singhal, M.T. Liu. (2002). A fault tolerant algorithm for distributed mutual exclusion. , 146–154[10.1109/reldis.1990.93960]
31.N. Malpani, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation on mobile ad hoc networks. , 4–13[10.1109/icnp.2001.992755]
32.Dhananjay M. Dhamdhere, Sandeep S. Kulkarni. (1994). A token based k-resilient mutual exclusion algorithm for distributed systems. Information Processing Letters, 50(3), 151–157[10.1016/0020-0190(94)00019-0]
33.Gérard Le Lann. (1977). Distributed Systems--Towards a Formal Approach. HAL (Le Centre pour la Communication Scientifique Directe), 155–160[link]
34.S.M. Masum, A.A. Ali. (2006). Distributed Allocation of Identical Resources in Mobile Ad Hoc Networks. , 1–10[10.1109/wiopt.2006.1666527]

Cited By

1.Ashish Khanna, Awadhesh Kumar Singh, Abhishek Swaroop. (2014). A Leader-Based k-Local Mutual Exclusion Algorithm Using Token for MANETs. , 30(5), 1303–1319
2.Ashish Khanna, Awadhesh Kumar Singh, Abhishek Swaroop. (2016). A Token-Based Solution to Group Local Mutual Exclusion Problem In Mobile Ad Hoc Networks. Arabian Journal for Science and Engineering, 41(12), 5181–5194[10.1007/s13369-016-2199-y]
3.Murali Parameswaran, Chittaranjan Hota. (2010). A novel permission-based reliable distributed mutual exclusion algorithm for MANETs. , 38, 1–6[10.1109/wocn.2010.5587356]
4.Anchal, Poonam Saini, C. Rama Krishna. (2014). An efficient permission-cum-cluster based distributed mutual exclusion algorithm for mobile adhoc networks. , 2, 141–146[10.1109/pdgc.2014.7030731]
5.Tahar Allaoui, Mohamed Yagoubi. (2015). A FAULT TOLERANT ALGORITHME FOR MULTIPLE RESOURCES SHARING IN DISTRIBUTED SYSTEMS.
6.Mehmet Hakan Karaata, Rachid Hadid. (2016). A Stabilizing Optimal <i>ℓ</i>-Exclusion Algorithm. Journal of Circuits Systems and Computers, 25(08), 1650098[10.1142/s0218126616500985]
7.Rachid Hadid, Mehmet Hakan Karaata. (2014). A stabilizing l-exclusion algorithm in arbitrary rooted networks. Journal of Engineering Research, 2(1), 94–121[10.1016/s2307-1877(25)00973-3]

← All publications

References

1.David B. Johnson, David A. Maltz. (2007). Dynamic Source Routing in Ad Hoc Wireless Networks. , 153–181[10.1007/978-0-585-29603-6_5]

2.Leslie Lamport. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558–565[10.1145/359545.359563]

3.Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva. (1998). A performance comparison of multi-hop wireless ad hoc network routing protocols. , 85–97[10.1145/288235.288256]

4.Edsger W. Dijkstra. (1974). Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11), 643–644[10.1145/361179.361202]

5.Young-Bae Ko, Nitin H. Vaidya. (1998). Location-aided routing (LAR) in mobile ad hoc networks. , 66–75[10.1145/288235.288252]

6.Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, Barry A. Woodward. (1998). A distance routing effect algorithm for mobility (DREAM). , 76–84[10.1145/288235.288254]

7.Elizabeth M. Royer, Charles E. Perkins. (1999). Multicast operation of the ad-hoc on-demand distance vector routing protocol. , 207–218[10.1145/313451.313538]

8.Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, Mikael Degermark. (1999). Scenario-based performance analysis of routing protocols for mobile ad-hoc networks. , 195–206[10.1145/313451.313535]

9.Tomasz Imieliński, Henry F. Korth. (1996). Mobile Computing.

10.E. W. Dijkstra. (1983). Solution of a problem in concurrent programming control. Communications of the ACM, 26(1), 21–22[10.1145/357980.357989]

11.Edsger W. Dijkstra, C.S. Scholten. (1980). Termination detection for diffusing computations. Information Processing Letters, 11(1), 1–4[10.1016/0020-0190(80)90021-6]

12.E. W. Dijkstra. (1965). Solution of a problem in concurrent programming control. Communications of the ACM, 8(9), 569[10.1145/365559.365617]

13.R. Bagrodia, R. Meyer, M. Takai, Yu-An Chen, Xiang Zeng, J. Martin, Ha Yoon Song. (1998). Parsec: a parallel simulation environment for complex systems. Computer, 31(10), 77–85[10.1109/2.722293]

14.Kerry Raymond. (1989). A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1), 61–77[10.1145/58564.59295]

15.E. Gafni, D. Bertsekas. (1981). Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. IRE Transactions on Communications Systems, 29(1), 11–18[10.1109/tcom.1981.1094876]

16.Divyakant Agrawal, Amr El Abbadi. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1), 1–20[10.1145/103727.103728]

17.Leslie Lamport. (1986). The mutual exclusion problem. Journal of the ACM, 33(2), 327–348[10.1145/5383.5385]

18.Jennifer E. Walter, Jennifer L. Welch, Nitin H. Vaidya. (2001). A Mutual Exclusion Algorithm for Ad Hoc Mobile Networks. Wireless Networks, 7(6), 585–600[10.1023/a:1012363200403]

19.Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin. (1979). Resource allocation with immunity to limited process failure. , 234–254[10.1109/sfcs.1979.37]

20.Robert Castañeda, Samir R. Das. (1999). Query localization techniques for on-demand routing protocols in ad hoc networks. , 186–194[10.1145/313451.313534]

21.M. Singhal. (1989). A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Transactions on Computers, 38(5), 651–662[10.1109/12.24268]

22.N. Malpani, Yu Chen, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 4(2), 154–165[10.1109/tmc.2005.25]

23.George Varghese. (1994). Self-stabilization by counter flushing. , 244–253[10.1145/197917.198102]

24.B.R. Badrinath, A. Acharya, T. Imielinski. (2002). Structuring distributed algorithms for mobile hosts. , 21–28[10.1109/icdcs.1994.302386]

25.Vassos Hadzilacos. (2001). A note on group mutual exclusion. , 100–106[10.1145/383962.383997]

26.R. Baldoni, A. Virgillito, R. Petrassi. (2003). A distributed mutual exclusion algorithm for mobile ad-hoc networks. , 539–544[10.1109/iscc.2002.1021727]

27.M. Benchaïba, A. Bouabdallah, N. Badache, M. Ahmed-Nacer. (2004). Distributed mutual exclusion algorithms in mobile ad hoc networks. ACM SIGOPS Operating Systems Review, 38(1), 74–89[10.1145/974104.974111]

28.Yu Chen, Jennifer L. Welch. (2002). Self-stabilizing mutual exclusion using tokens in mobile ad hoc networks. , 34–42[10.1145/570810.570815]

29.Yu Chen, Jennifer L. Welch. (2005). Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks. Journal of Parallel and Distributed Computing, 65(9), 1072–1089[10.1016/j.jpdc.2005.03.009]

30.Y.-I. Chang, M. Singhal, M.T. Liu. (2002). A fault tolerant algorithm for distributed mutual exclusion. , 146–154[10.1109/reldis.1990.93960]

31.N. Malpani, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation on mobile ad hoc networks. , 4–13[10.1109/icnp.2001.992755]

32.Dhananjay M. Dhamdhere, Sandeep S. Kulkarni. (1994). A token based k-resilient mutual exclusion algorithm for distributed systems. Information Processing Letters, 50(3), 151–157[10.1016/0020-0190(94)00019-0]

33.Gérard Le Lann. (1977). Distributed Systems--Towards a Formal Approach. HAL (Le Centre pour la Communication Scientifique Directe), 155–160[link]

34.S.M. Masum, A.A. Ali. (2006). Distributed Allocation of Identical Resources in Mobile Ad Hoc Networks. , 1–10[10.1109/wiopt.2006.1666527]

Cited By

1.Ashish Khanna, Awadhesh Kumar Singh, Abhishek Swaroop. (2014). A Leader-Based k-Local Mutual Exclusion Algorithm Using Token for MANETs. , 30(5), 1303–1319

2.Ashish Khanna, Awadhesh Kumar Singh, Abhishek Swaroop. (2016). A Token-Based Solution to Group Local Mutual Exclusion Problem In Mobile Ad Hoc Networks. Arabian Journal for Science and Engineering, 41(12), 5181–5194[10.1007/s13369-016-2199-y]

3.Murali Parameswaran, Chittaranjan Hota. (2010). A novel permission-based reliable distributed mutual exclusion algorithm for MANETs. , 38, 1–6[10.1109/wocn.2010.5587356]

4.Anchal, Poonam Saini, C. Rama Krishna. (2014). An efficient permission-cum-cluster based distributed mutual exclusion algorithm for mobile adhoc networks. , 2, 141–146[10.1109/pdgc.2014.7030731]

5.Tahar Allaoui, Mohamed Yagoubi. (2015). A FAULT TOLERANT ALGORITHME FOR MULTIPLE RESOURCES SHARING IN DISTRIBUTED SYSTEMS.

6.Mehmet Hakan Karaata, Rachid Hadid. (2016). A Stabilizing Optimal <i>ℓ</i>-Exclusion Algorithm. Journal of Circuits Systems and Computers, 25(08), 1650098[10.1142/s0218126616500985]

7.Rachid Hadid, Mehmet Hakan Karaata. (2014). A stabilizing l-exclusion algorithm in arbitrary rooted networks. Journal of Engineering Research, 2(1), 94–121[10.1016/s2307-1877(25)00973-3]