A minimum time algorithm for the graph construction and the leader election problems in a distributed system

Given an asynchronous distributed system with an arbitrary topology, in which each site has unique identifier, this paper considers the graph construction problem that asks for each site to construct the entire graph representing the system topology, and the leader election problem that asks to find the site with the largest identifier. A distributed algorithm is proposed in this paper to solve the above two problems with 2m²-mn+2m message complexity under the constraint that the time span until all sites know the solution is minimum, where n and m are the numbers of sites and links in the system, respectively. Furthermore, it is shown that any distributed algorithm for solving the graph construction problem with the minimum time span requires at least m(m+1) messages. This means that the above algorithm is optimum in the sense of the order of message complexity. [In Japanese.]