Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Proof sketches: verifiable in-network aggregation

Garofalakis Minos, Hellerstein Joseph M., Maniatis Petros

Full record


URI: http://purl.tuc.gr/dl/dias/1C4CF2E5-1B4C-471E-8E48-469FDE16C3F7
Year 2007
Type of Item Conference Full Paper
License
Details
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

Summary

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.

Services

Statistics