Research on Complexity of Self-adaptive Distributed Algorithms in Dynamic Networks

本研究旨在提出一种在动态网络环境下既能保证自适应性又能保证稳定性的分布式算法设计框架。具体地说，我们专注于保证自适应的自稳定分布式算法。我们证明了稳定性是通过减少环境动态变化后的计算量来实现的。此外，我们还给出了稳定化(即重新计算)所需信息量的下界，并针对动态网络提出了自适应和稳定的分布式算法。

This research aims to propose a framework for designing distributed algorithms that promises both self-adaptability and stability under dynamic networks. Specifically, we focus on self-stabilizing distributed algorithms that guarantee self-adaptability. We showed that stability is achieved by reducing the recomputation after dynamic changes in environments. Additionally, we showed the lower bound for necessary amount of information during stabilization (i.e., recomputation), and proposed self-adaptive and stable distributed algorithms for dynamic networks.