Singularly Near Optimal Leader Election in Asynchronous Networks
Singularly Near Optimal Leader Election in Asynchronous Networks
复制标题
DOI：
10.4230/lipics.disc.2021.27
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
S. Kutten;W. Moses;Gopal Pandurangan;D. Peleg
中科院分区：
文献类型：
--
作者：
S. Kutten;W. Moses;Gopal Pandurangan;D. Peleg
本文涉及设计分布式算法的分布式算法，这些算法是{\ em singunder of Trimalal}，即，对于{\ em emnchronous}网络中的基本领导者选举问题，这些算法是{\ em同时}时间和消息{\ em optimal}。 Kutten等。 （JACM 2015）在一般{\ em同步}网络中呈现了一个最佳的最佳随机领导者选举算法，该算法在$ o（d）$ time中运行，并使用了$ o（m \ log n）$消息（其中$ d $，$ d $，$ M $和$ n $是网络的直径，边数和节点的数量），概率很高。概率“意思是”概率至少$ 1-1/n^c $，对于常数$ c $。”}这两个界限都接近最佳（最多是对数因素），因为$ \ omema（d）$和$ \ omega （m）$是时间和领导者选举的时间和消息的各个范围，即使是同步网络甚至（Monte-Carlo）随机算法。另一方面，对于一般的异步网络，领导者选举算法仅是最佳时间或消息最佳的已知，但两者兼而有之。 Kutten等。 （DISC 2020）提出了一种随机的异步领导者选举算法，该算法几乎是\ emph {完整网络}的最佳选择，但为一般网络打开了问题。本文表明，对于一般{\ em Asynchronous}网络，可以达到接近最佳（最终达到多毛因子因子）的界限。我们提出了一个随机的近乎最佳的领导者选举算法，该算法以$ O（D + \ log^2n）$时间和$ O（M \ log^2 N）$含量高的概率运行。我们的结果是第一个已知的异步网络的分布式领导者选举算法，该算法在时间和消息复杂性方面几乎是最佳的，并且在长期的结果中改善了，包括Gallager等人的经典结果。 （ACM Toplas，1983），Peleg（JPDC，1989）和Awerbuch（Stoc 89）。
This paper concerns designing distributed algorithms that are {\em singularly optimal}, i.e., algorithms that are {\em simultaneously} time and message {\em optimal}, for the fundamental leader election problem in {\em asynchronous} networks. Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general {\em synchronous} networks that ran in $O(D)$ time and used $O(m \log n)$ messages (where $D$, $m$, and $n$ are the network's diameter, number of edges and number of nodes, respectively) with high probability.\footnote{Throughout,"with high probability"means"with probability at least $1-1/n^c$, for constant $c$."} Both bounds are near optimal (up to a logarithmic factor), since $\Omega(D)$ and $\Omega(m)$ are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for \emph{complete networks}, but left open the problem for general networks. This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general {\em asynchronous} networks. We present a randomized singularly near optimal leader election algorithm that runs in $O(D + \log^2n)$ time and $O(m\log^2 n)$ messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC 89).