如何计算网络节点的平均值(或和)?

假设网络中有数量未知、有限个、足够多的节点,每个节点上有个值,这些节点应如何交互,才能使得每个节点都知道整个网络上各个节点值的均值(或和)?

“数量未知”是说网络节点的数量N是未知的,不过给出一个假设N已知的算法也行。
“有限个”是说不需要考虑溢出/发散的问题。
“足够多”是说,如果你想要让每个节点先把所有节点的值记下来再求均值/和的话,那么有足够多的节点让你记不下来(同理你也不能完全记录你收到了谁的值)。

网络的拓扑是非完全图,其他的如果算法需要什么假设都可以加。
最弱的假设应该是每个节点都能收到其他节点发来的信息(如果其他节点帮忙转发的话),也就是有向图里有一条遍历所有节点的环路。

最后我不知道这算是哪个领域的东西,分布式计算?图论?分布式图算法?有类似的问题应该去看哪里的东西么?

推荐  (0) | 1人关注关注
1个答案
6 0

方弦科学松鼠会成员,信息学硕士生

2015-06-26 03:28

这应该属于分布式网络算法的内容。具体有没有书不知道,但是我以前上的硕士课程里有开这样的一门课(我没去上过):https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-18-1

因为没具体学过,所以不能立刻回答你的问题。不过我知道这是可以做到的,比如说先选举一个带头节点,然后让带头节点帮大家计算。选举算法有现成的,后面就很容易了。当然这应该不是最好的算法,但是凑合着用也可以。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区