Asymptotically optimal randomized rumor spreading

摘要: We propose a new protocol for the fundamental problem of disseminating piece information to all members group n players. It builds upon classical randomized rumor spreading and several extensions. The main achievements are following: Our spreads from one node other nodes in asymptotically optimal time (1 + o(1)) log2 n. whole process can be implemented way such that only O(nf(n)) calls made, where f(n) = ω(1) arbitrary. In spite these quantities being close theoretical optima, remains relatively robust against failures; random failures, our algorithm again comes arbitrarily optima. The extended also deal with adversarial failures. price is constant factor increase run-time, depends on fraction failing supposed cope with. easily O(n) properly working made. In contrast push-pull by Karp et al. [FOCS 2000], uses push operations, i.e., informed take active actions network. On hand, we discard address-obliviousness. To best knowledge, this first achieves an running time.