Dynamic-fault-prone BSP

dc.contributor.author	Κοντογιάννης, Σπύρος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.contributor.author	Yung, Moti	en
dc.date.accessioned	2015-05-28T18:32:10Z
dc.date.available	2015-05-28T18:32:10Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11415
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://dl.acm.org/citation.cfm?id=277666	en
dc.subject	επεξεργαστές
dc.subject	δυναμική επιρρεπούς σφάλματος
dc.subject	δικτυο
dc.subject	μηχανές
dc.subject	processors
dc.subject	Dynamic-fault-prone
dc.subject	Network
dc.subject	machines
dc.title	Dynamic-fault-prone BSP	en
heal.type	conferenceItem
heal.secondaryTitle	a paradigm for robust computations in changing environments	en
heal.classification	Επιστήμες
heal.classification	Πληροφορική
heal.classification	Science
heal.classification	Computer science
heal.classificationURI	N/A-Επιστήμες
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	http://skos.um.es/unescothes/C03532
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.identifier.secondary	DOI: 10.1145/277651.277666
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1998
heal.bibliographicCitation	Kontogiannis, S., Pantziou, G., Spirakis, P. and Yung, M. (1998) Dynamic-fault-prone BSP: a paradigm for robust computations in changing environments. Proceedings of the 10th ACM Symp. on Parallel Algorithms and Architectures - SPAA’98. pp.37-46. New York: ACM Press	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-fauhprone BSP machines. The fault occurrences are fail-stop and fully dynamic, i.e., they are ahowed 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 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 a BACKTRACKING process to robustly stored instances of the computation). It adopts an adaptive balancing scheme of the work load among the currently live processors of the BSP machine. Moreover, the storage schemes adopted in this work achieve space optimality, which is very crucial in the BSP cost model, since space overhead is interpreted into communication overhead, when a fraction of the work load has to migrate to a currently live processor. Our strategy is efficient in the sense that, compared to an optimal off-line adversarial computation under the same sequence of fault occurrences, it achieves an 0 ((log n . loglog n)“) multiplicative factor times the optimal work (namely, this measure is in the sense of “competitive ratio” of on-line analysis). In addition, our scheme is modular, integrated, and considers many implementation points. We comment that, up 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 where an efficient Las Vegas simulation in this area is achieved.	en
heal.publisher	ACM Press	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 10th ACM Symp. on Parallel Algorithms and Architectures - SPAA’98	en
heal.conferenceItemType	full paper