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)

PDF (Adobe PDF (1.8MB))
See Usage Policy.

See Usage Policy.


Use this Persistent URL to link to this item:


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 Report ItemBook Chapter
Riedel, Marc D.0000-0002-3318-346X
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:1998.ETR022
Persistent URL:
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
Deposited By: Imported from CaltechPARADISE
Deposited On:03 Sep 2002
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page