A self-correcting connected components algorithm

Piyush Sao; Oded Green; Chirag Jain; Richard Vuduc

doi:10.1145/2909428.2909435

A self-correcting connected components algorithm

Piyush Sao, Oded Green, Chirag Jain, Richard Vuduc

Discrete Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

We present a new fault-tolerant algorithm for the problem of computing the connected components of a graph. Our algorithm derives from a highly parallel but non-resilient algorithm, which is based on the technique of label propagation (LP). To make the LP algorithm resilient to transient soft faults, we apply an algorithmic design principle that we refer to as self-correction. Briefly, a self-correcting algorithm detects if it has reached an invalid state given that it was previously in a known valid state; and if so, restores itself back to a valid state assuming the availability of a selective guaranteed-reliable mode. Our self-correcting algorithm, FT-LP, has relatively small storage and computation overheads: in empirical tests on a variety of input graphs, we observe execution time overheads of 10-35% in FT-LP compared to LP even at high fault rates, with the computation overhead increasing gracefully as fault rates increase.

Original language	English
Title of host publication	FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale
Publisher	Association for Computing Machinery, Inc
Pages	9-16
Number of pages	8
ISBN (Electronic)	9781450343497
DOIs	https://doi.org/10.1145/2909428.2909435
State	Published - May 31 2016
Event	ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, FTXS 2016 - Kyoto, Japan Duration: May 31 2016 → …

Publication series

Name	FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale

Conference

Conference	ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, FTXS 2016
Country/Territory	Japan
City	Kyoto
Period	05/31/16 → …

Funding

We thank Srinivas Eswar and Aftab Patel for the help in revising this manuscript, including checking of the proofs. This work was supported in part by the U.S. Department of Energy (DOE), Office of Science, Advanced Scientific Computing Research X-Stack 1.0 under DE-FC02-10ER26006/DE-SC0004915. We also used resources of the National Energy Research Scientific Computing Center, which is supported by the DOE Office of Science under Contract No. DE-AC02-05CH11231. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of DOE.

Keywords

Fault-tolerance
Label propagation
Selective reliability
Self-stabilization
Transient soft faults

Access to Document

10.1145/2909428.2909435

Cite this

Sao, P., Green, O., Jain, C., & Vuduc, R. (2016). A self-correcting connected components algorithm. In FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale (pp. 9-16). (FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale). Association for Computing Machinery, Inc. https://doi.org/10.1145/2909428.2909435

@inproceedings{3aaac8e16fcc4d309225e7e44c3300eb,

title = "A self-correcting connected components algorithm",

abstract = "We present a new fault-tolerant algorithm for the problem of computing the connected components of a graph. Our algorithm derives from a highly parallel but non-resilient algorithm, which is based on the technique of label propagation (LP). To make the LP algorithm resilient to transient soft faults, we apply an algorithmic design principle that we refer to as self-correction. Briefly, a self-correcting algorithm detects if it has reached an invalid state given that it was previously in a known valid state; and if so, restores itself back to a valid state assuming the availability of a selective guaranteed-reliable mode. Our self-correcting algorithm, FT-LP, has relatively small storage and computation overheads: in empirical tests on a variety of input graphs, we observe execution time overheads of 10-35% in FT-LP compared to LP even at high fault rates, with the computation overhead increasing gracefully as fault rates increase.",

keywords = "Fault-tolerance, Label propagation, Selective reliability, Self-stabilization, Transient soft faults",

author = "Piyush Sao and Oded Green and Chirag Jain and Richard Vuduc",

note = "Publisher Copyright: {\textcopyright} 2016 ACM.; ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, FTXS 2016 ; Conference date: 31-05-2016",

year = "2016",

month = may,

day = "31",

doi = "10.1145/2909428.2909435",

language = "English",

series = "FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale",

publisher = "Association for Computing Machinery, Inc",

pages = "9--16",

booktitle = "FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale",

}

Sao, P, Green, O, Jain, C & Vuduc, R 2016, A self-correcting connected components algorithm. in FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale. FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, Association for Computing Machinery, Inc, pp. 9-16, ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, FTXS 2016, Kyoto, Japan, 05/31/16. https://doi.org/10.1145/2909428.2909435

A self-correcting connected components algorithm. / Sao, Piyush; Green, Oded; Jain, Chirag et al.
FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale. Association for Computing Machinery, Inc, 2016. p. 9-16 (FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A self-correcting connected components algorithm

AU - Sao, Piyush

AU - Green, Oded

AU - Jain, Chirag

AU - Vuduc, Richard

PY - 2016/5/31

Y1 - 2016/5/31

N2 - We present a new fault-tolerant algorithm for the problem of computing the connected components of a graph. Our algorithm derives from a highly parallel but non-resilient algorithm, which is based on the technique of label propagation (LP). To make the LP algorithm resilient to transient soft faults, we apply an algorithmic design principle that we refer to as self-correction. Briefly, a self-correcting algorithm detects if it has reached an invalid state given that it was previously in a known valid state; and if so, restores itself back to a valid state assuming the availability of a selective guaranteed-reliable mode. Our self-correcting algorithm, FT-LP, has relatively small storage and computation overheads: in empirical tests on a variety of input graphs, we observe execution time overheads of 10-35% in FT-LP compared to LP even at high fault rates, with the computation overhead increasing gracefully as fault rates increase.

AB - We present a new fault-tolerant algorithm for the problem of computing the connected components of a graph. Our algorithm derives from a highly parallel but non-resilient algorithm, which is based on the technique of label propagation (LP). To make the LP algorithm resilient to transient soft faults, we apply an algorithmic design principle that we refer to as self-correction. Briefly, a self-correcting algorithm detects if it has reached an invalid state given that it was previously in a known valid state; and if so, restores itself back to a valid state assuming the availability of a selective guaranteed-reliable mode. Our self-correcting algorithm, FT-LP, has relatively small storage and computation overheads: in empirical tests on a variety of input graphs, we observe execution time overheads of 10-35% in FT-LP compared to LP even at high fault rates, with the computation overhead increasing gracefully as fault rates increase.

KW - Fault-tolerance

KW - Label propagation

KW - Selective reliability

KW - Self-stabilization

KW - Transient soft faults

UR - http://www.scopus.com/inward/record.url?scp=84978525713&partnerID=8YFLogxK

U2 - 10.1145/2909428.2909435

DO - 10.1145/2909428.2909435

M3 - Conference contribution

AN - SCOPUS:84978525713

T3 - FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale

SP - 9

EP - 16

BT - FTXS 2016 - Proceedings of the ACM Workshop on Fault-Tolerance for HPC at Extreme Scale

PB - Association for Computing Machinery, Inc

T2 - ACM Workshop on Fault-Tolerance for HPC at Extreme Scale, FTXS 2016

Y2 - 31 May 2016

ER -

A self-correcting connected components algorithm

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this