Leader Election in Unreliable Radio Networks
Leader Election in Unreliable Radio Networks
复制标题
不可靠无线电网络中的领导者选举
DOI：
10.4230/lipics.icalp.2016.138
复制
发表时间：
2016
影响因子：
1.3
通讯作者：
Calvin C. Newport
中科院分区：
文献类型：
--
作者：
M. Ghaffari;Calvin C. Newport
对偶图模型描述了包含可靠和不可靠链路的无线电网络。近年来，该模型受到分布式算法社区的显著关注[Kuhn/Lynch/纽波特/Oshman/Richa，PODC 2010; Censor-Hillel/吉尔伯特/Kuhn/Lynch/纽波特，Dist. Comp. 2014; Ghaffari/Haeupler/Lynch/纽波特，DISC 2012; Ghaffari/Lynch/纽波特，PODC 2013; Ghaffari/Kantor/Lynch/纽波特，PODC 2014;纽波特，DISC 2014; Ahmadi/Ghodselahi/Kuhn/Molla，OPODIS 2015; Lynch/纽波特，PODC 2015]。由于[Ghaffari/Lynch/纽波特，PODC 2013]中的结果，已知领导者选举在实现这种困难设置中的有效计算中起着关键作用：领导者可以同步网络，使得大多数问题可以随后在时间上解决，类似于缺乏不可靠链路的经典无线电网络模型。然而，在对偶图模型中有效的领导者选举的可行性是一个重要的悬而未决的问题。在本文中，我们回答这个问题。更详细地说，我们证明了新的上限和下限的结果，在这种情况下，领导人选举的复杂性。通过这样做，我们揭示了一个令人惊讶的二分法：（1）假设网络大小n在1到N的范围内，其中N是最大可能网络大小的大上限（例如，ID空间），领导者选举基本上是困难的，在最坏情况下需要~Omega（sqrt（N））轮来解决;（2）然而，在n在2到N的范围内的假设下，对于网络直径D，该问题可以仅在~O（D）轮中解决，匹配标准无线电网络模型中的领导者选举的下限（在对数因子内）[Ghaffari/Haeupler，SODA 2013]。
The dual graph model describes a radio network that contains both reliable and unreliable links. In recent years, this model has received significant attention by the distributed algorithms community [Kuhn/Lynch/Newport/Oshman/Richa, PODC 2010; Censor-Hillel/Gilbert/Kuhn/Lynch/Newport, Dist. Comp. 2014; Ghaffari/Haeupler/Lynch/Newport, DISC 2012; Ghaffari/Lynch/Newport, PODC 2013; Ghaffir/Kantor/Lynch/Newport, PODC 2014; Newport, DISC 2014; Ahmadi/Ghodselahi/Kuhn/Molla, OPODIS 2015; Lynch/Newport, PODC 2015]. Due to results in [Ghaffari/Lynch/Newport, PODC 2013], it is known that leader election plays a key role in enabling efficient computation in this difficult setting: a leader can synchronize the network in such a manner that most problems can be subsequently solved in time similar to the classical radio network model that lacks unreliable links. The feasibility of efficient leader election in the dual graph model, however, was left as an important open question. In this paper, we answer this question. In more detail, we prove new upper and lower bound results that characterize the complexity of leader election in this setting. By doing so, we reveal a surprising dichotomy: (1) under the assumption that the network size n is in the range 1 to N, where N is a large upper bound on the maximum possible network size (e.g., the ID space), leader election is fundamentally hard, requiring ~Omega(sqrt(N)) rounds to solve in the worst-case; (2) under the assumption that n is in the range 2 to N, however, the problem can be solved in only ~O(D) rounds, for network diameter D, matching the lower bound for leader election in the standard radio network model (within log factors) [Ghaffari/Haeupler, SODA 2013].