论文标题
拉斯维加斯领导人选举的能源复杂性
The Energy Complexity of Las Vegas Leader Election
论文作者
论文摘要
我们考虑在多访问通道中随机领导者选举的时间和能量复杂性，其中设备的数量$ n \ geq 2 $是未知的。众所周知，对于多项式时间随机领导者选举算法，成功概率$ 1-1/poly（n）$，如果接收者可以检测碰撞，最佳能量复杂度为$θ（\ log \ log \ log \ log^*n）$，并且$θ（\ log log^*n）$否则。 没有碰撞检测，所有现有的随机领导者选举算法都使用$ o（\ log \ log n）$能量是蒙特卡洛，因为它们可能会以某种较小的概率失败，并且在失败时可能会消耗无界的能量，并且永远不会停止。尽管领导者选举的最佳能源复杂性似乎已经解决，但通过有效的拉斯维加斯算法，达到最佳的$ o（\ log^*n）$能量复杂性仍然是一个悬而未决的问题。在本文中，我们解决了这个基本问题。 $ \ textbf {蒙特卡洛和拉斯维加斯之间的分离：} $没有碰撞检测，我们证明，具有有限的预期时间复杂性的任何拉斯维加斯领导者选举算法必须使用$ω（\ log \ log \ log \ log \ log \ log n）$能量，建立Monte Carlo Carlo Carlo Carlo和Las vegas and Las vegas和Las vegas Algoriths之间的大分离。 $\textbf{Exponential improvement with sender collision detection:}$ In the setting where senders can detect collisions, we design a new leader election algorithm that finishes in $O(\log^{1+ε}n)$ time and uses $O(ε^{-1}\log\log\log n)$ energy in expectation, showing that sender collision detection helps improve the energy complexity指数。 $\textbf{Optimal deterministic leader election algorithm:}$ As a side result, via derandomization, we show a new deterministic algorithm that takes $O(n\log(N/n))$ time and $O(\log(N/n))$ energy to elect a leader from $n$ devices, where each device has a unique identifier in $[N]$.该算法是时间优势和最佳能量。
We consider the time and energy complexities of randomized leader election in a multiple-access channel, where the number of devices $n\geq 2$ is unknown. It is well-known that for polynomial-time randomized leader election algorithms with success probability $1-1/poly(n)$, the optimal energy complexity is $Θ(\log\log^*n)$ if receivers can detect collisions, and $Θ(\log^*n)$ otherwise. Without collision detection, all existing randomized leader election algorithms using $o(\log\log n)$ energy are Monte Carlo in that they may fail with some small probability, and they may consume unbounded energy and never halt when they fail. Though the optimal energy complexity of leader election appears to be settled, it is still an open question to attain the optimal $O(\log^*n)$ energy complexity by an efficient Las Vegas algorithm that never fails. In this paper we address this fundamental question. $\textbf{Separation between Monte Carlo and Las Vegas:}$ Without collision detection, we prove that any Las Vegas leader election algorithm with finite expected time complexity must use $Ω(\log\log n)$ energy, establishing a large separation between Monte Carlo and Las Vegas algorithms. $\textbf{Exponential improvement with sender collision detection:}$ In the setting where senders can detect collisions, we design a new leader election algorithm that finishes in $O(\log^{1+ε}n)$ time and uses $O(ε^{-1}\log\log\log n)$ energy in expectation, showing that sender collision detection helps improve the energy complexity exponentially. $\textbf{Optimal deterministic leader election algorithm:}$ As a side result, via derandomization, we show a new deterministic algorithm that takes $O(n\log(N/n))$ time and $O(\log(N/n))$ energy to elect a leader from $n$ devices, where each device has a unique identifier in $[N]$. This algorithm is time-optimal and energy-optimal.
