ASYNCHRONOUS ALGORITHMS FOR DISTRIBUTED PROCESSING (PARALLEL, PROBLEM SOLVING, BLACKBOARD, TEAM APPROACH, BRANCH, BOUND

Of the three levels of distributed processing--distributed architectures, systems, and applications--the application level has received the least attention while the first two levels have made rapid advancement in recent years. To make full use of the potential provided by the distributed processing, one must look at the application level of distributed processing.;Algorithms are divided into three groups: Strongly synchronous (SS), weakly synchronous (WS), and asynchronous (AS). WS and AS algorithms, because they are well suited to distributed processing, are attractive for computationally intensive areas. However, these algorithms are seldom employed because they are unfamiliar and good paradigms have been unavailable for their use.;This research is an attempt to provide an algorithmic approach in distributed processing. Essentially this research has attempted to develop systematic ways of generating asynchronous algorithms suitable for distributed processing. Two approaches are suggested in this thesis: the ULD (use the latest data) mechanism and the team approach.;The ULD mechanism is a powerful tool for decomposing synchronous algorithms into asynchronous ones. A class of asynchronous iterative algorithms is described by the ULD mechanism, and their convergence results are provided.;The team approach is a means of assembling a distributed asynchronous algorithm by combining existing algorithms. Because of the heuristic nature of this approach, formal theoretical treatment was not attempted. Rather, the usefulness of the team approach is demonstrated through examples.;Processes of an asynchronous algorithm use communication as the only means of cooperation. Because of the communication bandwidth limitation exhibited by distributed systems in general, an efficient communication medium is required for the success of asynchronous algorithms. In this thesis we used the blackboard as a communication medium for asynchronous processes.;Finally, a distributed branch and bound algorithm is developed to solve a class of combinatorial optimization problems. The algorithm employs both the ULD mechanism and the team approach. We experimented with an implementation of this on an existing distributed system SPICE for the zero-one integer linear programming problem. The result of this experiment shows that these approaches are indeed a powerful tool for developing asynchronous algorithms for distributed processing.