Gossiping of a single source with multiple messages (by splitting information into pieces) hasbeen treated only for complete graphs, shown to considerably reduce the completion time, that is, thefirst time at which all network nodes are informed, compared with single-message gossiping. In thispaper, gossiping of a single source with multiple messages is treated, for networks modeled as certainstructured graphs, wherein upper bounds of the high-probability completion time are established througha novel “dependency graph” technique. The results shed useful insights into the behavior of multiple-messagegossiping and can be useful for data dissemination in sensor networks, multihopping contentdistribution, and file downloading in peer-to-peer networks.
展开▼
