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

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

Postscript
See Usage Policy. 498kB 
Use this Persistent URL to link to this item: https://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 faulttolerant balancer. We substitute a faulttolerant 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 kfaulttolerant counting network with depth O(k log to the power of 2 n). The second approach is to append a correction network, built with faulttolerant 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: 
 
ORCID: 
 
Group:  Parallel and Distributed Systems Group  
Record Number:  CaltechPARADISE:1998.ETR022  
Persistent URL:  https://resolver.caltech.edu/CaltechPARADISE:1998.ETR022  
Usage Policy:  You are granted permission for individual, educational, research and noncommercial 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:  22 Nov 2019 09:58 
Repository Staff Only: item control page