Tolerating faults in synchronization networks

Sandeep N. Bhatt, Fan R.K. Chung, F. Thomson Leighton, Arnold L. Rosenberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

A synchronization network (SN) consists of processing elements (PEs) at the leaves of a complete binary tree, with routing switches at interior nodes. We study the problem of rendering an SN tolerant to PE failures, by adding queues to its edges. We obtain the following results. In the worst-case, an N-PE SN whose edges have queues of capacity O(log log N) can tolerate the failure of a positive fraction of its PEs, no matter how the failed PEs are distributed; furthermore, this capacity requirement cannot be lowered by more than a small constant factor. In the expected-case, with probability exceeding 1-N-Ω(1), an N-PE SN whose edges have queues of capacity O(log log log N) can tolerate the failure of a positive fraction of its PEs; we do not know if this capacity requirement can be lowered. We also present an algorithm which, given an SN with queues of capacity C, salvages a maximum number of fault-free PEs; the running time is a low-degree polynomial in N even when C is as large as log(N/log N).

Original languageEnglish
Title of host publicationParallel Processing
Subtitle of host publicationCONPAR 1992 ─ VAPP V - 2nd Joint International Conference on Vector and Parallel Processing, Proceedings
EditorsLuc Bouge, Michel Cosnard, Yves Robert, Denis Trystram
Pages1-12
Number of pages12
DOIs
StatePublished - 1992
Event2nd Joint International Conference on Vector and Parallel Processing, CONPAR 1992 - Lyon, France
Duration: 1 Sep 19924 Sep 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume634 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd Joint International Conference on Vector and Parallel Processing, CONPAR 1992
Country/TerritoryFrance
CityLyon
Period1/09/924/09/92

Fingerprint

Dive into the research topics of 'Tolerating faults in synchronization networks'. Together they form a unique fingerprint.

Cite this