Show simple item record

dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorKowalski, D. R.en
dc.contributor.authorShvartsman, A. A.en
dc.creatorGeorgiou, Chryssisen
dc.creatorKowalski, D. R.en
dc.creatorShvartsman, A. A.en
dc.description.abstractThis paper presents an efficient deterministic gossip algorithm for p synchronous, crash-prone, message-passing processors. The algorithm has time complexity T=O(log2p) and message complexity M=O(p1+ε), for any ε>0. This substantially improves the message complexity of the previous best algorithm that has M=O(p1.77), while maintaining the same time complexity. The strength and utility of the new result is demonstrated by constructing a deterministic algorithm for performing n tasks in this distributed setting. Previous solutions used coordinator or check-pointing approaches, immediately incurring a work penalty Ω(n+f·p) for f crashes, or relied on strong communication primitives, such as reliable broadcast, or had work too close to the trivial Θ(p·n) bound of oblivious algorithms. The new algorithm uses p crash-prone processors to perform n similar and idempotent tasks so long as one processor remains active. The work of the algorithm is W=O(n+p·min{f+1,log3p}) and its message complexity is M=O(fpε+pmin{f+1,logp}), for any ε>0. This substantially improves the work complexity of previous solutions using simple point-to-point messaging, while "meeting or beating" the corresponding message complexity bounds. The new algorithms use communication graphs and permutations with certain combinatorial properties that are shown to exist. The algorithms are correct for any permutations, and in particular, the same expected bounds can be achieved using random permutations. © 2005 Elsevier B.V. All rights reserved.en
dc.sourceTheoretical Computer Scienceen
dc.subjectProblem solvingen
dc.subjectGraph theoryen
dc.subjectComputational complexityen
dc.subjectDistributed algorithmsen
dc.subjectComputer scienceen
dc.subjectCombinatorial toolsen
dc.subjectPerforming worken
dc.subjectProcessor failuresen
dc.titleEfficient gossip and robust distributed computationen
dc.description.endingpage166 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :20</p>en
dc.contributor.orcidGeorgiou, Chryssis [0000-0003-4360-0260]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record