Random Gossip Processes in Smartphone Peer-to-Peer Networks
Random Gossip Processes in Smartphone Peer-to-Peer Networks
复制标题
DOI：
10.1109/dcoss.2019.00041
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Calvin C. Newport;A. Weaver
中科院分区：
文献类型：
--
作者：
Calvin C. Newport;A. Weaver
在本文中，我们研究了随机八卦过程中的通信模型，描述了标准的智能手机操作系统中包含的对等网络功能。随机流言过程通过随机选择邻居进行连接的基本机制来传播信息。这些过程在标准的点对点网络模型中得到了很好的理解，但在抽象智能手机点对点设置的模型中，对它们的行为知之甚少。考虑到这一点，我们开始研究一个简单的随机八卦过程中的同步移动的电话模型（最常见的抽象用于研究智能手机点对点系统）。通过引入一种新的分析技术，我们证明了这个简单的过程实际上是更有效的比最著名的八卦算法在移动的电话模型，这需要复杂的协调网络中的节点之间。然后，我们介绍了一个新的变化的移动的电话模型，消除了同步轮的假设，缩小理论和实践之间的差距。我们证明了简单的随机八卦过程仍然收敛在这个设置和信息传播仍然改善沿着与图的连通性。这个新的模型和我们介绍的工具提供了一个坚实的基础，为进一步的理论分析的算法要部署在真实的智能手机对等网络。更一般地说，我们在本文中的结果意味着，简单的随机信息传播过程应该预期在这种新兴的点对点设置中表现良好。
In this paper, we study random gossip processes in communication models that describe the peer-to-peer networking functionality included in standard smartphone operating systems. Random gossip processes spread information through the basic mechanism of randomly selecting neighbors for connections. These processes are well-understood in standard peer-to-peer network models, but little is known about their behavior in models that abstract the smartphone peer-to-peer setting. With this in mind, we begin by studying a simple random gossip process in the synchronous mobile telephone model (the most common abstraction used to study smartphone peer-to-peer systems). By introducing a new analysis technique, we prove that this simple process is actually more efficient than the best-known gossip algorithm in the mobile telephone model, which required complicated coordination among the nodes in the network. We then introduce a novel variation of the mobile telephone model that removes the synchronized round assumption, shrinking the gap between theory and practice. We prove that simple random gossip processes still converge in this setting and that information spreading still improves along with graph connectivity. This new model and the tools we introduce provide a solid foundation for the further theoretical analysis of algorithms meant to be deployed on real smartphone peer-to-peer networks. More generally, our results in this paper imply that simple random information spreading processes should be expected to perform well in this emerging new pseer-to-peer setting.