Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/1C4CF2E5-1B4C-471E-8E48-469FDE16C3F7 | ||
| Year | 2007 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | M. Garofalakis, J. M. Hellerstein and P. Maniatis, "Proof sketches: verifiable in-network aggregation", in IEEE 23rd International Conference on Data Engineering, 2007, pp. 996-1005. doi: 10.1109/ICDE.2007.368958 https://doi.org/10.1109/ICDE.2007.368958 | ||
| Appears in Collections |
Recent work on distributed, in-network aggregation assumesa benign population of participants. Unfortunately,modern distributed systems are plagued by malicious participants.In this paper we present a first step towardsverifiable yet efficient distributed, in-network aggregationin adversarial settings. We describe a general frameworkand threat model for the problem and then present proofsketches, a compact verification mechanism that combinescryptographic signatures and Flajolet-Martin sketches toguarantee acceptable aggregation error bounds with highprobability. We derive proof sketches for count aggregatesand extend them for random sampling, which can be used toprovide verifiable approximations for a broad class of dataanalysisqueries, e.g., quantiles and heavy hitters. Finally,we evaluate the practical use of proof sketches, and observethat adversaries can often be reduced to much smaller violationsin practice than our worst-case bounds suggest.
Copyright © DIAS 2013
