Abstract
Problems considered in distributed systems may be classified into two mainareas: (1) software problems concerned in distributed operating systems,including termination detection, network traversal (graph search),deadlock detection and garbage collection, etc; (2) haardware problemsrelated to network topology, including interconnection networks androuting control algorithms, etc. There are two major parts in thisdissertation, One considers the software problems and the other takes careof the hardware problems.In the first part, we stydy stable properties in distributed systems. Astable state is a state that once a system reaches it will remain in thestate forever if without outside intervention, Stable properties are amongthe most important issues for distributed systerms; for example thetermination detection is a typical problem for detecting stable state indistributed systems. We can classify stable states into two types: desiredstable states and undesired stable states. The desired stable states arethose we hope systems to reach, such as program terminated, systemstabilized, etx. On the other hand, the undesired stable states are thosewe do not like systems to have, such as existence of deadlock processesand garbage processes, etc. Our studies cover these two types of stableproperties, A self-stabilizing algorithm is proposed for constructingbreadth-first trees;it concerns the type of desired stable state. Theproposed algorithm for collecting garbage processes in distributed systemsis the type of detecting undesired stable state.In the second part, we study two types of interconnection networks formultiprocessor systems. It is widely known that message complexity is animportant factor for any multiprocessor system. Hence, those otpologieswhich can support efficient message routing are the most desirable.Because shuffle-exchange networks can provide efficient message-routing,the shuffle connection scheme is intensively used in MultistagedInterconnection Networks (MIN). However, most shuffle-exchange networksdiscussed in the previous works consider only 2x2 switching elements. Wegeneralize the using of 2x2 switching elements to kxk switching elements.We also propose a new class of rearrangeable networks, called cascadeddelta networks, Due to its more generalized link pattern, the proposednetworks cover most of rearrangeable MINs proposed in the literature.本篇中文中介紹了兩種自我穩定性演算法(selfstabilizing algorithm) . 目的乃在分散式系統(distribrted system)中構建樹(trees). 其一為涵蓋樹(spanning tree)，其二為廣度優先樹(breadth-first tree).所謂自我穩定演算法有一個重要性質，那就是無論在任何起始狀態下，無論每一次進行動作的次序選擇如何，系統保證能在有限次動作後達成穩定，即正常狀態legitimate state).在本中文中是介紹涵蓋樹或廣度優先樹的建立．不過給你一個良心的建議，請看英文本．