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

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

本项目旨在探索一般拓扑的通信网络上分布式决策问题的可计算性与同步性之间的关系，致力于进一步加强拓扑学与计算机科学之间的联系。因此，我们不仅研究了分布式秘书问题、多智能体博弈等具体问题，还对图和分布式计算的基础、共性问题进行深入探讨，并且把相关结果和方法应用到以车载网和无线传感网络为代表的容迟网络中。主要进展如下：.算法方面，分析了容迟网络的通信延迟，发现中转节点延迟与中转节点的缓存大小无关，对双跳容迟网络中的通信延迟给出了高精度的估计；首次关注了低秩二部图中匹配的结构性特征，证明在一定条件下其局部性完全由秩决定，一般情况下可以通过任意小的扰动降低局部性；首次研究了动态数据的top-k排序问题，找到了该问题以高概率无误差可解的充要条件；首次提出了并行秘书问题的高效、竞争比最优、确定性的算法，并对若干特例明确找到了其近似比；在无向简单图上，证明了阈值匹配博弈的最小核和核仁都是多项式可解的，并且对它们给出了显式的刻画。.拓扑学方面，探讨了(n-1)连通的(n+k)-维复形的伦型分类，对其同调群没有2阶和3阶挠子群并且 k<7，或者同调群没有2阶挠子群并且 k＝4的情况得到了完全的分类，表明同调群不含2阶挠子群这一条件是伦型分类中必不可少的条件；针对图的交换正则覆盖问题，我们通过把寻找交换覆盖归结为寻找满足特定性质的数和矩阵，可以找到所有有限交换正则覆盖，并在此基础上得到Petersen 图的有向边可迁有限交换正则覆盖的分类。.应用方面，我们主要针对车载网络和无线传感器网络，进行了通信协议、休眠调度、数据聚合等方面的研究，提出了高效、节能的算法，搭建了一个可扩展的车载/无线传感器网络仿真平台，并在此平台上对算法进行验证。.