Riedel, Marc D. and Bruck, Jehoshua (1998) Tolerating Faults in Counting Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:1998.ETR022
PDF (Adobe PDF (1.8MB))
See Usage Policy.
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:1998.ETR022
Counting networks were proposed by Aspnes, Herlihy and Shavit  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 . 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)|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||03 Sep 2002|
|Last Modified:||26 Dec 2012 13:52|
Repository Staff Only: item control page