26/02/2019, 14h00, LIP6 25-26.105

Title: Parallel Complexity for MapReduce Computation

Abstract: MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing BigData on tera- and peta-byte scale. In this note, we introduce several theoretical computational models for MapReduce computation from a standpoint of parallel algorithmic power by comparing MapReduce computation with standard parallel computational models such as PRAMs and/or combinational Boolean circuits. We survey recent results and new one about computational parallel complexity of MapReduce computation.

Bio: Kochi Wada is currently serving as a Professor in the department of Applied Informatics under Faculty of Science and Engineering at Hosei University, Japan since April 2012. He is also serving as an Emeritus Professor at Nagoya Institute of Technology (NIT) since May, 2012. Earlier Prof. Wada received his PH.D degree in Information and Computer Science from Osaka University in 1983. He also served as a visiting Professor at ETH Zurich (Switzerland), RWTH, Aachen (Germany), University of Wisconsin Milwaukee (USA), University of Minnesota (USA). His current research includes graph theoretical concepts, ad-hoc sensor networks, parallel and distributed computing and big data. He is a member of ACM, IEEE, IPSJ, IEICE (fellow).