Dependable decentralized cooperation with the help of reliability estimation

Seda Davtyan, Kishori M. Konwar, Alexander A. Shvartsman

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 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 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 Θ(t/n log n) communication rounds, has work complexity Θ(t log n), and message complexity O(n log2 n); (b) when the bound is polynomial (|P−F| = Ω(na), for a constant a ∈ (0, 1)), the algorithm takes O(t/na log n log log n) rounds, with work O(t log n log log n), and message complexity O(n log2 n log log n); (c) when the bound is polylog in n, it takes O(t) rounds, has work O(t·na), and message complexity O(n1+a), for a ∈ (0, 1).

Original languageEnglish (US)
Title of host publicationStabilization, Safety and Security of Distributed Systems
EditorsPascal Felber, Vijay K. Garg
PublisherSpringer Verlag
Number of pages16
ISBN (Electronic)9783319117638
StatePublished - 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Dependable decentralized cooperation with the help of reliability estimation'. Together they form a unique fingerprint.

Cite this