Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Using Golomb Rulers for Optimal Recovery Schemes in Fault Tolerant Distributed Computing
Blekinge Institute of Technology.
Blekinge Institute of Technology.
Blekinge Institute of Technology.
2003 (English)In: Proceedings International Parallel and Distributed Processing Symposium, IEEE, 2003Conference paper, Published paper (Refereed)
Abstract [en]

Clusters and distributed systems offer fault tolerance and high performance through load sharing. When all computers are up and running, we would like the load to be evenly distributed among the computers. When one or more computers break down the load on these computers must be redistributed to other computers in the cluster. The redistribution is determined by the recovery scheme. The recovery scheme should keep the load as evenly distributed as possible even when the most unfavorable combinations of computers break down, i.e. we want to optimize the worst-case behavior. In this paper we define recovery schemes, which are optimal for a number of important cases. We also show that the problem of finding optimal recovery schemes corresponds to the mathematical problem called Golomb rulers. These provide optimal recovery schemes for up to 373 computers in the cluster.

Place, publisher, year, edition, pages
IEEE, 2003.
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:mau:diva-39009DOI: 10.1109/IPDPS.2003.1213390ISBN: 0-7695-1926-1 (print)OAI: oai:DiVA.org:mau-39009DiVA, id: diva2:1515373
Conference
International Parallel and Distributed Processing Symposium; 22-26 April 2003; Nice, France
Available from: 2021-01-08 Created: 2021-01-08 Last updated: 2021-04-27Bibliographically approved
In thesis
1. Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing
Open this publication in new window or tab >>Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of two parts: performance bounds for scheduling algorithms for parallel programs in multiprocessor systems, and recovery schemes for fault tolerant distributed systems when one or more computers go down. In the first part we deliver tight bounds on the ratio for the minimal completion time of a parallel program executed in a parallel system in two scenarios. Scenario one, the ratio for minimal completion time when processes can be reallocated compared to when they cannot be reallocated to other processors during their execution time. Scenario two, when a schedule is preemptive, the ratio for the minimal completion time when we use two different numbers of preemptions. The second part discusses the problem of redistribution of the load among running computers in a parallel system. The goal is to find a redistribution scheme that maintains high performance even when one or more computers go down. Here we deliver four different redistribution algorithms. In both parts we use theoretical techniques that lead to explicit worst-case programs and scenarios. The correctness is based on mathematical proofs.

Place, publisher, year, edition, pages
Blekinge Institute of Technology, 2007
Series
Blekinge Institute of Technology Doctoral Dissertation Series, ISSN 1653-2090
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:mau:diva-7778 (URN)8614 (Local ID)978-91-7295-126-6 (ISBN)8614 (Archive number)8614 (OAI)
Available from: 2020-02-28 Created: 2020-02-28 Last updated: 2021-01-08Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf