A Latency Optimal Superstabilizing Mutual Exclusion Protocol in Unidirectional Rings

• Published in: Journal of parallel and distributed computing 2002-05, Vol.62 (5), p.865-884
• Main Authors: Katayama, Yoshiaki, Ueda, Eiichiro, Fujiwara, Hideo, Masuzawa, Toshimitsu
• Format: Article
• Language: English
• Subjects: mutual exclusion; ring network; self-stabilization; superstabilization
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1006/jpdc.2001.1826

A self-stabilizing protocol is a protocol that achieves its intended behavior regardless of the initial configuration. Thus, a self-stabilizing protocol is resilient to any number and any type of transient faults. A self-stabilizing protocol is called a superstabilizing protocol if it can recover from any “almost legitimate” configuration while satisfying a certain safety property during the recovery. Superstabilizing protocols are attractive since the number of processes that experience transient faults at the same time is small in most cases, and the resultant configuration is almost legitimate. Herman [Distrib. Comput. 13(1) (2002), 1–17] investigates superstabilizing mutual exclusion protocols in unidirectional rings. Herman considers, as the almost legitimate configuration, any configuration that results from a transient fault of a single process, and proposes the following safety property that should be satisfied during the recovery: no two processes simultaneously have privileges with the single exception of a temporary spurious privilege that the faulty process has. Herman adopts the process-register model, and shows an impossibility result: there exists no 1-latent protocol using fewer than 2n registers, where n is the number of processes in the ring. Herman also presents an n-latent protocol using n registers and a 1-latent protocol using 2n registers. In this paper, we further consider the latency of superstabilizing mutual exclusion protocols on unidirectional rings. On the shared variable model, we show that there exists no ⌊n/2⌋-latent protocol, and present a (⌈n/2⌉+1)-latent protocol. The proposed protocol is latency-optimal for the case that n is even.