Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 518149.0, MPI für Informatik / Algorithms and Complexity Group
Robust Parallel Computations through Randomization
Authors:Kontogiannis, Spyros; Pantziou, Grammati E.; Spirakis, Paul G.; Yung, Moti
Date of Publication (YYYY-MM-DD):2000
Title of Journal:Theory of Computing Systems
Issue / Number:5/6
Start Page:427
End Page:464
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:In this paper we present an efficient general simulation strategy
for computations designed for fully operational BSP machines of
n ideal processors, on n-processor dynamic-fault-prone BSP
machines. The fault occurrences are fail-stop and fully dynamic,
i.e., they are allowed to happen on-line at any point of the
computation, subject to the constraint that the total number of
faulty processors may never exceed a known fraction. The
computational paradigm can be exploited for robust computations
over virtual parallel settings with a volatile underlying
infrastructure, such as a NETWORK OF WORKSTATIONS (where
workstations may be taken out of the virtual parallel machine
by their owner).

Our simulation strategy is Las Vegas (i.e., it may never fail,
due to backtracking operations to robustly stored instances of
the computation, in case of locally unrecoverable situations).
It adopts an adaptive balancing scheme of the workload among the
currently live processors of the BSP machine. Our strategy is
efficient in the sense that, compared with an optimal off-line
adversarial computation under the same sequence of fault
occurrences, it achieves an O(log n loglog n)^2 multiplicative
factor times the optimal work (namely, this measure is in the
sense of the "competitive ratio" of on-line analysis). In
addition, our scheme is modular, integrated, and considers many
implementation points.

We comment that, to our knowledge, no previous work on robust
parallel com-putations has considered fully dynamic faults in
the BSP model, or in general distributed memory systems.
Furthermore, this is the first time an efficient Las Vegas
simulation in this area is achieved.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Full Text:
You have privileges to view the following file(s):
KPSY-TOCS2000.pdf.gz  [342,00 Kb] [Comment:file from upload service]  
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.