ブロードキャストが可能な環境においてノードの平衡2分木状接続を自律的に行う分散アルゴリズムとその試験的実装

摘要

This paper shows an autonomous distributed algorithm which forms balanced binary structure of nodes, and an experimental structured P2P system which adopts the algorithm. This algorithm can be applied when nodes are IP reachable and broadcast-able. The time complexity of this algorithm is 0((logN)2), where N is the number of nodes, if some conditions are satisfied. The shape will be fixed by re-starting the algorithm at children of the failure node.%自律的に，平衡2分木状に，ノード間接続を行う分散アルゴリズムと，それを試験的に実装した構造型P2Pシステムについて述べる．このアルゴリズムは，ノード間がIP reachable で，かつ，ブロードキャスト通信が可能な範囲内で利用できる．ある条件が満たされた場合，N をノード数とするとすべてのノードが接続されるのに必要な時間は0（（log N）~2）となる．任意の節ノードが停止してもその下位ノードでこのアルゴリズムを再起動することにより，再接続が行われる．