Tight Bounds for Quasirandom Rumor Spreading
Tight Bounds for Quasirandom Rumor Spreading
复制标题
准随机谣言传播的严格界限
DOI：
10.37236/191
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Panagiotou
中科院分区：
文献类型：
--
作者：
Spyros Angelopoulos;Benjamin Doerr;Anna Huber;K. Panagiotou
本文解决了以下基本问题：假设在一个由n个人组成的群体中，每个人都知道所有其他的群体成员，其中一个人拥有一条必须传播给群体中每个人的信息。人们应该如何传播信息，以便在短时间内每个人都被告知？经典的方法，被称为推模型，要求在每一轮中，每个知情者随机选择群体中的其他人，然后通知他们。在另一种被称为准随机推送模型的模型中，每个人都维护一个循环列表，即，组中所有成员的排列（例如，联系人列表）。一旦一个人被告知，它会在自己的列表中随机选择一个成员，从那时起，它会按照列表规定的顺序每轮通知一个新人。在本文中，我们证明了准随机协议以概率1 − o（1）在（1 ± o（1））log 2 n+ln n轮中通知每个人;此外，我们还证明了这个界是紧的。这一结果，再加上以前的工作的随机推模型，表明，无论列表的选择，quasirandom广播是一样快的随机推模型中的广播，到较低的订单条款。同时，它将随机位的数量从O（log 2 n）减少到每个人只有10 log 2 n n n。
This paper addresses the following fundamental problem: Suppose that in a group of n people, where each person knows all other group members, a single person holds a piece of information that must be disseminated to everybody within the group. How should the people propagate the information so that after short time everyone is informed? The classical approach, known as the push model, requires that in each round, every informed person selects some other person in the group at random, whom it then informs. In a different model, known as the quasirandom push model, each person maintains a cyclic list, i.e., permutation, of all members in the group (for instance, a contact list of persons). Once a person is informed, it chooses a random member in its own list, and from that point onwards, it informs a new person per round, in the order dictated by the list. In this paper we show that with probability 1 − o(1) the quasirandom protocol informs everybody in (1 ± o(1))log 2 n+ln n rounds; furthermore we also show that this bound is tight. This result, together with previous work on the randomized push model, demonstrates that irrespectively of the choice of lists, quasirandom broadcasting is as fast as broadcasting in the randomized push model, up to lower order terms. At the same time it reduces the number of random bits from O(log 2 n) to only ⌈log2 n⌉ per person.
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--