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.