Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!lll-winken!uunet!ncrlnk!ncrcae!hubcap!segall
From: segall@caip.rutgers.edu (Ed Segall)
Newsgroups: comp.parallel
Subject: Re: Is a data flow graph deadlock-free?
Message-ID: <5048@hubcap.clemson.edu>
Date: 10 Apr 89 12:15:55 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 28
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?

This is not necessarily deadlock.  The critical issue is what you mean
by "If no token [is] sent from either N2 or N3...".  For example, if a
token will eventually be sent from N2 and N3, then N1 is simply
waiting, no more.  If however, N2 or N3 will never send another
token, this may or may not be deadlock. 

One case in which this is not deadlock is if the program has
terminated.  Just because a node will never fire again doesn't mean
the program is deadlocked.  In order for deadlock to occur,
termination must depend on a node's firing, and it must be the case
that that node will never fire again.  


--Ed
-- 


uucp:   {...}!rutgers!caip.rutgers.edu!segall
arpa:   segall@caip.rutgers.edu