Robust parallel computations through randomization

dc.contributor.author	Κοντογιάννης, Σπύρος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Yung, M.	en
dc.date.accessioned	2015-05-24T20:01:28Z
dc.date.available	2015-05-24T20:01:28Z
dc.date.issued	2015-05-24
dc.identifier.uri	http://hdl.handle.net/11400/11082
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/article/10.1007%2Fs002240010009	en
dc.subject	Παράλληλοι υπολογισμοί
dc.subject	τυχαιοποίηση
dc.subject	δίκτυο σταθμών εργασίας
dc.subject	Parallel Computations
dc.subject	Randomization
dc.subject	network of workstations
dc.title	Robust parallel computations through randomization	en
heal.type	journalArticle
heal.classification	Πληροφορική
heal.classification	Μαθηματικά
heal.classification	Computer science
heal.classification	Mathematics
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	N/A-Μαθηματικά
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.classificationURI	http://skos.um.es/unescothes/C02437
heal.identifier.secondary	DOI: 10.1007/s002240010009
heal.language	en
heal.access	free
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	2000-12
heal.bibliographicCitation	Kontogiannis, S., Pantziou, G., Spirakis, P. and Yung, M. (2000) Robust Parallel Computations through Randomization. Theory of Computing Systems. [Online] 33 (5-6). pp.427-464. Available from: http://link.springer.com [Accessed 24/05/2015]	en
heal.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 \cal O \left( (log n ⋅log log n) 2 \right) 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 computations 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.	en
heal.publisher	Springer-Verlag	en
heal.journalName	Theory of Computing Systems	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true