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 contribution

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 (US)
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 - Nov 26 2014
Event16th IEEE International Conference on Cluster Computing, CLUSTER 2014 - Madrid, Spain
Duration: Sep 22 2014Sep 26 2014

Publication series

Name2014 IEEE International Conference on Cluster Computing, CLUSTER 2014

Other

Other16th IEEE International Conference on Cluster Computing, CLUSTER 2014
CountrySpain
CityMadrid
Period9/22/149/26/14

Keywords

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

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software

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