2010 | OriginalPaper | Buchkapitel
Computing in Social Networks
verfasst von : Andrei Giurgiu, Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper defines the problem of Scalable Secure Computing in a Social network: we call it the
S
3
problem. In short, nodes, directly reflecting on associated users, need to compute a function
$f:\ V \rightarrow U$
of their inputs in a set of constant size, in a
scalable
and
secure
way. Scalability means that the message and computational complexity of the distributed computation is at most
$\mathcal{O}(\sqrt{n}\cdot {\rm polylog}{n})$
. Security encompasses (1) accuracy and (2) privacy: accuracy holds when the distance from the output to the ideal result is negligible with respect to the maximum distance between any two possible results; privacy is characterized by how the information disclosed by the computation helps faulty nodes infer inputs of non-faulty nodes.
We present AG-S3, a protocol that
S
3
-computes a class of aggregation functions, that is that can be expressed as a commutative monoid operation on
U
:
f
(
x
1
,...,
x
n
) =
x
1
⊕ ... ⊕
x
n
, assuming the number of faulty participants is at most
$\sqrt{n}/{\rm log}^2n$
. Key to our protocol is a dedicated overlay structure that enables secret sharing and distributed verifications which leverage the social aspect of the network: nodes care about their reputation and do not want to be tagged as misbehaving.