Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Fault Tolerance In Networks Of Bounded Degree, Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal
Fault Tolerance In Networks Of Bounded Degree, Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal
All HMC Faculty Publications and Research
Achieving processor cooperation in the presence of faults is a major problem in distributed systems. Popular paradigms such as Byzantine agreement have been studied principally in the context of a complete network. Indeed, Dolev [J. Algorithms, 3 (1982), pp. 14–30] and Hadzilacos [Issues of Fault Tolerance in Concurrent Computations, Ph.D. thesis, Harvard University, Cambridge, MA, 1984] have shown that Ω(t) connectivity is necessary if the requirement is that all nonfaulty processors decide unanimously, where t is the number of faults to be tolerated. We believe that in forseeable technologies the number of faults will grow with the size of the …
Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger
Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger
All HMC Faculty Publications and Research
A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n1 + 1/k ( log n )1 - 1/k ).