Institutional Repository
Technical University of Crete
EN  |  EL



My Space

Proof sketches: verifiable in-network aggregation

Garofalakis Minos, Hellerstein Joseph M., Maniatis Petros

Full record

Year 2007
Type of Item Conference Full Paper
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
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.