Kishori Mohan Konwar: Dependable Decentralized Cooperation with the Help of Reliability Estimation

Internet supercomputing is an approach to solving partition-able, computation-intensive problems by using large numbers of interconnected computers. We consider the abstract problem of n processors performing t independent tasks, with n< t, where each processor must obtain the results of all tasks. An adversary may cause a processor to return incorrect results with some probability, and/or cause the process to crash. Prior randomized synchronous algorithms for this problem 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 the probabilities of returning incorrect results for all other processors. This paper presents a new randomized synchronous algorithm that is able to deal with much stronger adversaries while achieving efficiency comparable to that of the weaker solutions. The adversary is constrained in two ways. First, the set of non-crashed processors must contain a subset H of the initial set of processors P, called the “hardened” set, for which the “average” probability of a processor returning a bogus result is inferior to 1/2. Notably, crashes may “increase” the average overall probability of processors returning incorrect results. Second, the adversary may crash a set of processors F, provided |P-F| is bounded from below. We consider three bounds on |P-F|: (a)~linear, (b) polynomial (fractional degree), and (c) polylog bounds. In the algorithm each live processor determines locally when all tasks are done and collects the correct results of all tasks, all with high probability. We provide work, time, and message complexity of our algorithm in the above three bounds.