FlyMC: Highly scalable testing of complex interleavings in distributed systems

Jeffrey F. Lukman; Huan Ke; Cesar A. Stuardo; Riza O. Suminto; Daniar H. Kurniawan; Dikaimin Simon; Satria Priambada; Chen Tian; Feng Ye; Tanakorn Leesatapornwongsa; Aarti Gupta; Shan Lu; Haryadi S. Gunawi

doi:10.1145/3302424.3303986

FlyMC: Highly scalable testing of complex interleavings in distributed systems

Jeffrey F. Lukman, Huan Ke, Cesar A. Stuardo, Riza O. Suminto, Daniar H. Kurniawan, Dikaimin Simon, Satria Priambada, Chen Tian, Feng Ye, Tanakorn Leesatapornwongsa, Aarti Gupta, Shan Lu, Haryadi S. Gunawi

Computer Science

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

29 Scopus citations

Abstract

We present a fast and scalable testing approach for datacenter/cloud systems such as Cassandra, Hadoop, Spark, and ZooKeeper. The uniqueness of our approach is in its ability to overcome the path/state-space explosion problem in testing workloads with complex interleavings of messages and faults. We introduce three powerful algorithms: state symmetry, event independence, and parallel flips, which collectively makes our approach on average 16× (up to 78×) faster than other state-of-the-art solutions. We have integrated our techniques with 8 popular datacenter systems, successfully reproduced 12 old bugs, and found 10 new bugs — all were done without random walks or manual checkpoints.

Original language	English (US)
Title of host publication	Proceedings of the 14th EuroSys Conference 2019
Publisher	Association for Computing Machinery, Inc
ISBN (Electronic)	9781450362818
DOIs	https://doi.org/10.1145/3302424.3303986
State	Published - Mar 25 2019
Event	14th European Conference on Computer Systems, EuroSys 2019 - Dresden, Germany Duration: Mar 25 2019 → Mar 28 2019

Publication series

Name	Proceedings of the 14th EuroSys Conference 2019

Conference

Conference	14th European Conference on Computer Systems, EuroSys 2019
Country/Territory	Germany
City	Dresden
Period	3/25/19 → 3/28/19

All Science Journal Classification (ASJC) codes

Hardware and Architecture
Electrical and Electronic Engineering

Keywords

Availability
Distributed Concurrency Bugs
Distributed Systems
Reliability
Software Model Checking

Access to Document

10.1145/3302424.3303986

Cite this

Lukman, J. F., Ke, H., Stuardo, C. A., Suminto, R. O., Kurniawan, D. H., Simon, D., Priambada, S., Tian, C., Ye, F., Leesatapornwongsa, T., Gupta, A., Lu, S., & Gunawi, H. S. (2019). FlyMC: Highly scalable testing of complex interleavings in distributed systems. In Proceedings of the 14th EuroSys Conference 2019 Article 3303986 (Proceedings of the 14th EuroSys Conference 2019). Association for Computing Machinery, Inc. https://doi.org/10.1145/3302424.3303986

@inproceedings{51de1c7ee8ee4d2c9801673884bcf726,

title = "FlyMC: Highly scalable testing of complex interleavings in distributed systems",

abstract = "We present a fast and scalable testing approach for datacenter/cloud systems such as Cassandra, Hadoop, Spark, and ZooKeeper. The uniqueness of our approach is in its ability to overcome the path/state-space explosion problem in testing workloads with complex interleavings of messages and faults. We introduce three powerful algorithms: state symmetry, event independence, and parallel flips, which collectively makes our approach on average 16× (up to 78×) faster than other state-of-the-art solutions. We have integrated our techniques with 8 popular datacenter systems, successfully reproduced 12 old bugs, and found 10 new bugs — all were done without random walks or manual checkpoints.",

keywords = "Availability, Distributed Concurrency Bugs, Distributed Systems, Reliability, Software Model Checking",

author = "Lukman, {Jeffrey F.} and Huan Ke and Stuardo, {Cesar A.} and Suminto, {Riza O.} and Kurniawan, {Daniar H.} and Dikaimin Simon and Satria Priambada and Chen Tian and Feng Ye and Tanakorn Leesatapornwongsa and Aarti Gupta and Shan Lu and Gunawi, {Haryadi S.}",

note = "Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 14th European Conference on Computer Systems, EuroSys 2019 ; Conference date: 25-03-2019 Through 28-03-2019",

year = "2019",

month = mar,

day = "25",

doi = "10.1145/3302424.3303986",

language = "English (US)",

series = "Proceedings of the 14th EuroSys Conference 2019",

publisher = "Association for Computing Machinery, Inc",

booktitle = "Proceedings of the 14th EuroSys Conference 2019",

}

Lukman, JF, Ke, H, Stuardo, CA, Suminto, RO, Kurniawan, DH, Simon, D, Priambada, S, Tian, C, Ye, F, Leesatapornwongsa, T, Gupta, A, Lu, S & Gunawi, HS 2019, FlyMC: Highly scalable testing of complex interleavings in distributed systems. in Proceedings of the 14th EuroSys Conference 2019., 3303986, Proceedings of the 14th EuroSys Conference 2019, Association for Computing Machinery, Inc, 14th European Conference on Computer Systems, EuroSys 2019, Dresden, Germany, 3/25/19. https://doi.org/10.1145/3302424.3303986

FlyMC: Highly scalable testing of complex interleavings in distributed systems. / Lukman, Jeffrey F.; Ke, Huan; Stuardo, Cesar A. et al.
Proceedings of the 14th EuroSys Conference 2019. Association for Computing Machinery, Inc, 2019. 3303986 (Proceedings of the 14th EuroSys Conference 2019).

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

TY - GEN

T1 - FlyMC

T2 - 14th European Conference on Computer Systems, EuroSys 2019

AU - Lukman, Jeffrey F.

AU - Ke, Huan

AU - Stuardo, Cesar A.

AU - Suminto, Riza O.

AU - Kurniawan, Daniar H.

AU - Simon, Dikaimin

AU - Priambada, Satria

AU - Tian, Chen

AU - Ye, Feng

AU - Leesatapornwongsa, Tanakorn

AU - Gupta, Aarti

AU - Lu, Shan

AU - Gunawi, Haryadi S.

PY - 2019/3/25

Y1 - 2019/3/25

N2 - We present a fast and scalable testing approach for datacenter/cloud systems such as Cassandra, Hadoop, Spark, and ZooKeeper. The uniqueness of our approach is in its ability to overcome the path/state-space explosion problem in testing workloads with complex interleavings of messages and faults. We introduce three powerful algorithms: state symmetry, event independence, and parallel flips, which collectively makes our approach on average 16× (up to 78×) faster than other state-of-the-art solutions. We have integrated our techniques with 8 popular datacenter systems, successfully reproduced 12 old bugs, and found 10 new bugs — all were done without random walks or manual checkpoints.

AB - We present a fast and scalable testing approach for datacenter/cloud systems such as Cassandra, Hadoop, Spark, and ZooKeeper. The uniqueness of our approach is in its ability to overcome the path/state-space explosion problem in testing workloads with complex interleavings of messages and faults. We introduce three powerful algorithms: state symmetry, event independence, and parallel flips, which collectively makes our approach on average 16× (up to 78×) faster than other state-of-the-art solutions. We have integrated our techniques with 8 popular datacenter systems, successfully reproduced 12 old bugs, and found 10 new bugs — all were done without random walks or manual checkpoints.

KW - Availability

KW - Distributed Concurrency Bugs

KW - Distributed Systems

KW - Reliability

KW - Software Model Checking

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

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

U2 - 10.1145/3302424.3303986

DO - 10.1145/3302424.3303986

M3 - Conference contribution

AN - SCOPUS:85063859202

T3 - Proceedings of the 14th EuroSys Conference 2019

BT - Proceedings of the 14th EuroSys Conference 2019

PB - Association for Computing Machinery, Inc

Y2 - 25 March 2019 through 28 March 2019

ER -

FlyMC: Highly scalable testing of complex interleavings in distributed systems

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this