Ron and Andreas,
I solved this problem in an interesting but very simple way. Our solution was within a database. What we did was commit a lock to the database, then query for the lock, if you get more then one lock back then you remove your lock. In your process you could fail all the way back to the beginning. This has the effect of favoring everyone failing instead of a deadlock. If you can keep the locking time down to a small percentage of overall processing time it should work.
I wonder if to "fail" (or rollback) is an option for Andreas. If so, the two phase locking protocol should work. In such protocol, each process is divided (over time) into two phases. In the first phase, the process acquires all locks it needs, and in the second phase, it only releases locks but never acquire new ones. If the process finds unavailable lock, it aborts.
-- Yoshiki