如何估算 P2P 网络中的节点总数？
How to estimate total number of nodes in a P2P network?
我正在创建一个没有主节点的 p2p 网络。如何统计活节点总数？精度不是关键，但轻便和性能很重要。
目前我在想两种方法，它们都有很大的缺点...
每个节点都有一个随机数作为其ID。每个节点都有一个巨大的位数组，最初只有索引 == ID 处的位为 1，其他位为 0。每个节点都与已知的对等节点交换它的位数组。使用位或将节点的位数组与对等节点合并。随着这个过程的进行，最终每个节点都应该有相似的位数组，1的数量表示网络中的节点数量。优点是这可以并行地并且随着时间完成。在查询时，响应会非常快（因为结果已经存在）。缺点：a)。难以处理消失的节点。 b).如果有数百万个节点，位数组太大。
类似于 BFS。从初始节点开始，它会询问所有已知的对等点连接了多少个节点。然后将所有响应相加作为待探测网络的总大小。这是一种递归方法。如果一个节点已经收到这样的查询，它将忽略来自其他节点的进一步相同的查询。就像 BFS 一样。缺点是这很可能不准确。查看 BFS 树，对于每个节点，它都可能是单点故障，这会导致该节点的所有查询丢失。考虑从节点 A 初始化查询，查询连接的对等点 B 和 C。然后 B 和 C 将查询传播到它们连接的网络。由于某种原因C发生故障，无法响应A。那么所有收到C直接或间接查询的节点都不会被统计。这个问题可能发生在网络的任何节点上，并可能导致最小的不准确性或很大的不准确性，如上述方法，可能是网络的 50%。
知道如何实际估算 P2P 网络中的总节点数吗？
没有完美的方法。如果关键部分上有一个节点不稳定（经常上下波动），那么您很可能会因此而错过网络的一部分，并且不知道该部分有多大。即使假设网络连接良好，也很难给出正确的计数，因为网络状态可能会在算法为 运行.
时发生变化
您可能不想要第二种方法，因为您将更多权重放在靠近起点的节点上，就像您说的那样。
但是，第一种方法有不同的看法，它以牺牲一定的准确性为代价消除了太长的位数组。
这个想法非常相似，但不必计算所有节点（您的 ID 必须是唯一且相当连续的）和一个非常大的位数组，您可以有随机 ID（每台机器随机选择一个 32/64 bit id) 而不是传递 bloom 过滤器和计数器的位数组。布隆过滤器类似于数组，因为它可以判断 id 是否尚未插入。然而，它 space 更有效。缺点是虽然它有 100% 的召回率（如果过滤器说 id 不存在，它确实不存在）它没有 100% 的精度（过滤器可能说 id 已被插入但实际上它不是）。对于该算法，这意味着您一定会避免重复计算（好），但根据插入的顺序，您可能会错过一些节点。
算法的其余部分是相同的。首先插入您自己的 ID 并将计数器设置为 1。将状态发送给所有对等点。当你收到一个状态时，检查你的 id 是否已经被插入，如果没有插入它，加 1 并将状态发送给你所有的对等体。如果您有相同的布隆过滤器状态但计数不同，请选择较大的一个（因为我们确定不会重复计算）。最终状态会趋于一致，这就是你的答案。
Here's link 关于布隆过滤器的工作原理。
如果您有 DHT 或类似的覆盖网络（您可能有，否则您将如何拥有纯分布式网络？），您可以通过查看小型子系统中的 ID 分布来估计其大小-space 的 ID space。你的方法本质上是试图准确，所以它们最终是不切实际的。仅查看 ID space 的一部分并得出关于其余部分的结论通常显然不准确，它仅在 ID 是随机的并且您知道足够多的节点可以调用大定律的情况下才有效数字。如果您保留适当的路由表，您可以纯粹在本地进行此估计，但如果您的查询允许，您可以决定询问接近某个随机生成的 ID 的节点，现在您有两个可以平均的估计（但这是一个昂贵的技巧） .有许多论文介绍如何使它对某些攻击更具弹性，在高流失率的情况下更准确，并使用实际的估算公式。
我正在创建一个没有主节点的 p2p 网络。如何统计活节点总数？精度不是关键，但轻便和性能很重要。
目前我在想两种方法，它们都有很大的缺点...
每个节点都有一个随机数作为其ID。每个节点都有一个巨大的位数组，最初只有索引 == ID 处的位为 1，其他位为 0。每个节点都与已知的对等节点交换它的位数组。使用位或将节点的位数组与对等节点合并。随着这个过程的进行，最终每个节点都应该有相似的位数组，1的数量表示网络中的节点数量。优点是这可以并行地并且随着时间完成。在查询时，响应会非常快（因为结果已经存在）。缺点：a)。难以处理消失的节点。 b).如果有数百万个节点，位数组太大。
类似于 BFS。从初始节点开始，它会询问所有已知的对等点连接了多少个节点。然后将所有响应相加作为待探测网络的总大小。这是一种递归方法。如果一个节点已经收到这样的查询，它将忽略来自其他节点的进一步相同的查询。就像 BFS 一样。缺点是这很可能不准确。查看 BFS 树，对于每个节点，它都可能是单点故障，这会导致该节点的所有查询丢失。考虑从节点 A 初始化查询，查询连接的对等点 B 和 C。然后 B 和 C 将查询传播到它们连接的网络。由于某种原因C发生故障，无法响应A。那么所有收到C直接或间接查询的节点都不会被统计。这个问题可能发生在网络的任何节点上，并可能导致最小的不准确性或很大的不准确性，如上述方法，可能是网络的 50%。
知道如何实际估算 P2P 网络中的总节点数吗？
没有完美的方法。如果关键部分上有一个节点不稳定（经常上下波动），那么您很可能会因此而错过网络的一部分，并且不知道该部分有多大。即使假设网络连接良好，也很难给出正确的计数，因为网络状态可能会在算法为 运行.
时发生变化您可能不想要第二种方法，因为您将更多权重放在靠近起点的节点上，就像您说的那样。
但是，第一种方法有不同的看法，它以牺牲一定的准确性为代价消除了太长的位数组。
这个想法非常相似，但不必计算所有节点（您的 ID 必须是唯一且相当连续的）和一个非常大的位数组，您可以有随机 ID（每台机器随机选择一个 32/64 bit id) 而不是传递 bloom 过滤器和计数器的位数组。布隆过滤器类似于数组，因为它可以判断 id 是否尚未插入。然而，它 space 更有效。缺点是虽然它有 100% 的召回率（如果过滤器说 id 不存在，它确实不存在）它没有 100% 的精度（过滤器可能说 id 已被插入但实际上它不是）。对于该算法，这意味着您一定会避免重复计算（好），但根据插入的顺序，您可能会错过一些节点。
算法的其余部分是相同的。首先插入您自己的 ID 并将计数器设置为 1。将状态发送给所有对等点。当你收到一个状态时，检查你的 id 是否已经被插入，如果没有插入它，加 1 并将状态发送给你所有的对等体。如果您有相同的布隆过滤器状态但计数不同，请选择较大的一个（因为我们确定不会重复计算）。最终状态会趋于一致，这就是你的答案。
Here's link 关于布隆过滤器的工作原理。
如果您有 DHT 或类似的覆盖网络（您可能有，否则您将如何拥有纯分布式网络？），您可以通过查看小型子系统中的 ID 分布来估计其大小-space 的 ID space。你的方法本质上是试图准确，所以它们最终是不切实际的。仅查看 ID space 的一部分并得出关于其余部分的结论通常显然不准确，它仅在 ID 是随机的并且您知道足够多的节点可以调用大定律的情况下才有效数字。如果您保留适当的路由表，您可以纯粹在本地进行此估计，但如果您的查询允许，您可以决定询问接近某个随机生成的 ID 的节点，现在您有两个可以平均的估计（但这是一个昂贵的技巧） .有许多论文介绍如何使它对某些攻击更具弹性，在高流失率的情况下更准确，并使用实际的估算公式。