Deterministic Logarithmic Completeness in the Distributed Sleeping Model
Deterministic Logarithmic Completeness in the Distributed Sleeping Model
复制标题
分布式睡眠模型中的确定性对数完整性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tzalik Maimon
中科院分区：
文献类型：
--
作者：
Leonid Barenboim;Tzalik Maimon
我们提供了一个确定性方案，用于解决分布式{睡眠模型}中的任何可确定问题。睡眠模型是标准消息模型的概括，其额外的网络节点偶尔进入睡眠状态。只要顶点处于清醒状态，它就类似于标准消息设置。但是，当顶点入睡时，它无法在网络中接收或发送消息，也无法执行内部计算。另一方面，睡眠弹不算{清醒的复杂性。}醒着的复杂性是这种情况下的主要复杂性测量，这是顶点在执行过程中花费的醒目的数量。在本文中，我们根据清醒的复杂性，用最差的案例来设计算法。我们通过构造一个我们称为{分布式分层的树}的结构来设计一种确定性方案，以清醒复杂性为$ O（log n）$来解决此模型中的任何可决定性问题。这种结构在睡眠模型中非常强大，因为它允许人们在恒定的清醒次数中收集整个图形信息。此外，我们证明在该模型中不能改进我们的一般技术，这表明分布式分层树的构建本身需要$ OMEGA（log n）$清醒的回合。我们在这项工作中获得的另一个结果是确定性方案，用于从$ o（log delta + log^*n）$ awake nounds中从一类问题（表示O-local）中解决任何问题。该课程包含各种经过充分研究的问题，例如MIS和$（Delta+1）$ - 颜色。
We provide a deterministic scheme for solving any decidable problem in the distributed {sleeping model}. The sleeping model is a generalization of the standard message-passing model, with an additional capability of network nodes to enter a sleeping state occasionally. As long as a vertex is in the awake state, it is similar to the standard message-passing setting. However, when a vertex is asleep it cannot receive or send messages in the network nor can it perform internal computations. On the other hand, sleeping rounds do not count towards {awake complexity.} Awake complexity is the main complexity measurement in this setting, which is the number of awake rounds a vertex spends during an execution. In this paper we devise algorithms with worst-case guarantees on the awake complexity. We devise a deterministic scheme with awake complexity of $O(log n)$ for solving any decidable problem in this model by constructing a structure we call { Distributed Layered Tree}. This structure turns out to be very powerful in the sleeping model, since it allows one to collect the entire graph information within a constant number of awake rounds. Moreover, we prove that our general technique cannot be improved in this model, by showing that the construction of distributed layered trees itself requires $Omega(log n)$ awake rounds. Another result we obtain in this work is a deterministic scheme for solving any problem from a class of problems, denoted O-LOCAL, in $O(log Delta + log^*n)$ awake rounds. This class contains various well-studied problems, such as MIS and $(Delta+1)$-vertex-coloring.
DOI：
10.1145/3212734.3212774
发表时间：
2017-10
期刊：
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Yi-Jun Chang;Varsha Dani;Thomas P. Hayes;Qizheng He;Wenzheng Li;Seth Pettie
通讯作者：
Yi-Jun Chang;Varsha Dani;Thomas P. Hayes;Qizheng He;Wenzheng Li;Seth Pettie
睡眠是高效的：O(1) 轮中的 MIS 节点平均清醒复杂度
DOI：
10.1145/3382734.3405718
发表时间：
2020
期刊：
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Chatterjee, Soumyottam;Gmyr, Robert;Pandurangan, Gopal
通讯作者：
Pandurangan, Gopal