2014 | OriginalPaper | Buchkapitel
Dependable Decentralized Cooperation with the Help of Reliability Estimation
verfasst von : Seda Davtyan, Kishori M. Konwar, Alexander A. Shvartsman
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer International Publishing
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
Internet supercomputing aims to solve large partitionable computational problems by using vast numbers of computers. Here we consider the abstract version of the problem, where
n
processors perform
t
independent tasks, with
n
≤
t
, and each processor learns the results of all tasks. An adversary may cause a processor to return incorrect results, and to crash. Prior solutions limited the adversary by either (
i
) assuming the average probability of returning incorrect results to always be inferior to
$\frac{1}{2}$
, or (
ii
) letting each processor know such probabilities for all other processors. This paper presents a new randomized synchronous algorithm that deals with stronger adversaries while achieving efficiency comparable to the weaker solutions. The adversary is constrained in two ways. (1) The set of non-crashed processors must contain a
hardened
subset
H
of the initial set of processors
P
, for which the
average
probability of returning a bogus result is inferior to
$\frac{1}{2}$
. Notably, crashes may
increase
the average probability of processor misbehavior. (2) The adversary may crash a set of processors
F
, provided |
P
−
F
| is bounded from below. We analyse the algorithm for three bounds on |
P
−
F
|: (
a
) when the bound is linear in
n
the algorithm takes
$\Theta(\frac{t}{n}\log{n})$
communication rounds, has work complexity Θ(
t
log
n
), and message complexity
O
(
n
log
2
n
); (
b
) when the bound is polynomial (|
P
−
F
| = Ω(
n
a
), for a constant
a
∈ (0,1)), the algorithm takes
$O(\frac{t}{n^{a}}\log{n}\log{\log{n}})$
rounds, with work
O
(
t
log
n
loglog
n
), and message complexity
O
(
n
log
2
n
loglog
n
); (
c
) when the bound is polylog in
n
, it takes
O
(
t
) rounds, has work
O
(
t
·
n
a
), and message complexity
O
(
n
1 +
a
), for
a
∈ (0,1).