Shortest route computation in distributed systems

摘要

This paper presents a polynomial time algorithm for computing the shortest route in distributed systems. A distributed system is composed of autonomous subsystems and a central computing server. A subsystem stores and maintains its own data, and is obligated to provide the central computing server with the information about its intersections with other subsystems. The approach presented in this paper is for the central computing server to compute the shortest route that crosses subsystems based on the partial local information provided by the subsystems. It is the first efficient algorithm that guarantees to find the shortest route in such a distributed system.