Premium
New bounds on the minimum number of calls in failure‐tolerant gossiping
Author(s) -
Hou Zhe,
Shigeno Maiko
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20259
Subject(s) - gossip , computer science , vertex (graph theory) , process (computing) , upper and lower bounds , dissemination , computer network , distributed computing , theoretical computer science , mathematics , graph , telecommunications , psychology , social psychology , mathematical analysis , operating system
Gossiping is an extensively investigated information dissemination process. In gossiping, every vertex holds a message that has to be transmitted to all other vertices. This article deals with k ‐failure tolerant gossiping, which investigates the minimum number of transmissions (calls) required by the communication process, provided that at most k transmissions may fail. We show new bounds for the number of transmissions, an improvement over previous results if k is sufficiently large. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009