TY - JOUR
T1 - CorrectMR
T2 - Authentication of Distributed SQL Execution on MapReduce
AU - Zhang, Bo
AU - Dong, Boxiang
AU - Wang, Wendy Hui
N1 - Publisher Copyright:
© 1989-2012 IEEE.
PY - 2021/3/1
Y1 - 2021/3/1
N2 - 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.
AB - 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.
KW - MapReduce
KW - authentication
KW - database security
KW - verifiable computation
UR - http://www.scopus.com/inward/record.url?scp=85087510420&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087510420&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2019.2935968
DO - 10.1109/TKDE.2019.2935968
M3 - Article
AN - SCOPUS:85087510420
SN - 1041-4347
VL - 33
SP - 897
EP - 908
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 3
M1 - 8807323
ER -