在分布式系统中发送的消息

Question

假设我们有n个进程组成一个通用网络。我们不知道哪些连接在一起，但是我们知道进程的数量（n）。如果在每一轮中，进程向它所连接的所有进程发送消息，从它们中的每一个接收1条消息，并且程序执行循环，有没有办法找到程序执行过程中发送了多少条消息？

Answer 1

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

现在只是要弄清楚我们所说的大O：

• 大O是指上限（即最坏的情况）的复杂性
• 这是可能的（和在实际系统中很有可能），实际值会少
• 没有描述平均情况下，一些功能（如每道工序都连接到平均N/2其他进程），我们必须假设最坏的情况下
• 通过“最坏的情况”对于这个问题，我们的意思是消息的最大数量发送

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

我们还定义了一些变量：

• S：=的进程集
• N：=的过程中S

我们可以表示一组S的数量完成（每个节点连接到每个其他节点），无向图，其中图中的每个节点对应一个进程，并且图中的每条边对应于2条发送的消息（1个传出传输和一个回复）。

从here，我们看到，在一个完全图的边数为(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指的是从节点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 s的数量（忽略对角线）将为N x N = N^2。 现在我们必须考虑对角线。对(x, x)，可以存在由函数f(i) where Z(N) -> Z(N) x Z(N) : f(i) = (i, i)给定的数 - 这意味着会有正好N个不同的解决方案，以该功能。

所以总的结果是，我们有N^2 - N消息时对角被认为是。

现在，我们用同样的大O推理从上面到了相同的结论到达，邮件数量的增长在最坏的情况下为O(N^2)。

---

所以，现在你只需要考虑发生的回合数，给你留下O（RN^2）。

当然，现在你必须考虑你是否真的有最坏的情况下...