Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Proof sketches: verifiable in-network aggregation

Garofalakis Minos, Hellerstein Joseph M., Maniatis Petros

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/1C4CF2E5-1B4C-471E-8E48-469FDE16C3F7
Έτος 2007
Τύπος Πλήρης Δημοσίευση σε Συνέδριο
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά 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
Εμφανίζεται στις Συλλογές

Περίληψη

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.

Υπηρεσίες

Στατιστικά