分布式计算

在計算機科學中，分布式计算（英语：Distributed computing，又譯為分散式計算）這個研究領域，主要研究分散系統（Distributed system）如何進行計算。分散系統是一組電子計算機（computer），透過計算機網路相互連結與通訊後形成的系統。把需要进行大量计算的工程数据分割成小块，由多台计算机分别计算，在上传运算结果後，將結果统一合并得出数据结论的科学。

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

概論

分布式計算，平行運算與並行運算是三個概念相近但不同的術語。

一些分布式计算的例子

• 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）。

外部链接

• 中国分布式计算总站
• 中国分布式计算论坛