Gossip in a Smartphone Peer-to-Peer Network
Gossip in a Smartphone Peer-to-Peer Network
复制标题
智能手机点对点网络中的八卦
DOI：
10.1145/3087801.3087813
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Newport, Calvin
中科院分区：
文献类型：
--
作者：
Newport, Calvin
在本文中，我们研究的基本问题，八卦的电话模型：最近推出的经典电话模型的修改，以更好地描述本地对等通信服务，在许多流行的智能手机操作系统中实现的变化。更详细地，移动的电话模型在三个方面不同于经典电话模型：（1）每个设备每轮最多可以参与一个连接;（2）网络拓扑可以经历参数化的变化速率;以及（3）设备可以在发起连接尝试之前在每轮中向它们的邻居通告关于它们的状态的参数化数量的比特。我们开始描述和分析新的随机八卦算法在这个模型下的网络拓扑结构，可以完全改变在每一轮的苛刻假设。我们证明了一个显着的时间复杂度差距的情况下，节点可以在每一轮广告0位到他们的邻居，和节点可以广告1位的情况下。对于后者的假设，我们提出了两个解决方案：第一个取决于一个共享的随机性源，而第二个消除了这个假设，使用伪随机发生器，我们证明了存在一个新的推广的经典结果，从两方通信的复杂性的研究。然后，我们把我们的注意力转向更容易的情况下，拓扑图是稳定的，并描述和分析一个新的八卦算法，提供了许多参数的性能大幅改善。最后，我们通过研究一个宽松的版本的八卦，它是唯一必要的节点，每个学习系统中的消息的指定部分。我们证明，我们现有的算法动态网络拓扑结构和一个单一的广告位解决这个宽松的版本多项式因子更快（网络大小）的许多参数。这些是移动的电话模型的第一个已知的八卦结果，它们极大地扩展了我们对如何在这个日益相关的环境中进行沟通和协调的理解。
In this paper, we study the fundamental problem of gossip in themobile telephone model: a recently introduced variation of the classicaltelephone modelmodified to better describe the local peer-to-peer communication services implemented in many popular smartphone operating systems. In more detail, the mobile telephone model differs from the classical telephone model in three ways: (1) each device can participate in at most one connection per round; (2) the network topology can undergo a parameterized rate of change; and (3) devices can advertise a parameterized number of bits about their state to their neighbors in each round before connection attempts are initiated. We begin by describing and analyzing new randomized gossip algorithms in this model under the harsh assumption of a network topology that can change completely in every round. We prove a significant time complexity gap between the case where nodes can advertise 0 bits to their neighbors in each round, and the case where nodes can advertise 1 bit. For the latter assumption, we present two solutions: the first depends on a shared randomness source, while the second eliminates this assumption using a pseudorandomness generator we prove to exist with a novel generalization of a classical result from the study of two-party communication complexity. We then turn our attention to the easier case where the topology graph is stable, and describe and analyze a new gossip algorithm that provides a substantial performance improvement for many parameters. We conclude by studying a relaxed version of gossip in which it is only necessary for nodes to each learn a specified fraction of the messages in the system. We prove that our existing algorithms for dynamic network topologies and a single advertising bit solve this relaxed version up to a polynomial factor faster (in network size) for many parameters. These are the first known gossip results for the mobile telephone model, and they significantly expand our understanding of how to communicate and coordinate in this increasingly relevant setting.
登录
查看更多内容
智能手机点对点网络中的领导者选举
DOI：
10.1109/ipdps.2017.11
发表时间：
2017
期刊：
Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS
影响因子：
--
作者：
Newport, Calvin
通讯作者：
Newport, Calvin
谣言传播和图表电导
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Flavio Chierichetti;Silvio Lattanzi;A. Panconesi
通讯作者：
A. Panconesi
影响因子：
2.5
作者：
George Giakkoupis
通讯作者：
George Giakkoupis
使用多点连接的点对点
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
David Mark;J. Varma;Jeff LaMarche;A. Horovitz;Kevin Kim
通讯作者：
Kevin Kim