<p>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</p>
<blockquote>
<p>&quot;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.&quot;</p>
</blockquote>
<p>This is a definition from a book. I tried to apply this definition to an example but I guess that something is wrong.</p>
<h3>Example.</h3>
<blockquote>
<p>There are 4 processes and they multicast the following messages (the second number in parentheses is timestamp) :<br />
P1 multi-casts (m11, 5);  (m12, 12); (m13, 14);<br />
P2 multi-casts (m21, 6); (m22, 14);<br />
P3 multi-casts (m31, 5); (m32, 7); (m33, 11);<br />
P4 multi-casts (m41, 8); (m42, 15); (m43, 19).</p>
</blockquote>
<p>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.</p>

CC BY-SA 3.0
2014-04-15T11:28:42.447Z
This is a nice question, but it is more suitable for CS.SE.
András Salamon
CC BY-SA 3.0
2014-04-15T12:44:23.900Z
What is CS.SE ? Sorry for ignorance.
Fabrizio
CC BY-SA 3.0
2014-04-15T13:05:24.327Z
CS.SE is our sister site [cs.se] 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."
András Salamon
CC BY-SA 3.0
2014-04-15T14:00:12.863Z
@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)?
Sasho Nikolov
CC BY-SA 3.0
2014-04-20T13:30:06.707Z
@Sasho: this seems to be a basic question about how Lamport clocks work.  Lamport's 1978 CACM paper is widely cited and is a basic mechanism in most distributed systems: there seems to be nothing research level in the question.
András Salamon
CC BY-SA 3.0
2014-04-20T13:30:59.793Z
Cross-posted to https://cs.stackexchange.com/q/23847
András Salamon
<dc.distributed-comp>
Totally ordered multicast with Lamport timestamps
Fabrizio
# Totally ordered multicast with Lamport timestamps

(Asked by: username_0 on 2014-04-15)

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 (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.

**Tags:** dc.distributed-comp

> **Comments:**
> **username_1**: This is a nice question, but it is more suitable for CS.SE.  
> **username_0**: What is CS.SE ? Sorry for ignorance.  
> **username_1**: CS.SE is our sister site [cs.se] 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."  
> **username_2**: @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)?  
> **username_1**: @Sasho: this seems to be a basic question about how Lamport clocks work.  Lamport's 1978 CACM paper is widely cited and is a basic mechanism in most distributed systems: there seems to be nothing research level in the question.  
> **username_1**: Cross-posted to https://cs.stackexchange.com/q/23847  

---

## 0 answers

