A Dual-Token-Based Fault Tolerant Mutual Exclusion Algorithm for MANETs
Most existing mutual exclusion algorithms for mobile ad hoc networks (MANETs) adopt a token-based approach. In traditional wired networks, timeout-based mechanisms are commonly used to detect token losses. However, in MANETs, it is difficult to set a prop
- PDF / 295,340 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 70 Downloads / 188 Views
Department of Computing, The Hong Kong Polytechnic University, Kowloon, Hong Kong {cswgwu,csjcao}@comp.polyu.edu.hk 2 IRISA, Campus de Beaulieu, Université de Rennes1, 35042 Rennes Cedex, France [email protected]
Abstract. Most existing mutual exclusion algorithms for mobile ad hoc networks (MANETs) adopt a token-based approach. In traditional wired networks, timeout-based mechanisms are commonly used to detect token losses. However, in MANETs, it is difficult to set a proper timeout value due to the network dynamics. In this paper, we propose a dual-token-based mutual exclusion algorithm, which can tolerate token losses without using timeout. Two tokens are concurrently circulated in the system to monitor each other by using sequence numbers. If one token is lost, the other token can detect the loss and regenerate a new token. Simulations have been carried out to evaluate the effectiveness and performance of the proposed algorithm in comparison with the timeout-based approach. The results show that the timeout-based algorithm may falsely claim the loss of a token, thus cannot guarantee the correctness of mutual exclusion algorithms. On the contrary, our proposed algorithm can avoid false detection of token losses and satisfy all the correctness requirements of mutual exclusion, though it costs a bit more messages and longer time. Keywords: Mutual Exclusion, Distributed Algorithm, MANET, Mobile Computing, Token Loss.
1 Introduction Mutual exclusion (MUTEX) is a fundamental problem in distributed systems, where a group of hosts intermittently require entering the Critical Section (CS) in order to exclusively perform some critical operations, e.g. accessing the shared resource. A solution to the MUTEX problem must satisfy the following three correctness properties: • Mutual Exclusion (safety): At most one host can be in the CS at any time; • Deadlock Free (liveness): If any host is waiting for the CS, then in a finite time some host enters the CS; • Starvation Free (Fairness): If a host is waiting for the CS, then in a finite time the host enters the CS. H. Zhang et al. (Eds.): MSN 2007, LNCS 4864, pp. 572–583, 2007. © Springer-Verlag Berlin Heidelberg 2007
A Dual-Token-Based Fault Tolerant Mutual Exclusion Algorithm for MANETs
573
Many MUTEX algorithms have been proposed for traditional distributed systems [19], which can be categorized into two classes: token-based algorithms and permission-based algorithms. In token-based algorithms, a token is passed among all the hosts. A host is allowed to enter the CS only if it possesses the token. In a permission-based algorithm, the host requesting for the CS must first obtain the permissions from other hosts by exchanging messages. With the emergence of mobile networks, new challenges are introduced in solving the MUTEX problem [6][17]. In this paper, we focus on mobile ad hoc networks (MANETs), which have become the focus of research in recent years. MANETs have fundamentally different properties from traditional wired networks in the aspects of communication, mobilit
Data Loading...
