如何计算分布式系统中发送的消息数量？

Question

假设我们有 n 个进程形成一个通用网络。我们不知道哪些进程连接在一起，但我们知道进程的数量 (n)。如果在每一轮，一个进程向它连接的所有进程发送一条消息，从每个进程接收 1 条消息，并且程序执行了r轮，有没有办法知道程序执行期间发送了多少条消息？

Answer 1

正如您所指出的，如果没有确切的网络结构，就不可能对发送的消息数量给出具体的值。相反，我们可以看看它的 Big-O 值。

现在要清楚我们所说的 Big-O 的含义：

• Big-O 指的是上限（即最坏的可能情况）复杂度
• 有可能（并且在实际系统中很可能）实际值会更少
• 如果没有一些描述平均情况的函数（例如，每个进程平均连接到 N / 2 个其他进程），我们必须假设最坏的情况
• 通过“最坏的情况”为此问题我们的意思是发送的消息的最大数量

所以让我们假设最坏的情况，其中每个进程都连接到 N - 1 个其他进程。

我们还定义一些变量：

• S := 进程集合
• N := S 中的进程数量

我们可以表示集合 < code>S 作为一个完整的（每个节点都连接到每个其他节点）无向图，其中图中的每个节点对应一个进程，图中的每条边对应于 2 个发送的消息（1 个传出传输和一个回复）。

从此处，我们看到完整图中的边数为(N( N-1))/2

所以在最坏的情况下，发送的消息数量是N(N-1)，或者N^2 - N 。

现在，因为我们正在处理 Big-O 表示法，所以我们感兴趣的是这个值如何作为 N 的函数增长。

通过三角不等式，我们可以看出O(N^2 - N)是O(N^2)的一个元素。

因此，在最坏的情况下，发送的消息数量会增长为 N^2。

---

也可以使用邻接矩阵得出此结果，即一个 N x N 矩阵，其中 (i, j) 中的 1 code>th 元素指的是从节点i 到节点j 的边。

因为在最初的问题中，每个进程都会向所有连接的进程发送一条消息，而这些进程则用一条消息进行响应，因此我们可以看到，对于每对 (i, j) 和 (j, i ） 将有一条边（一条代表传出消息，一条代表回复）。例外情况是 i = j 的对，即。我们的进程不会向自己发送消息。
因此，除了对角线之外，矩阵将完全被 1 填充。

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

上图：N = 4 的邻接矩阵。

因此，我们首先要确定一个公式，将发送的消息总数作为节点数量的函数。

通过矩形的面积，我们可以看到矩阵中1的数量（忽略对角线）将为N x N = N^2。
现在我们必须考虑对角线。可以存在的对(x, x)的数量由函数f(i)给出，其中Z(N) -> Z(N) x Z(N) : f(i) = (i, i) ——这意味着该函数将有 N 个不同的解。

因此，总体结果是，当考虑对角线时，我们有 N^2 - N 消息。

现在，我们使用与上面相同的 Big-O 推理来得出相同的结论，消息数量在最坏的情况下增长为 O(N^2)。

---

因此，现在您只需要考虑已发生的轮数，剩下的就是 O(RN^2)。

当然现在你必须考虑你是否真的遇到了最坏的情况......