Premium
Randomized broadcast in networks
Author(s) -
Feige Uriel,
Peleg David,
Raghavan Prabhakar,
Upfal Eli
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 0-387-52921-7
DOI - 10.1002/rsa.3240010406
Subject(s) - computer science , undirected graph , atomic broadcast , graph , computation , rumor , simple (philosophy) , distributed computing , computer network , theoretical computer science , broadcasting (networking) , algorithm , philosophy , public relations , epistemology , political science
In this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in the maintenance of replicated databases.