[科普中国]-分布式问题求解

系统的协作方式

分布式问题求解系统有两种协作方式：任务分担和结果共享。在任务分担系统中，节点之间通过分担执行任务而相互协作，系统中的控制以目标为指导，各节点的处理目标是求解整个问题的一部分。在结果共享系统中，各节点通过共享部分结果相互协作，系统中的控制以数据为指导，各节点在任何时刻进行的求解取决于当时它所拥有的或从其他节点得到的数据和知识。

任务分担方式适合于求解具有层次结构的任务，如数字逻辑电路设计、医疗诊断等。结果共享方式适合于求解与总任务有关的各子任务的结果相互影响，并且部分结果需要综合才能得出最终解的问题，如分布式运输调度系统、分布式车辆监控实验系统等。

组织结构分布式问题求解系统的组织结构，是指节点之间信息与控制关系以及问题求解能力在节点中的分布模式。组织结构可分为层次、平行、混合三大类型。

（1）层次类型

层次类型的系统中，任务是分层的，即每个任务由若干下层子任务组成。但同层子任务之间在逻辑上或物理上是分布的。

（2）平行类型

平行类型的系统中，任务是平行的，即每个任务由性质类似，具有平行关系的若干子任务组成。但各个子任务在时间或空间上往往是分布的。

（3）混合类型

混合类型的系统中，任务是分层次的，而每层中的任务是并行的。同时，各个子任务是分布的。

问题求解过程问题求解过程可分为四步：任务分解、任务分配、子任务求解以及结果综合。各个步骤的工作分别由任务分解器、任务分配器、求解器和协作求解系统完成。任务分解器按一定的算法将接受的任务分解为若干相对独立、又相互联系的子任务，并将它们交给任务分配器。任务分配器按一定的分配算法将接受的各个子任务分配到合适的节点。各求解器接到子任务后，借助通信系统进行协作求解，并将局部解提交给协作求解系统，由协作求解系统将局部解综合成最终解。

任务分解和任务分配涉及到优化问题，一种典型的方法是合同网络的方法，即任务分配节点以合同招标的形式，选择任务执行节点的方法。2