Completely Distributed Algorithm for Measurement Collaboration Problem
Qi Wu · Chinese Journal of Computers · 2004
Measurement Collaboration Problem (MCP) is a kind of distributed collaboration problem with tasks having confliction, which is a class of particular resource distribution problem. Its particularity lies in that: (1)resources negotiate about which process (or task) should be triggered; (2)if the resource demand of a task can’t be satisfied, the task should be given up. After having studied the arbitrator-based solution, authors present a Completely Distributed Algorithm (CDA) in this paper. They also prove the aliveness and correctness of CDA, and finally analyze the message complexity, space complexity and convergence time. Compared with the arbitrator-based algorithm, CDA can be used in the system with larger scale. To validate the efficiency of CDA, authors put forward Single Wait State Algorithm (SWSA) and a simulation experiment. The experiment indicates that, in the course of a large scale of measurement, when the concurrent number of measurement tasks created randomly is small, CDA has no better efficiency than SWSA. But with the increase of concurrent number, CDA gradually has higher efficiency. It also shows that CDA has much better ability of dealing with conflict tasks than SWSA. With the portion of conflicted tasks increasing, the efficiency of CDA even slightly increases. CDA can also be utilized in many aspects, such as disaster rescue, distributed agent collaboration, object position and so on.