A multiple random walks based self-stabilizing k-exclusion algorithm in ad hoc networks

Abstract

In this paper, we present a solution to a resource allocation problem in a mobile ad hoc environment: the k-exclusion problem where k nodes are allowed to use a shared resource. We use a k tokens based circulation algorithm. Each token circulates continuously through the network according to a random walk policy. A node can enter the critical section if it owns one of the k tokens. The algorithm is decentralised – no node needs to be distinguished – adaptive to dynamical topology changes and self-stabilizing under a flexible mobility constraint.

Keywords:

• self-stabilization
• random walk
• ad hoc network
• distributed algorithm

Notes

^1. [email protected]

^2. [email protected]

^3. [email protected]

Additional information

Notes on contributors

Thibault Bernard

1. 1. [email protected]

Olivier Flauzac

2. 2. [email protected]

Florent Nolot

3. 3. [email protected]