Correctness of Self-Stabilizing Algorithms Under the Dolev Model When Adapted to Composite Atomicity Models

Correctness of Self-Stabilizing Algorithms Under the Dolev Model When Adapted to Composite Atomicity Models

Chih-Yuan Chen (Department of Computer Science and Information Engineering, Tao-yuan Innovation Institute of Technology, Chung-Li, Taiwan), Cheng-Pin Wang (General Education Center, Tzu Chi College of Technology, Hualien, Taiwan), Tetz C. Huang (Department of Computer Science and Engineering, Yuan-Ze University, Chung-Li, Taiwan) and Ji-Cherng Lin (Department of Computer Science and Engineering, Yuan-Ze University, Chung-Li, Taiwan)
Copyright: © 2012 |Pages: 16
DOI: 10.4018/ijalr.2012100102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

In this paper, the authors first clarify that it is not a trivial matter whether or not a self-stabilizing algorithm under the Dolev model, when adapted to a composite atomicity model, is also self-stabilizing. Then the authors employ a particular “simulation” approach to show that if a self-stabilizing algorithm under the Dolev model has one of two certain forms, then it is also self-stabilizing when adapted to one of the composite atomicity models, the fair daemon model. Since most existing self-stabilizing algorithms under the Dolev model have the above-mentioned forms, the authors’ results imply that they are all self-stabilizing when adapted to the fair daemon model.
Article Preview

1. Introduction

A distributed system consists of a set of loosely connected processors that do not share a global memory. It is usually modelled by a connected simple undirected graph with each node representing a processor in the system and each edge representing the link connecting processors and Each processor has one or more shared registers and possibly some non-shared local variables, the contents of which specify the local state of the processor. Local states of all processors in the system at a certain time constitute the global configuration (or, simply, configuration) of the system at that time. The main restriction of the distributed system is that each processor in the system can only access the data (i.e., read the shared data) of its neighbors. Since a distributed algorithm is an algorithm that works in a distributed system, it cannot violate this main restriction. In this paper, we adopt the point of view in Dolev et al. (1993). Thus, an atomic step is the “largest” step that is guaranteed to be executed uninterruptedly. A distributed algorithm uses composite atomicity if some atomic step contains (at least) a read operation and a write operation. A distributed algorithm uses read/write atomicity if each atomic step contains either a single read operation or a single write operation but not both.

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