The Worst-Case Stabilization Time of a Self-Stabilizing Algorithm under the Weakly Fair Daemon Model

The Worst-Case Stabilization Time of a Self-Stabilizing Algorithm under the Weakly Fair Daemon Model

Tetz C. Huang (Yuan-Ze University, Taiwan), Ji-Cherng Lin (Yuan-Ze University, Taiwan), Chih-Yuan Chen (Nanya Institute of Technology, Taiwan) and Cheng-Pin Wang (Yuan-Ze University, Taiwan)
Copyright: © 2010 |Pages: 8
DOI: 10.4018/jalr.2010070105
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this paper, the result of any self-stabilizing algorithm under the weakly fair daemon model (for a particular problem) that is not self-stabilizing under the non-fair central daemon model is obtained. Also, if any safe configuration under the weakly fair daemon model is also a safe configuration under the non-fair central daemon model, the worst-case stabilization time, measured in steps, is infinity. The implication of this new finding is that any problem, the existence of self-stabilizing algorithms for the weakly fair daemon model only, is unsatisfactory, that is of significance to pursue self-stabilizing algorithms for the non-fair central daemon model.
Article Preview

Introduction

A distributed system consists of a set of loosely connected processors that do not share a global memory. It is usually modeled by a connected simple undirected graph, with each noderepresenting a processor in the system and each edge representing the link connecting processors x and y. In any distributed system considered in this paper, each processor has a set of shared registers (registers for short). For each registerin a processor x, only x can write values into it and only x and its neighbors can read values of it. Each processor is equipped with a local algorithm that consists of one or more rules of the form:

condition partaction part.

The condition part (or guard) is a Boolean expression of registers of the processor and its neighbors, and the action part is an assignment of values to some registers of the processor. If the condition part of one or more rules in a processor is evaluated as true, we say that the processor is privileged to execute the action part of any of these rules (or privileged to make a move). The local algorithms of all the processors in a distributed system constitute a distributed algorithm. The local state of a processor is specified by the values of all its shared registers. The local states of all the processors in the system constitute a global configuration (configuration for short) of the system.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 7: 2 Issues (2017)
Volume 6: 2 Issues (2016)
Volume 5: 1 Issue (2015)
Volume 4: 1 Issue (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing