| Abstract: | This thesis addresses election and termination detection problems in specialized communication structures. Three communication structures; namely, composite complete network (i.e., a complete network whose size is composite), recursively scalable network and H-mesh, are examined. The objective in considering composite complete networks is to investigate the effect on the message complexity of the election algorithms when N the size of the complete network is composite. Specifically, it is shown that when N is a multiple of 2, 3, 4, 5, or 6, the message complexity of the existing election algorithm for the complete network can be improved. To this end, an hybrid approach to designing election algorithms for complete networks with a sense of direction is developed when N is composite. The approach is based on a well-known divide and conquer paradigm for problem solving. The objective in considering recursively scalable networks and H-meshes is to utilize the underlying communication structure as a guiding factor in the development of election and termination detection algorithms. Furthermore, these communication structures are recently analyzed and are employed as interprocessor communication architectures in the development of message passing multiprocessor systems. An election algorithm in a synchronous recursively scalable network is designed by making use of its hierarchical communication structure. It requires less than 4.5N messages and the running time is at most 2.75$\sqrt{N}$ where N is the number of processors in the network. A termination detection algorithm in a H-mesh is developed. It is based on the propagation of passive state information and on the probe passing technique. Traffic rules for probes and passive state information are designed by making use of the structure of the H-mesh. The correctness proof for the termination detection algorithm is also presented. |