I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the application, but

"It is sufficient to multicast any other type of message, as long as that message has a timestamp larger than the received message. The condition for delivering a message m to the application, is that another message has been received from each other process with a large timestamp. This guarantees that there are no more messages underway with a lower timestamp."

This is a definition from a book. I tried to apply this definition to an example but I guess that something is wrong.


There are 4 processes and they multicast the following messages (the second number in parentheses is timestamp) :
P1 multi-casts (m11, 5); (m12, 12); (m13, 14);
P2 multi-casts (m21, 6); (m22, 14);
P3 multi-casts (m31, 5); (m32, 7); (m33, 11);
P4 multi-casts (m41, 8); (m42, 15); (m43, 19).

Supposing that there are no acknoledgments, can I guess which messages can be delivered and which not? Based on definition, my guess is that only m11 and m31 can be delivered to the application, because all the other messages received will have a timestamp greater, but this seems very strange, and I think I didn't understand the delivery condition very well. I have an exam on Tuesday about this, but anyway I would understand this mechanism.

  • $\begingroup$ This is a nice question, but it is more suitable for CS.SE. $\endgroup$ – András Salamon Apr 15 '14 at 11:28
  • $\begingroup$ What is CS.SE ? Sorry for ignorance. $\endgroup$ – Fabrizio Apr 15 '14 at 12:44
  • $\begingroup$ CS.SE is our sister site Computer Science for general computer science questions and answers. In contrast "Theoretical Computer Science - Stack Exchange is a question and answer site for professional researchers in theoretical computer science and related fields." $\endgroup$ – András Salamon Apr 15 '14 at 13:05
  • $\begingroup$ @AndrásSalamon The question seems to be about TCS. Are you saying it's not research level (for me it's hard to judge this for distributed computing questions)? $\endgroup$ – Sasho Nikolov Apr 15 '14 at 14:00
  • 1
    $\begingroup$ Cross-posted to cs.stackexchange.com/q/23847 $\endgroup$ – András Salamon Apr 20 '14 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.