CaltechAUTHORS
  A Caltech Library Service

Tolerating Faults in Counting Networks

Riedel, Marc D. and Bruck, Jehoshua (1998) Tolerating Faults in Counting Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1998.ETR022

[img]
Preview
PDF (Adobe PDF (1.8MB))
See Usage Policy.

1793Kb
[img]
Preview
Postscript
See Usage Policy.

486Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1998.ETR022

Abstract

Counting networks were proposed by Aspnes, Herlihy and Shavit [4] as a technique for solving multiprocessor coordination problems. We describe a method for tolerating an arbitrary number of faults in counting networks. In our fault model, the following errors can occur dynamically in the counting network data structure: 1) a balancer's state is spuriously altered, 2) a balancer's state can no longer be accessed. We propose two approaches for tolerating faults. The first is based on a construction for a fault-tolerant balancer. We substitute a fault-tolerant balancer for every balancer in a counting network. Thus, we transform a counting network with depth O(log to the power of 2 n); where n is the width, into a k-fault-tolerant counting network with depth O(k log to the power of 2 n). The second approach is to append a correction network, built with fault-tolerant balancers, to a counting network that may experience faults. We present a bound on the error in the output token distribution of counting networks with faulty balancers (a generalization of the error bound for sorting networks with faulty comparators presented by Yao & Yao [21]. Given a token distribution with a bounded error, the correction network produces a token distribution that is smooth, i.e., the number of tokens on each output wire differs by at most one (a weaker condition than the step property). In order to tolerate k faults, the correction network has depth O (k to the power of 2 log n) for a network of width n.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/etr022.psPublisherUNSPECIFIED
ORCID:
AuthorORCID
Riedel, Marc D.0000-0002-3318-346X
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1998.ETR022
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:1998.ETR022
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26052
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:03 Sep 2002
Last Modified:25 Feb 2014 21:59

Repository Staff Only: item control page