Kademliaメトリックの変更 - 単方向プロパティの重要性

Question

KademliaはXORメトリックを使用します。とりわけ、これは「単方向」特性（=任意の点xと距離e> 0に対して、d（x、y）= eとなるようにちょうど1つの点yがある）と呼ばれています。

最初の質問は、メデリックのこのプロパティがKademliaの機能に欠かせないのか、それとも特定のノードからの圧力を明らかにするのに役立つものなのか（元の論文が示唆しているように）。言い換えれば、メトリックを変更したい場合は、「一方向性」のメトリックを使用することがどれだけ重要なのでしょうか？

第2の質問は、メトリックの具体的な変更についてです。ノード識別子（アドレス）がXビットの数字であると仮定します。次のメトリックのいずれかがKademliaで使用できますか？

1. d(x,y) = abs(x-y)
2. d(x,y) = abs(x-y) + 1/(x xor y)

のID 90および110を有するノードが均等に離れているので、これは一方向メトリックないノードID 100のために第1のメトリックは、単純に、数の差を提供します。後者の場合、（x xまたはy）が単方向であることが分かっているので、1 /（x xまたはy）を加えることで、1 /（x xまたはy）にこのプロパティを保持する必要があります。

ノードID100の場合、ノードID90はd(100,90) = 10 + 1/62であり、ノードID110からの距離はd(100,110) = 10 + 1/10です。

Answer 1

あなたはもうkademliaを扱わないでしょう。異なる距離メトリック、一部の不均一な距離メトリックを使用する他のルーティングアルゴリズムもありますが、それらはkademlia固有の仮定に依存せず、これらのメトリックの望ましくない側面を補うために他の機能を組み込むこともあります。

メトリックに結びつきがある可能性があるため（各点につき2つの候補）、ルックアップは最も近いノードの正確な集合に収束することができませんでした。

バケット分割およびその他のルーティングテーブルメンテナンスアルゴリズムは、同一の距離がノードIDのみで発生すると想定されるため、変更する必要があります。

Big-Oプロパティやその他のkademliaの保証に影響するかどうかはわかりません。

とにかく、これはX-Yの問題のようです。特定の目標を達成するためにメトリックを変更する必要があります。たぶん、その目標に合わせて設計されたルーティングオーバーレイを念頭に置いて探すべきでしょう。

D（X、Y）= ABS（X-Y）+ 1 /（Xの排他的論理和Y）

これは非現実的と思われる、整数に分割丸め苦しんでいます。実際には、このような小さな数字ではなく、より大きな（例えば160ビット）数字を扱うことになり、部門の費用も高くなります。