[cs63201] On the complexity of deadlock detection algorithms

[Mikhail Nesterenko]

> >That is, the worst case message complexity of Obermark's algorithm is
> >the same as that of CMH and it is cubic with respect to the number of
> >processes in the system.
> >
> >thanks,
> >--
> >Mikhail
> >
> >  
> >  
> >
> >
> >
> >Dear Prof. Nesterenko,
> >Are we assuming here that All processes are initiating deadlock detection 
> >concurrently? since we've established the worst case message complexities 
> >for both in class as O(n^2).
> >  

No, it is O(N^3) as this long email indicates. This contradicts
Obermark's estimate (though he uses different assumptions) and CMH
never estimate the complexity of their algorithm.

thanks,
--
Mikhail