分布式计算机网络[编辑]

分布式计算机系统是一种计算机硬件的配置方式和相应的功能配置方式。它是一种多处理器的计算机系统，各处理器通过互连网络构成统一的系统。系统采用分布式计算结构，即把原来系统内中央处理器处理的任务分散给相应的处理器，实现不同功能的各个处理器相互协调，共享系统的外设与软件。这样就加快了系统的处理速度，简化了主机的逻辑结构，特别适合于工业生产线自动控制和企事业单位的管理，成本低，易于维护，成为计算机在应用领域发展的一个重要方向。

分布式计算是一种把需要进行大量计算的工程数据分区成小块，由多台计算机分别计算，在上传运算结果后，将结果统一合并得出数据结论的科学。

目前常见的分布式计算项目通常使用世界各地上千万志愿者计算机的闲置计算能力，通过互联网进行数据传输。如分析计算蛋白质的内部结构和相关药物的Folding@home项目，该项目结构庞大，需要惊人的计算量，由一台电脑计算是不可能完成的。即使现在有了计算能力超强的超级电脑，但是一些科研机构的经费却又十分有限。

1 一些分布式计算的例子2 主流分布式计算项目列表3 复杂性衡量4 参考资料5 外部链接

[编辑] 一些分布式计算的例子

Climateprediction.net：模拟百年以来全球气象变化，并计算未来地球气象，以对付未来可能遭遇的灾变性天气。D2OL：研究新药物。DPAD：设计粒子加速器。Einstein@Home：于2005年(定为世界物理年)的这一年开始的计划，预计是要找出脉冲星的重力波，验证爱因斯坦的相对论预测。Find-a-Drug：并行运行一系列项目，用来寻找一些危害人类健康的重大疾病的药物。项目目标包括疟疾、艾滋病、癌症、呼吸道系统疾病等等。FightAIDS@home：研究艾滋病的生理原理和相关药物。Folding@home：了解蛋白质折叠、聚合以及相关疾病。GIMPS：寻找新的梅森素数。SETI@home：通过运行屏幕保护程序或后台程序来分析世界上最大的射电望远镜所收到的、可能含有外星智能讯号的射电波。SOB：解决谢尔宾斯基问题。United Devices：综合科学性运算，主攻医药领域，以寻找抗癌药物和天花疫苗为主。Distributed.net：2002年10月7日，以破解加密术而著称的Distributed.net宣布，在经过全球33.1万名电脑高手共同参与，苦心研究了4年之后，他们已于2002年9月中旬破解了以研究加密算法而著称的美国RSA数据安全实验室开发的64位密匙——RC5-64密匙。目前正在进行的是RC5-72密匙。最优Golomb尺问题（OGR）。所谓Golomb尺是指在一个固定整数长度的尺上不等长地划分最少的刻度，并且不存在这样的两对刻度使得每对刻度量出的长度相等的问题。例如OGR-6是在6cm的尺上按0、1、4、6划分刻度，即可连续量度1、2、3、4、5、6cm的每一距离。最优Golomb尺OGR-22、23、24、25(Phase1)均已解决，目前正在进行的是OGR-25(Phase2)。

可参见网格计算。

[编辑] 主流分布式计算项目列表

正在运行中的分布式计算项目Sun Grid Engine - 升阳电脑所研发的分布式计算机集群软件。

[编辑] 复杂性衡量

在并行算法中，对资源的要求除了时间和空间之外，还包括计算机的数量。通常，运行时间和计算机数量之间有个权衡：在并行系统中，更多的计算机会使得问题解决得更加快速（见speedup）。如果一个决策问题通过使用一个多项式数的处理器在综合对数时间内被解决，那么，称这个问题属于NC类。NC类可以用并行随机存取机的形式或者布尔电路来等价——并行随机存取机可以有效地仿真布尔电路，反之亦然。

在分布式算法分析中，人们更加关注的是计算机间的通信而不是算法步骤。同步系统可能算是最简单的分布式系统了，因为它里面所有的节点步调一致。在每一轮通信中，所有节点并行：

（1）从他们邻居节点接受最新消息。

（2）执行任意的本地计算。

（3）给邻居节点发送信息。

在中系统中，核心计算复杂度在于完成任务所需要的同步通信轮数上。

算法复杂度和网络的直径有密切关系。设网络直径为D。一方面，在同步分布式系统中，任何计算问题几乎都可以在2D轮通信之内完成：收集信息到一个本地节点（D轮通信），然后计算，再把计算结果告诉邻居节点（D轮通信）。

另一方面，如果运行时间远远小于D轮通信，这时候，网络中的节点还没来得及获取网络中远处的信息，就得产生输出。换句话说，节点只有在获取了邻居节点之后才能对网络做出决定。很多的分布式算法运行时间都远远小于D轮通信，在这种情况下，明白什么问题能用这类算法来解就是这个领域的核心问题了。

其他的衡量措施是网络上传输的比特总数（cf. communication complexity）。

参考资料：

扩展阅读：