具有不同实现的循环 DHT
Circular DHT with different implementations
我在考试中遇到了以下问题：
此问题涉及循环 DHT，其中每个对等节点仅跟踪其前任和后继节点。没有捷径可用。
考虑以下三个结构。在所有这三种构造中，节点 ID 范围
从 0 到 N-1，密钥 ID 也是如此。在给定时间，参与的对等节点的数量
DHT 是 M 并且这个数字很容易为所有对等节点所知。 （键，值）中的“值”
pair 是独立存储感兴趣数据的节点的 ID 集。
C-1：每个存储的（键，值）对（k，v）都存储在一个随机节点（从当时在线的节点中）。
C-2：每个存储的（键，值）对（k，v）存储在一个节点，其ID由k给出mod M.
C-3：每个存储的（键，值）对（k，v）都存储在ID为k的节点（如果它在线）或其最接近的在线后继者（带环绕）。
(a) 一个在线peer想找出一个key k得到对应的value。是什么
在这三种结构中的每一种中，该操作的复杂性（即大 oh O(·)）。如果你是
不熟悉 O( ) 表示法，仅说明发起的平均查询数。
(b) 在线节点发起对密钥 k 的查询并在 return 中获取一组两个节点 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) ^ (n-k)
所以你的答案应该是：
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
我在考试中遇到了以下问题：
此问题涉及循环 DHT，其中每个对等节点仅跟踪其前任和后继节点。没有捷径可用。 考虑以下三个结构。在所有这三种构造中，节点 ID 范围 从 0 到 N-1，密钥 ID 也是如此。在给定时间，参与的对等节点的数量 DHT 是 M 并且这个数字很容易为所有对等节点所知。 （键，值）中的“值” pair 是独立存储感兴趣数据的节点的 ID 集。
C-1：每个存储的（键，值）对（k，v）都存储在一个随机节点（从当时在线的节点中）。
C-2：每个存储的（键，值）对（k，v）存储在一个节点，其ID由k给出mod M.
C-3：每个存储的（键，值）对（k，v）都存储在ID为k的节点（如果它在线）或其最接近的在线后继者（带环绕）。
(a) 一个在线peer想找出一个key k得到对应的value。是什么 在这三种结构中的每一种中，该操作的复杂性（即大 oh O(·)）。如果你是 不熟悉 O( ) 表示法，仅说明发起的平均查询数。
(b) 在线节点发起对密钥 k 的查询并在 return 中获取一组两个节点 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) ^ (n-k)
所以你的答案应该是：
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