Το έργο με τίτλο Proof sketches: verifiable in-network aggregation από τον/τους δημιουργό/ούς Garofalakis Minos, Hellerstein Joseph M., Maniatis Petros διατίθεται με την άδεια Creative Commons Αναφορά Δημιουργού 4.0 Διεθνές
Βιβλιογραφική Αναφορά
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.