Efficient computations on fault-prone BSP machines

dc.contributor.author	Κοντογιάννης, Σπύρος	el
dc.contributor.author	Πάντζιου, Γραμματή Ε.	el
dc.contributor.author	Σπυράκης, Παύλος	el
dc.date.accessioned	2015-05-28T18:53:31Z
dc.date.available	2015-05-28T18:53:31Z
dc.date.issued	2015-05-28
dc.identifier.uri	http://hdl.handle.net/11400/11429
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=258501	en
dc.subject	αλγόριθμοι
dc.subject	μηχανές
dc.subject	επεξεργαστές
dc.subject	επικοινωνία
dc.subject	algorithms
dc.subject	machines
dc.subject	processors
dc.subject	communication
dc.title	Efficient computations on fault-prone BSP machines	en
heal.type	conferenceItem
heal.classification	Μηχανική
heal.classification	Μηχανική υπολογιστών
heal.classification	Mechanics
heal.classification	Computer engineering
heal.classificationURI	N/A-Μηχανική
heal.classificationURI	N/A-Μηχανική υπολογιστών
heal.classificationURI	http://skos.um.es/unescothes/C02449
heal.classificationURI	http://id.loc.gov/authorities/subjects/sh85029495
heal.identifier.secondary	DOI: 10.1145/258492.258501
heal.language	en
heal.access	campus
heal.recordProvider	Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	1997
heal.bibliographicCitation	Kontogiannis, S., Pantziou, G. and Spirakis, P. (1997) Efficient computations on fault-prone BSP machines. Proceedings of the 9th ACM Symp. on Parallel Algorithms and Architectures - SPAA’97. pp.84-93. New York: ACM Press	en
heal.abstract	In this paper general simulations of algorithms designed for fully operational BSP machines on BSP machines with fault y or unavailable processors, are deveioped. The fail-stop model is considered for the fault occurrences, that is, if a processor fails or becomes unavailable, it remains so until the end of the computation. The faults are random, in the sense that a processor may fail independently with probability at most a, where a is a constant. Two possible settings for fault occurrences are considered: the static case where the faults are static (the faulty or unavailable processors are already known at the beginning of the computation), and the dynamic case where the processors may become faulty or unavailable during the computation. In the case of static faults, a simulation of an n-processor fault-free BSP machine on a faulty n-processor BSP machine is presented with constant slowdown per local computation step and O(log n . max{ L, g }) slowdown per communication step, given that a preprocessing has been done that needs O(n/ log n max{L, g}) time (L and g are the parameters of the simulating BSP machine). In the case of dynamic faults, a simulation of an n-processor fault-free BSP machine on an cn log nprocessor faulty BSP machine is presented. No dynamic faults may occur during certain periods of the simulation. The simulations are randomized and Monte Carlo: they are guaranteed to be correct with high probability, and the time bounds always hold. To our knowledge, no previous work on the fault tolerance of the BSP model exists.	en
heal.publisher	ACM Press	en
heal.fullTextAvailability	true
heal.conferenceName	Proceedings of the 9th ACM Symp. on Parallel Algorithms and Architectures - SPAA’97	en
heal.conferenceItemType	full paper