Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
Could you elaborate a bit about what's driving your preference for UDP? –  Blrfl Feb 17 '13 at 15:34

1 Answer 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.

share|improve this answer
    
Also note that light-weight protocol above UDP already exists en.wikipedia.org/wiki/RUDP . –  Matěj Zábský Feb 17 '13 at 15:04
    
@MatějZábský: Having read the RUDP draft, it doesn't look that much lighter than TCP. Never having been standardized, the best route would be having to run it in userspace, which has its own set of tradeoffs that the OP would have to evaluate for himself. –  Blrfl Feb 17 '13 at 15:34
1  
+1 for reminding everyone that TCP does these things so we don't have to. I have seen too many occasions where people wanted to use UDP because they couldn't stand (what they thought was) the high overhead of TCP, and then the proceeded to reimplement almost everything TCP does because they needed reliability. –  John R. Strohm Feb 17 '13 at 16:08
1  
@Blrfl We use an user-space implementation of RUDP successfully at our company. The overhead of RUDP is little and in our experience works much better that TCP in conditions with poor connection quality (eg. GPRS in an area with poor cell signal). It is also much simpler to implement (from several hundred lines of code over existing UDP implementation) and has lesser computational overhead (it still lacks many features of TCP) - both of which are massive advantage for embedded devices. Of course, if OP wants to implement heavy-load reliable server application, TCP would probably be better. –  Matěj Zábský Feb 17 '13 at 16:42
    
@MatějZábský: Good to know you've had some success with that. –  Blrfl Feb 17 '13 at 17:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.