A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed environment are subject to faults, an important issue is to be able to check that the output is correct, or in general that the network is in proper configuration with respect to some predicate. One would like this checking to be very local, to avoid using too much resources. Unfortunately most predicates cannot be checked this way, and that is where certification comes into play. Local certification (also known as proof-labeling schemes, locally checkable proofs or distributed verification) consists in assigning labels to the nodes, that certify that the configuration is correct. There are several point of view on this topic: it can be seen as a part of self-stabilizing algorithms, as labeling problem, or as a non-deterministic distributed decision. This paper is an introduction to the domain of local certification, giving an overview of the history, the techniques and the current research directions.


翻译:分布式图表算法基本上是一种算法, 每一个图表的节点都可以在图形中的某个距离查看其周围, 并选择其输出。 由于分布式环境存在错误, 一个重要的问题是能够检查输出是否正确, 或者一般地说, 网络对于某些上游的配置是否正确。 人们希望这个检查非常本地化, 以避免使用过多的资源。 不幸的是, 大多数的上游无法通过这个方式检查, 也就是验证起作用的地方 。 本地认证( 也称为 校对标签计划、 本地可核对的证明或分布式验证) 包括给节点分配标签, 以证明配置正确 。 在这个问题上有好几种观点: 它可以被看作是自我稳定算法的一部分, 标记问题, 或者非定义性分布式的决定 。 本文是本地认证域的介绍, 概括了历史、 技术和当前研究方向 。

0
下载
关闭预览

相关内容

数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
Arxiv
0+阅读 · 2021年11月4日
Arxiv
0+阅读 · 2021年11月3日
A Modern Introduction to Online Learning
Arxiv
20+阅读 · 2019年12月31日
Arxiv
4+阅读 · 2018年12月3日
VIP会员
相关VIP内容
数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
41+阅读 · 2020年7月27日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
Top
微信扫码咨询专知VIP会员