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

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