The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
复制标题
路径上局部可检查问题的分布式复杂度是可判定的
DOI：
10.1145/3293611.3331606
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Suomela, Jukka
中科院分区：
文献类型：
--
作者：
Balliu, Alkida;Brandt, Sebastian;Chang, Yi-Jun;Olivetti, Dennis;Rabie, Mikaël;Suomela, Jukka
考虑一个计算机网络，它由一条有n个节点的路径组成。节点被标记为来自一个恒定大小的集合的输入，任务是从一个恒定大小的集合中找到输出标签，这些标签受到一些局部约束-更正式地说，我们有一个LCL（局部可检查标签）问题。需要多少次通信（在标准的计算模型中）来解决这个问题？众所周知，答案总是O（1）轮，或Θ（log n）轮，或Θ（n）轮。在这项工作中，我们表明，这个问题是可判定的（虽然PSPACE硬）：我们提出了一个算法，给定任何LCL问题上定义的路径，输出分布式计算复杂性的这个问题和相应的渐近最优算法。
Consider a computer network that consists of a path with n nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a constant-sized set subject to some local constraints---more formally, we have an LCL (locally checkable labeling) problem. How many communication rounds are needed (in the standard LOCAL model of computing) to solve this problem?It is well known that the answer is always either O(1) rounds, or Θ(log⋅n) rounds, or Θ(n) rounds. In this work we show that this question is decidable (albeit PSPACE-hard): we present an algorithm that, given any LCL problem defined on a path, outputs the distributed computational complexity of this problem and the corresponding asymptotically optimal algorithm.
登录
查看更多内容
改进的分布式 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin }{-69pt} egin{文档}$$Delta $$end{文档}Δ-着色
影响因子：
1.3
作者：
M. Ghaffari;J. Hirvonen;F. Kuhn;Yannic Maus
通讯作者：
Yannic Maus
在无三角形图上使用局部算法进行大切割
影响因子：
0.7
作者：
J. Hirvonen;Joel Rybicki;S. Schmid;J. Suomela
通讯作者：
J. Suomela
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
影响因子：
5.9
作者：
D. Dolev;Keijo Heljanko;Matti Järvisalo;Janne H. Korhonen;C. Lenzen;Joel Rybicki;J. Suomela;Siert Wieringa
通讯作者：
Siert Wieringa
网格拼箱问题
DOI：
--
发表时间：
2017
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
S. Brandt;J. Hirvonen;Janne H. Korhonen;Tuomo Lempiäinen;P. Östergård;Christopher Purcell;Joel Rybicki;J. Suomela;P. Uznański
通讯作者：
P. Uznański