Detail publikačního výsledku

J-ReCoVer: Java Reducer Commutativity Verifier

CHEN, Y.; CHIANG, C.; HOLÍK, L.; KAO, W.; LIN, H.; VOJNAR, T.; WEN, Y.; WU, W.

Originální název

J-ReCoVer: Java Reducer Commutativity Verifier

Anglický název

J-ReCoVer: Java Reducer Commutativity Verifier

Druh

Stať ve sborníku v databázi WoS či Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

verification, reducer, MapReduce, Java, commutativity

Klíčová slova v angličtině

verification, reducer, MapReduce, Java, commutativity

Autoři

CHEN, Y.; CHIANG, C.; HOLÍK, L.; KAO, W.; LIN, H.; VOJNAR, T.; WEN, Y.; WU, W.

Rok RIV

2020

Vydáno

08.11.2019

Nakladatel

Springer International Publishing

Místo

Cham

ISBN

978-3-030-34174-9

Kniha

Proceedings of 17th Asian Symposium on Programming Languages and Systems (APLAS)

Edice

Lecture Notes in Computer Science

Svazek

11893

Strany od

357

Strany do

366

Strany počet

10

URL

BibTex

@inproceedings{BUT161467,
  author="CHEN, Y. and CHIANG, C. and HOLÍK, L. and KAO, W. and LIN, H. and VOJNAR, T. and WEN, Y. and WU, W.",
  title="J-ReCoVer: Java Reducer Commutativity Verifier",
  booktitle="Proceedings of 17th Asian Symposium on Programming Languages and Systems (APLAS)",
  year="2019",
  series="Lecture Notes in Computer Science",
  volume="11893",
  pages="357--366",
  publisher="Springer International Publishing",
  address="Cham",
  doi="10.1007/978-3-030-34175-6\{_}18",
  isbn="978-3-030-34174-9",
  url="https://link.springer.com/chapter/10.1007%2F978-3-030-34175-6_18"
}