NeTS: Small: Distributed and Efficient Randomized Algorithms for Large Networks

大多数分布式和随机算法的核心是一个马尔可夫链，它“访问和采样”图中节点的子集，满足以下三个性质：从图中行走得到的答案是收敛的，下一个状态的转移概率只依赖于局部可用的信息，收敛是“快速混合”或有效的。本提案将开发改进马尔可夫链蒙特卡罗（MCMC）算法混合时间的方法。然后将这些方法应用于三个不同领域的算法的构建块(1)采样大图(2)无线多跳调度和(3)无线传感器网络中的占空比。更广泛的影响：类似mcmc的方法是广泛的社会和经济重要问题的算法基础，并且改进混合时间的进展将产生重大影响。此外，该提案强调了学生指导和跨学科课程开发。

At the heart of most algorithms for distributed and randomized algorithms is a Markov chain that 'visits and samples' a subset of the nodes in the graph and which satisfies the following three properties: the answer derived from walking the graph converges, the transition probabilities for next state only depend on locally available information and the convergence is 'fast-mixing' or efficient. The proposal will develop approaches for improving the mixing time of Markov Chain Monte Carlo (MCMC) algorithms. These approaches are then to be applied as a building block for algorithms in three distinct areas -- (1) sampling large graphs (2) wireless multihop scheduling and (3) duty cycling in wireless sensor networks.Broader Impact: MCMC-like approaches underly algorithms for a wide range of socially and economically important problems and that progress in improving the mixing time will have significant impacts. Additionally, the proposal highlights student mentorship and interdisciplinary course development.