You can do incremental deadlock detection in O(1) time per waiter assuming you are okay with treating hash table operations as O(1), so that successful lock acquisition takes O(w) time where w is the number of threads directly or indirectly waiting on the lock-acquiring thread.
A really simple example would be Herlihy's dreadlocks: http://www.unine.ch/transact08/slides/Herlihy-Dreadlocks.pdf. He does lossy deadlock detection using Bloom filters and bit vectors, so it's truly constant time per waiter at the cost of false negatives. But the same idea works for exact deadlock detection if you use concurrent hash tables. The only question is whether you'd want to do that in practice. The overhead of using this as the default mode of operation would absolutely be prohibitive.
But all that is just an aside for your edification, because frankly I don't see anything in the slides that requires instant deadlock detection. He's just asking for a standardized DeadlockError exception that will be thrown to waiting threads involved in a cycle so as to break the deadlock. Most practical deadlock detectors run periodically and that's consistent with what he's requesting.
> And there seems to be some persistent obsession with the Date and Time classes.
Why not? Java's Date/Time classes have a broken design. That's why everyone uses Joda-Time.