Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!sharkey!shadooby!accuvax.nwu.edu!tank!ncar!unmvax!pprg.unm.edu!hc!lll-winken!uunet!ncrlnk!ncrcae!hubcap!wu
From: wu@wahoo.tds.kth.se (Wu Handong)
Newsgroups: comp.parallel
Subject: Is a data flow graph deadlock-free?
Message-ID: <5032@hubcap.clemson.edu>
Date: 6 Apr 89 11:51:51 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 29
Approved: parallel@hubcap.clemson.edu

Is a data flow graph deadlock-free? 
Let us look at an example. Suppose a node N1 has two input arcs which
originate from node a N2 and a node N3 respectively, all the three nodes
are allocated in different processor elements. The node N1 cannot be
executed until receiving tokens from both N2 and N3. If no token sent 
from either N2 or N3, N1 is in waiting state. 
Is the waiting state the same as the dealock state of a logic process 
in the context of distributed simulation?

In distributed simulation a logic process graph is used to represent
a simulated system, a node of the graph is a logic process which communicates
with other logic processes via its input and output channels. One important
issue of distributed simulation deals with maintaining the correct order
of time stamped messages. The conservative method owned to Chandy-Misra
allows a logic process proceed only after all its input channels having
messages. They claim that the logic process is deadlock if no message
arrives on one of its input channels. 

Since we have not considered any deadlock problem of data flow graph so far,
people may believe that a data flow graph is deadlock free.
What is your opinion? 

						
--------                                    ------------
Handong Wu                                    E-mail: wu@tds.kth.se
Dept. of Telecom. & Computer Systems          
Royal Institute of Technolgy
100 44 Stockholm
Sweden