A robust randomized algorithm to perform independent tasks

详细信息    查看全文

• 作者：Bogdan S. Chlebus ; Leszek Gä ; sieniec ; Dariusz R. Kowalski ; Alex A. Shvartsman
• 关键词：Randomization ; Distributed algorithm ; Message passing ; Crash failure ; Scheduling tasks ; Ramanujan graphs
• 刊名：Journal of Discrete Algorithms
• 出版年：2008
• 出版时间：December 2008
• 年：2008
• 卷：6
• 期：4
• 页码：651-665
• 全文大小：272 K

文摘

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 expected work and expected communication, for an arbitrary number f<p of crashes.