A robust randomized algorithm to perform independent tasks

作     者：Chlebus, Bogdan S. Gasieniec, Leszek Kowalski, Dariusz R. Shvartsman, Alex A. 

作者机构：Univ Colorado Denver Dept Comp Sci & Engn Denver CO 80217 USA Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA MIT Comp Sci Lab Cambridge MA 02139 USA 

出 版 物：《JOURNAL OF DISCRETE ALGORITHMS》 (离散算法杂志)

年 卷 期：2008年第6卷第4期

页      面：651-665页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [0310503, 9988304, 0121277, 0311368, 0702670] NSFNATO NSF Career Award 

主　　题：Randomization Distributed algorithm Message passing Crash failure Scheduling tasks Ramanujan graphs 

摘      要：The Do-All problem is about scheduling t similar and independent tasks to be performed by p processors prone to crashes. We assume that the distributed system is synchronous with processors communicating by message passing. Crashes are determined by a fully adaptive adversary that is restricted only by an upper bound f on the number of crashes. The complexity of algorithms is measured by work and communication, where work is defined as the number of available-processor steps, and communication as the number of point-to-point messages. We develop a randomized algorithm with W = O(t + p. log(2) p/log log p) expected work and O((p/p-f)(3.4) W) expected communication, for an arbitrary number f p of crashes. (C) 2008 Elsevier B.V. All rights reserved.