A distributed mutual exclusion algorithm for mobile ad-hoc networks

Abstract

A distributed mutual exclusion algorithm based on token exchange and well suited for mobile ad-hoc networks is presented along with a simulation study. The algorithm is based on a dynamic logical ring and combines the best from two families of token based algorithms (i.e., token-asking and circulating token). In this way, the number of messages exchanged per critical section (CS) access (the main performance index for such algorithms) tends to optimal values under a heavy request load (i.e., two application messages for each CS access). We present a simulation study that (i) confirms this optimality and (ii) shows that, in a mobile ad-hoc network, an effective reduction in the number of hops per application message can be achieved by using a specific policy to build the logical ring on-the-fly.