Abstract
This paper presents an efficient deterministic gossip algorithm for p synchronous, crash-prone, message-passing processors. The algorithm has time complexity T = O(log2 p) and message complexity M=O(p 1 + ε), for any ε>0. This substantially improves the message complexity of the previous best algorithm that has M=O(p 1.77), while maintaining the same time complexity. The strength of the new algorithm 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,log 3 p}) 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.
This research was supported by the NSF Grants 9988304, 0121277, and 0311368. The work of the second author was supported by the NSF-NATO Award 0209588. The work of the third author was supported by the NSF CAREER Award 9984778.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. J. Wiley and Sons, Inc., Chichester (2000)
Anderson, R.J., Woll, H.: Algorithms for the certified Write-All problem. SIAM Journal of Computing 26(5), 1277–1283 (1997)
Chlebus, B., De Prisco, R., Shvartsman, A.A.: Performing tasks on restartable message-passing processors. Distributed Computing 14(1), 49–64 (2001)
Chlebus, B.S., Gasieniec, L., Kowalski, D.R., Shvartsman, A.A.: Bounding work and communication in robust cooperative computation. In: 16th International Symposium on Distributed Computing, pp. 295–310 (2002)
Chlebus, B.S., Kowalski, D.R.: Gossiping to reach consensus. In: 14th Symposium on Parallel Algorithms and Architectures, pp. 220–229 (2002)
De Prisco, R., Mayer, A., Yung, M.: Time-optimal message-efficient work performance in the presence of faults. In: 13th Symposium on Principles of Distributed Computing, pp. 161–172 (1994)
Dwork, C., Halpern, J., Waarts, O.: Performing work efficiently in the presence of faults. SIAM Journal on Computing 27(5), 1457–1491 (1998)
Galil, Z., Mayer, A., Yung, M.: Resolving message complexity of byzantine agreement and beyond. In: 36th Symp. on Foundations of Comp. Sc., pp. 724–733 (1995)
Georgiou, C., Russell, A., Shvartsman, A.A.: The complexity of synchronous iterative Do-All with crashes. In: 15th Int-l Symposium on Distributed Computing, pp. 151–165 (2001)
Georgiou, C., Kowalski, D., Shvartsman, A.A.: Efficient gossip and robust distributed computation, http://www.engr.uconn.edu/~aas/GKS-2003.ps
Kanellakis, P.C., Shvartsman, A.A.: Efficient parallel algorithms can be made robust. Distributed Computing 5(4), 201–217 (1992)
Malewicz, G., Russell, A., Shvartsman, A.A.: Distributed cooperation during the absence of communication. In: 14th Int-l Symp. on Distr. Computing, pp. 119–133 (2000)
Pelc, A.: Fault-tolerant broadcasting and gossiping in communication networks. Networks 28, 143–156 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Georgiou, C., Kowalski, D.R., Shvartsman, A.A. (2003). Efficient Gossip and Robust Distributed Computation. In: Fich, F.E. (eds) Distributed Computing. DISC 2003. Lecture Notes in Computer Science, vol 2848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39989-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-39989-6_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20184-7
Online ISBN: 978-3-540-39989-6
eBook Packages: Springer Book Archive