分布式决策问题的同步度研究

项目名称： 分布式决策问题的同步度研究

项目编号： No.61173009

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 自动化技术、计算机技术

项目作者： 刘兴武

作者单位： 中国科学院计算技术研究所

项目金额： 54万元

中文摘要： FLP定理揭示了异步分布式计算中的一个根本性障碍。为了绕开FLP障碍，一个常用的方法是在异步分布式系统中增加同步性。而实现和维护同步性需要较高成本，因此同步度（即最弱的偏同步性以容错地解决特定问题）成了重要的研究课题。然而，目前仅在完全图网络中、在所有过程都强同步且只能发生非Byzantine失效时、对consensus问题的同步度有较大进展。因此本课题在四个方面开展研究：常见分布式决策问题在一般拓扑网络中的同步度，过程同步度（即至少需要多少偏同步的过程），过程可能发生Byzantine失效时的同步度，以及偏同步性与失效探测器的关系（旨在利用失效探测器来研究同步度）。本项目将在上述过程中，重点凝练两个通用方法：处理偏同步和失效探测器中渐进性挑战的方法，以及从拓扑学角度对Byzantine失效建模和分析的方法。不仅为同步度研究及其方法论做出基础性贡献，在数学上还可能促进拓扑学的发展

中文关键词： 分布式计算；拓扑；容迟网络；动态数据算法；图论

英文摘要：

英文关键词： distributed computing；topology；delay-tolerant network；dynamic data algorithm；graph theory