I’m trying to implement a modified version of the Lamport Mutual Exclusion algorithm. The original algorithm assumes FIFO message ordering between connected systems, but I would like to use UDP a protocol which does not guarantee FIFO. Is it possible to modify this algorithm to work without FIFO?
EDIT: Forget UDP. Just assume it is some protocol where the only problem is that FIFO is not guaranteed. That is the only problem I’m concerned with right now.
1
Order is the least of your problems. Not only does UDP not guarantee delivery order, it doesn’t guarantee delivery at all.
Lamport’s algorithm requires cooperation of all non-requesting processes that would contend for a resource in the form of replies. The loss of a datagram carrying a request would cause the other processes not to send replies. That or the loss of a single reply would cause the requester to wait indefinitely for something which never arrives.
The only way to modify the algorithm so it would work over an unreliable channel would be to use the same techniques used to implement reliable channels. My advice would be to re-evaluate whether you want to re-invent that wheel or simply switch to TCP, which (reliably) does all that work for you.
7