3
$\begingroup$

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.

Example.

There are 4 processes and they multicast the following messages (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 next week and in general I'd like to understand this mechanism.

$\endgroup$
  • 2
    $\begingroup$ You seem to be misinterpreting the definition. The key questions are: when can a process send a message with timestamp $t$, and when can a received message with timestamp $t$ be delivered to the application? Seeing a large timestamp is good, because it implicitly acks messages with lower timestamps. Take a look at Lamport's paper if you need a different take. scholar.google.com/scholar?cluster=4892527405117123487 $\endgroup$ – András Salamon Apr 20 '14 at 13:35
  • $\begingroup$ I suppose that all the processes receive all messages and queue them before delivering to the application in the order according to their timestamps. In the original algorithm, processes wait for the acknowledgments to the messages from all other processes before delivering these messages to the application layer. But in this case doesn't matter. Thus, the lowest timestamp wins (eventually please refer to my example)? $\endgroup$ – Fabrizio Apr 20 '14 at 15:51
  • $\begingroup$ Could you please offer a complete algorithm rather than just a definition? And how are the timestamps generated? $\endgroup$ – hengxin Mar 24 '15 at 8:09

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.