Publication Details

J-ReCoVer: Java Reducer Commutativity Verifier

CHEN Yu-Fang, CHIANG Chang-Yi, HOLÍK Lukáš, KAO Wei-Tsung, LIN Hsin-Hung, VOJNAR Tomáš, WEN Yean-Fu and WU Wei-Cheng. J-ReCoVer: Java Reducer Commutativity Verifier. In: Proceedings of 17th Asian Symposium on Programming Languages and Systems (APLAS). Lecture Notes in Computer Science, vol. 11893. Cham: Springer International Publishing, 2019, pp. 357-366. ISBN 978-3-030-34174-9. Available from: https://link.springer.com/chapter/10.1007%2F978-3-030-34175-6_18
Czech title
J-ReCoVer: Nástroj pro verifikaci komutativity redukčních funkcí v Javě
Type
conference paper
Language
english
Authors
Chen Yu-Fang (ASIN)
Chiang Chang-Yi (NTPU)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Kao Wei-Tsung (ASIN)
Lin Hsin-Hung (ASIN)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
Wen Yean-Fu (NTPU)
Wu Wei-Cheng (ASIN)
URL
Keywords

verification, reducer, MapReduce, Java, commutativity

Abstract

The MapReduce framework for data-parallel computation was first proposed by Google and later implemented in the Apache Hadoop project. Under the MapReduce framework, a reducer computes output values from a sequence of input values transmitted over the network. Due to non-determinism in data transmission, the order in which input values arrive at the reducer is not fixed. In relation to this, the commutativity problem of reducers asks if the output of a reducer is independent of the order of its inputs. Indeed, there are several advantages for a reducer to be commutative, e.g., the verification problem of a MapReduce program can be reduced to the problem of verifying a sequential program. We present the tool J-ReCoVer (Java Reducer Commutativity Verifier) that implements effective heuristics for reducer commutativity analysis. J-ReCoVer is the first tool that is specialised in checking reducer commutativity. Our experimental results over 118 benchmark examples collected from open repositories are very positive; J-ReCoVer correctly handles over 97% of them.

Annotation

The MapReduce framework for data-parallel computation was first proposed by Google and later implemented in the Apache Hadoop project. Under the MapReduce framework, a reducer computes output values from a sequence of input values transmitted over the network. Due to non-determinism in data transmission, the order in which input values arrive at the reducer is not fixed. In relation to this, the commutativity problem of reducers asks if the output of a reducer is independent of the order of its inputs. Indeed, there are several advantages for a reducer to be commutative, e.g., the verification problem of a MapReduce program can be reduced to the problem of verifying a sequential program. We present the tool J-ReCoVer (Java Reducer Commutativity Verifier) that implements effective heuristics for reducer commutativity analysis. J-ReCoVer is the first tool that is specialised in checking reducer commutativity. Our experimental results over 118 benchmark examples collected from open repositories are very positive; J-ReCoVer correctly handles over 97% of them.

Published
2019
Pages
357-366
Proceedings
Proceedings of 17th Asian Symposium on Programming Languages and Systems (APLAS)
Series
Lecture Notes in Computer Science
Volume
11893
Conference
17th Asian Symposium on Programming Languages and Systems -- APLAS'19, Bali, ID
ISBN
978-3-030-34174-9
Publisher
Springer International Publishing
Place
Cham, CH
DOI
UT WoS
000611530200018
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB12129,
   author = "Yu-Fang Chen and Chang-Yi Chiang and Luk\'{a}\v{s} Hol\'{i}k and Wei-Tsung Kao and Hsin-Hung Lin and Tom\'{a}\v{s} Vojnar and Yean-Fu Wen and Wei-Cheng Wu",
   title = "J-ReCoVer: Java Reducer Commutativity Verifier",
   pages = "357--366",
   booktitle = "Proceedings of 17th Asian Symposium on Programming Languages and Systems (APLAS)",
   series = "Lecture Notes in Computer Science",
   volume = 11893,
   year = 2019,
   location = "Cham, CH",
   publisher = "Springer International Publishing",
   ISBN = "978-3-030-34174-9",
   doi = "10.1007/978-3-030-34175-6\_18",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12129"
}
Back to top