After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages are delivered in order and no message is lost. In addition to that, the algorithm uses Lamport logical clock, so the requests will always be processed in order.


1 Answer 1


I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section.

If $S_i$ sends a critical section request to $S_j$, but $S_j$ never requests the critical section and doesn't send a reply, $S_i$ will never receive a message from $S_j$ thus causing it to wait forever to enter the critical section. In this scenario, $S_i$ cannot know for sure that $S_j$ does not have a pending request with a timestamp lower than $S_i$'s request.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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