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

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:

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.