Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Kontogiannis, Spyros
Pantziou, Grammati E.
Spirakis, Paul G.
Yung, Moti

dblp
dblp
dblp
dblp

Not MPG Author(s):

Pantziou, Grammati E.
Spirakis, Paul G.
Yung, Moti

BibTeX cite key*:

Kontogiannis2000

Title

Title*:

Robust Parallel Computations through Randomization


KPSY-TOCS2000.pdf.gz (342.51 KB)

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://link.springer-ny.com/link/service/journals/00224/

Download URL
for the article:

http://www.mpi-sb.mpg.de/~spyros/papers/KPSY-TOCS2000.pdf.gz

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York, USA

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

33

Number:

5/6

Publishing Date:

November 2000

Pages*:

427-464

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Kontogiannis2000,
AUTHOR = {Kontogiannis, Spyros and Pantziou, Grammati E. and Spirakis, Paul G. and Yung, Moti},
TITLE = {Robust Parallel Computations through Randomization},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {5/6},
VOLUME = {33},
PAGES = {427--464},
ADDRESS = {New York, USA},
MONTH = {November},
ISBN = {1432-4350},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Spyros Kontogiannis
Created
03/02/2001 11:31:33 AM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Uwe Brahm
Anja Becker
Anja Becker
Edit Dates
09.06.2004 16:40:19
26.08.2003 15:06:36
05/02/2001 12:14:48 PM
20.03.2001 17:14:12
02/03/2001 11:31:34
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
KPSY-TOCS2000.pdf.gz