具有不同实现方式的循环DHT

提基(El tikki)

我的考试中有以下问题:

此问题涉及循环DHT,其中每个对等节点仅跟踪其前任和后任。没有快捷方式可用。考虑下面的以下三种构造。在所有这三种构造中,节点ID的范围从0到N-1,密钥ID的范围也是如此。在给定的时间,参与DHT的对等节点的数量为M,并且所有对等节点都容易知道该数量。(键,值)对中的“值”是独立存储感兴趣数据的节点的ID集合。

C-1:每个存储的(键,值)对(k,v)都存储在一个随机节点上(然后是在线的)。

C-2:每个存储的(键,值)对(k,v)都存储在ID由k mod M给出的节点上。

C-3:每个存储的(键,值)对(k,v)都存储在ID为k(如果在线)或与其最接近的在线后继者(带有环绕)的节点上。

(a)在线对等方想要找出密钥k以获取相应的值。在这三种构造中的每一种构造中,此操作的复杂度(即,大O())是多少?如果您不熟悉O()表示法,则只需说明启动查询的平均数量即可。

(b)在线节点启动对密钥k的查询,并获得两个节点ID的集合作为回报。那些节点中的至少一个节点在线的机会是什么(以便查询节点可以获取感兴趣的数据)?提供您对每种构造的答案;您的答案可能是用k,M,N或任何其他参数表示的。

(c)如果平均有30%的节点在线,您对以上部分(针对每个结构)的(数字)答案是什么?

我对我写的答案感到困惑。我想知道我做的是否正确。我写了以下答案:

a)C1:O(N)-如果有N个在线节点

C2:O(M)-在键从0到M-1的情况下

C3:O(1)-密钥为k的最坏情况节点处于脱机状态,着眼于下一个

b)p =上网的概率

C1:2C1 * p *(1-p)+ 2C2 * p

C2:2C1 * p *(1-p)+ 2C2 * p

C3:2C1 * p *(1-p)+ 2C2 * p

c)C1:2C1 * 0.3 * 0.7 + 2C2 * 0.3

C2:2C1 * 0.3 * 0.7 + 2C2 * 0.3

C3:2C1 * 0.3 * 0.7 + 2C2 * 0.3

鲨鱼

a)对于C1,您已经陈述了M = N的情况的答案,该答案可能并不总是成立,因此您应将其更改为O(M),因为它将搜索所有在线节点,因为它们中的任何一个都可以将密钥保存在随机的。

C2:O(M)以及您陈述的原因都是正确的。

C3:这也将是O(M),因为平均而言,您将不得不遍历整个DHT来找到密钥。

b)您对二项式定理使用了错误的公式。正确的公式是:

nCk * p ^ k *(1-p)^(nk)

因此,您的答案应该是:

C1:2C1 * p *(1-p)+ 2C2 * p ^ 2

C2:2C1 * p *(1-p)+ 2C2 * p ^ 2

C3:2C1 * p *(1-p)+ 2C2 * p ^ 2

另外,请注意,此处p = M / N(因为M个节点从N个节点在线)

c)现在p = 0.3

C1:2C1 * 0.3 * 0.7 + 2C2 * 0.3 ^ 2 = 0.51

C2:2C1 * 0.3 * 0.7 + 2C2 * 0.3 ^ 2 = 0.51

C3:2C1 * 0.3 * 0.7 + 2C2 * 0.3 ^ 2 = 0.51

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章