Fault tolerant mutual and k-mutual exclusion algorithms for single-hop mobile ad hoc networks. (25th May 2006)

• Record Type: Journal Article
• Authors: Mellier, Romain; Myoupo, Jean-Frederic
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 1:Number 3(2006)
• Page Start: 156
• Page End: 166
• Publication Date: 2006-05-25
• Subjects: mutual exclusion -- k-mutual exclusion -- ad hoc networks -- mobile networks -- wireless networks -- fault tolerant algorithms; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

Abstract

Previous mutual exclusion (MUTEX for short) protocols for mobile ad hoc networks are based on the token circulation technique. They assume that the network is reliable to avoid starvation. Considering that the MUTEX issue is to share a communication channel, we have designed an average-case-analysis protocol for single-hop networks which is based on the fully distributed construction of a random binary tree. Contrarily to other papers, the stations are not identified and their number (n) is unknown. Assuming that time is slotted, our algorithm runs in approximately n/log 2 slots. The derived k-MUTEX protocol runs in n/log k slots.