Abstract: Disconnection of links is common in network for reasons such as bandwidth overload. However existing synchronization algorithms don’t consider this situation. And experimental result shows that the disconnection of the network has a great influence on the synchronization efficiency, in the worst case the synchronization time of the algorithm is doubled. In order to alleviate the problem of the efficiency of the existing synchronization algorithm in the case of network disconnection, this paper proposes a dynamic local continuous tree algorithm (DLCT): in the event of a disconnection, an asynchronous adjustment operator (AAO) is used to adjust the communication pattern to avoid open circuits, and a local continuous tree (LCT) communication pattern is constructed to deliver synchronous messages efficiently. Because the communication mode of DLCT can be dynamically adjusted, the DLCT can effectively avoid the disconnection and it is 30% to 50% more efficient than existing algorithms.

Key words: synchronization mechanism, communication pattern, asynchronous adjusting

摘要： 在网络中，由于负载过量等原因导致网络断路的情况是常见的，而现有的同步算法未曾考虑这种状况，通过实验表明网络断路对同步效率的影响很大，最坏情况下断路会使得现有算法的同步时间增加一倍。为了缓解现有同步算法在网络断路情况下效率骤降的问题，在现有Barrier同步算法的基础上，提出一种动态局部连续树算法（dynamic local continuous tree，DLCT）。在断路时，调用提出的异步调整算子（asynchronous adjustment operator，AAO）对通信模式进行调整使之避开断路，并构造局部连续树（local continuous tree，LCT）结构的通信模式高效传递同步消息。DLCT的通信模式能动态调整有效避开断路，并提高同步机制在断路情况下的效率。在断路情况下DLCT比现有算法效率高30%到50%。

关键词: 同步机制, 通信模式, 异步调整