0Distributed Deadlock Detection forDistributed Process NetworksAlex OlsonAbstractThis paper presents a discussion of the Kahn process network (PN) model and the challengesin distributing it onto multiple networked workstations. Compared to a non-distributed PN model, adistributed PN model is more scalable in terms of performance and has significantly lower cost. Althoughadditional distribution-specific challenges exist, existing distributed systems algorithms can solve them.An original contribution of this paper is a distributed process network implementation that performsdeadlock detection.Index TermsParallel, Concurrent Programming, Distributed Programming, Models of Computation, Processnetworks, distributed deadlock detection, KahnDRAFT April 2, 20040CONTENTSI Context of Research 1II Objectives 1III Existing Theoretical Work 2III-A Process Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2III-A.1 Kahn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2III-A.2 Parks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2III-A.3 Geillen & Basten . . . . . . . . . . . . . . . . . . . . . . . . . 3III-B Problems in Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 4III-C Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5III-C.1 Distributed Deadlock Detection . . . . . . . . . . . . . . . . . . 5III-C.2 Distributed Mutual Exclusion . . . . . . . . . . . . . . . . . . . 6IV Existing Implementations 7V Implementation Plan 7VI Conclusion 7References 8DRAFT April 2, 20041I. CONTEXT OF RESEARCHThere are a variety of approaches for high-performance computing. Many of these rely onexploiting the available parallelism in a computation and are highly effective. One can attemptto find parallelism by examining program code, as done by modern compilers & processors.Another way is to initially design the computation with parallelism in mind, by starting with ahighly parallelizable model. One such model is Kahn’s process network (PN) [1], which involvesthe idea of parallel processes communicating over one-way channels.The beauty of Kahn’s model lies in its simplicity. It guarantees determinism only basedupon the flow of data – not relying on timing, mutual exclusion, or any other synchronizationmechanism. The process network model is highly suitable for signal processing applications.For targeting desktop computers, several PN frameworks exist. All of these tend to map pro-cesses onto threads. Thus, symmetric-multiprocessor computers (SMP) can be used to achievehigh-performance. Recently, Allen used [2] the process network model to perform real-timesonar beamforming on a UNIX workstation. However, SMP desktops are becoming extremelyexpensive. Currently, the price of multiple single CPU workstations equals the price one SMPworkstation, and they offer greater combined performance. In addition, gigabit networking isbecoming affordable. It is no wonder the idea of cluster computing is becoming popular. Thus,it is desirable to have a distributed process network framework (DPN). Such a framework allowsfor greater performance and reduced cost over PN implementations on single SMP desktops.Unfortunately, few DPN frameworks exist and they are only in early stages of development.II. OBJECTIVESThe primary objective of this project is to research and design a high-performance distributedprocess network framework. Such a framework should implement deadlock detection, dynamicprocess migration, and load balancing. Deadlock detection is necessary to detect terminationand/or the condition of a buffer being too small. This will be explained in section III. Dynamicprocess migration refers to the ability to relocate a process from one workstation to anotherat runtime. This capability is useful should the need arise to add or delete a workstation fromthe network at run-time. It is also a highly useful capability for the implementation of dynamicload balancing. With process networks, the behavior of any process is not statically predictable.Thus, dynamic load balancing could be highly beneficial for ensuring maximum performance.April 2, 2004 DRAFT2However, the scope of this paper will be limited to a discussion of process networks, problemsin distribution, and plans for distributed deadlock detection.III. EXISTING THEORETICAL WORKA. Process Networks1) Kahn: In 1974, Kahn proposed [1] a determinate model of computation based on datatokens (and their flow). The term token is a general term for any unit of data. He suggestedthat multiple processes executing concurrently and communicating over channels could performa computation. The only requirements of his channels are that they be reliable FIFO queuesbut may be unbounded in length. Thus, the queues provide a loose coupling between producers(processes emitting tokens) and consumers (processes receiving tokens).One can visualize Kahn’s model as a group of processes which each consume (read) oneor more tokens from one or more inputs and produce (write) one or more tokens to one moreor more outputs. If a process attempts to read more tokens than are available on a channel,the process blocks until enough tokens are available. A process only blocks on at most onechannel at a time. In addition, a process may not to test a channel for the presence of tokens.However, a process enjoys a great deal of freedom; it can read and/or write tokens at any time.Additionally, a process with multiple inputs and/or multiple outputs is not required to performa read or write on all ports. As simple as these rules are, they do guarantee determinism. InKahn’s model, global deadlock only occurs when a computation terminates, and local deadlockis impossible. At termination, all processes are blocked on reads and all channels are empty.Another nice feature of this model is that it is completely independent of time. As long as allprocesses eventually have the opportunity to make progress, it doesn’t matter if some processesrun faster, receive more CPU time, or if they execute in varying orders. The sequence of tokensproduced at all processes will be unaffected. Kahn also guarantees that his model producescomplete output, regardless of scheduling. The simplicity and determinacy of process networksmakes it an extremely attractive model for distributed computations, especially in heterogeneousenvironments.2) Parks: There is one main drawback to Kahn’s model – it relies upon unbounded