A self-stabilizing token-based K-out-of-L exclusion algorithm

Document Type

Article

Publication Date

8-12-2003

Publication Title

Concurrency and Computation: Practice and Experience

Volume

15

Issue

2018-11-12

First page number:

1069

Last page number:

1091

Abstract

In this paper, we present the first self‐stabilizing solution to the k‐out‐of‐ℓ exclusion problem on a ring. The k‐out‐of‐ℓ exclusion problem is a generalization of the well‐known mutual exclusion problem—there are ℓ units of the shared resources, any process can request k $(1 \leq k \leq \ell)$ units of the shared resources, and no resource unit can be allocated to more than one process at one time. The space requirement of the proposed algorithm is independent of ℓ for all processors except a special processor, called Root. The stabilization time is only 5n, where n is the size of the ring. Copyright © 2003 John Wiley & Sons, Ltd.

Keywords

Fault-tolerance, k-out-of-ℓ exclusion, ℓ-exclusion, Mutual exclusion, Self-stabilization

Language

eng

UNLV article access

Find in your library

Share

COinS