Scalable replay with partial-order dependencies for message-logging fault tolerance

Jonathan Lifflander, Esteban Meneses, Harshitha Menon, Phil Miller, Sriram Krishnamoorthy, Laxmikant V. Kale

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

Deterministic replay of a parallel application is commonly used for discovering bugs or to recover from a hard fault with message-logging fault tolerance. For message passing programs, a major source of overhead during forward execution is recording the order in which messages are sent and received. During replay, this ordering must be used to deterministically reproduce the execution. Previous work in replay algorithms often makes minimal assumptions about the programming model and application to maintain generality. However, in many applications, only a partial order must be recorded due to determinism intrinsic in the program, ordering constraints imposed by the execution model, and events that are commutative (their relative execution order during replay does not need to be reproduced exactly). In this paper, we present a novel algebraic framework for reasoning about the minimum dependencies required to represent the partial order for different orderings and interleavings. By exploiting this framework, we improve on an existing scalable message-logging fault tolerance scheme that uses a total order. The improved scheme scales to 131,072 cores on an IBM BlueGene/P with up to 2× lower overhead.

Original languageEnglish
Title of host publication2014 IEEE International Conference on Cluster Computing, CLUSTER 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages19-28
Number of pages10
ISBN (Electronic)9781479955480
DOIs
StatePublished - 26 Nov 2014
Externally publishedYes
Event16th IEEE International Conference on Cluster Computing, CLUSTER 2014 - Madrid, Spain
Duration: 22 Sep 201426 Sep 2014

Publication series

Name2014 IEEE International Conference on Cluster Computing, CLUSTER 2014

Conference

Conference16th IEEE International Conference on Cluster Computing, CLUSTER 2014
Country/TerritorySpain
CityMadrid
Period22/09/1426/09/14

Keywords

  • determinism
  • execution model
  • fault tolerance
  • message logging
  • partial-order dependencies
  • replay

Fingerprint

Dive into the research topics of 'Scalable replay with partial-order dependencies for message-logging fault tolerance'. Together they form a unique fingerprint.

Cite this