Presently, the practice of distributed computing is such that problems exist in a mathematical realm different from their solutions: a problem is presented as a set of requirements on possible process or system behaviors, and the solution is presented as algorithmic pseudocode satisfying the requirements. Here, we present a novel mathematical realm, termed \emph{multiagent transition systems}, that aims to accommodate both distributed computing problems and their solutions. A problem is presented as a specification -- a multiagent transition system -- and a solution as an implementation of the specification by another, lower-level multiagent transition systems. This duality of roles of a multiagent transition system can be exploited all the way from a high-level distributed computing problem description down to an agreed-upon base layer, say TCP/IP, resulting in a mathematical protocol stack where each protocol is implemented by the one below it. Correct implementations are compositional and thus provide also an implementation of the protocol stack as a whole. The framework also offers a formal, yet natural, notion of faults and their resilience. We present two illustrations of the power of the approach: A multiagent transition systems specifying a centralized single-chain protocol and a distributed longest-chain protocol, show an implementation of this protocol by the longest-chain protocol, and conclude -- via the compositionality of correct implementations -- that the distributed longest-chain protocol is universal for centralized multiagent transition systems. Second, we describe a DAG-based blockchain consensus protocol stack that addresses each of the key tasks of a blockchain protocol -- dissemination, equivocation-exclusion, and ordering -- by a different layer of the stack. Additional applications of this mathematical framework are underway.


翻译:目前,分布式计算的做法是,在数学领域存在不同于其解决办法的问题:一个问题作为一套关于可能的程序或系统行为的要求提出,一个问题作为一套关于可能的程序或系统行为的要求提出,而解决办法则作为符合要求的算法伪编码提出。在这里,我们提出了一个新的数学领域,称为\emph{多剂过渡系统},旨在兼顾分布式计算问题及其解决办法。一个问题作为一个规格 -- -- 多剂过渡系统 -- -- 以及作为另一个较低层次的多剂过渡系统执行规格的解决办法。多剂过渡系统的作用的双重性,可以从一个高层次的分布式计算应用到一个商定的基础层,如TCP/IP,由此产生了一个数学协议堆,其中每个协议都由下面的一个实施方执行。 正确的执行是构成性的,从而也提供了整个协议层的落实。这个框架还提供了一个正式的,但自然的缺陷及其复原力概念。我们通过两个关于方法的力量的图解:多剂过渡系统说明一个集中的单一链式协议,一个链式应用系统,一个我们通过协议执行最长时间的链式协议的版本,一个协议执行过程,一个最长时间的顺序,一个我们通过协议执行的链式协议的顺序,一个协议,一个最长时间的顺序,一个协议,一个协议执行系统,一个最长时间的顺序,一个协议的顺序,一个执行,一个协议的顺序,一个执行系统,一个最固定式的顺序。

0
下载
关闭预览

相关内容

DC:Distributed Computing。 Explanation:分布式计算。 Publisher:Springer。 SIT:http://dblp.uni-trier.de/db/journals/dc/
最新《Transformers模型》教程,64页ppt
专知会员服务
306+阅读 · 2020年11月26日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
3+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
45+阅读 · 2019年12月20日
Arxiv
35+阅读 · 2019年11月7日
VIP会员
相关VIP内容
最新《Transformers模型》教程,64页ppt
专知会员服务
306+阅读 · 2020年11月26日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
IEEE TII Call For Papers
CCF多媒体专委会
3+阅读 · 2022年3月24日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
3+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员