CorrectMR: Authentication of Distributed SQL Execution on MapReduce

Bo Zhang, Boxiang Dong, Wendy Hui Wang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In this paper, we consider the SQL Selection-GroupBy-Aggregation (SGA) query evaluation on an untrusted MapReduce system in which mappers and reducers may return incorrect results. We design CorrectMR, a system that supports efficient verification of result correctness for both intermediate and final results of SGA queries. CorrectMR includes the design of Pedersen Merkle R-tree (PMR-tree), a new authenticated data structure (ADS). To enable efficient verification, CorrectMR includes a distributed ADS construction mechanism that allows mappers/reducers to construct PMR-trees in parallel without a centralized party. CorrectMR provides the following verification functionality: (1) correctness verification of PMR-trees by replication; (2) correctness verification of intermediate (final, resp.) query results by constructing local (global, resp.) PMR-trees and verification objects. Our experimental results demonstrate the efficiency and effectiveness of CorrectMR.

Original languageEnglish
Article number8807323
Pages (from-to)897-908
Number of pages12
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number3
StatePublished - 1 Mar 2021


  • MapReduce
  • authentication
  • database security
  • verifiable computation


Dive into the research topics of 'CorrectMR: Authentication of Distributed SQL Execution on MapReduce'. Together they form a unique fingerprint.

Cite this