کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430917 | 688229 | 2008 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A robust randomized algorithm to perform independent tasks
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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⋅log2ploglogp) expected work and O((pp−f)3.4W) expected communication, for an arbitrary number f
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 4, December 2008, Pages 651–665
Journal: Journal of Discrete Algorithms - Volume 6, Issue 4, December 2008, Pages 651–665
نویسندگان
Bogdan S. Chlebus, Leszek Ga̧sieniec, Dariusz R. Kowalski, Alex A. Shvartsman,