<div dir="ltr">What I said was "message passing is assumed to be reliable" <div><br></div><div>The key word here is *assumed* my assumption is that if I open a TCP socket</div><div>and send it five messages numbered 1 to 5 then If I successfully read message</div><div>5 and have seen no error indicators then I can *assume* that messages 1 to 4 also arrived in order.</div><div><br></div><div>Actually I have no idea if this is true - but it does seem to be a reasonable</div><div>assumption.</div><div><br></div><div>Messages 1 to 4 might have arrived got put in a buffer prior to my reading them and accidentally reordered due to a software bug. An alpha particle might have hit the data in message 3 and changed it -- who knows?</div><div><br></div><div>Having assumed that message passing is reliable I build code based on</div><div>this assumption.</div><div><br></div><div>I'm not, of course, saying that the assumption is true, just that I trust the</div><div>implementers of the system have done a good job to try and make it true.</div><div>Certainly any repeatable counter examples should have been investigated</div><div>to see if there were any errors in the system.</div><div><br></div><div>All this builds on layers of trust. I trust that erlang message passing is ordered and reliable in the absence of errors.</div><div><br></div><div>The Erlang implementers trust that TCP is reliable.</div><div><br></div><div>The TCP implementors trust that the OS is reliable.</div><div><br></div><div>The OS implementors trust that the processor is reliable.</div><div><br></div><div>The processor implementors trust that the VLSI compilers are correct.</div><div><br></div><div>Software runs on physical machines - so really the laws of physics apply not</div><div>maths. Physics takes into account space and time, and the concept of simultaneity does not exist, no so in maths.</div><div><br></div><div>It seems to me that software is built upon chains of trust, not upon mathematical chains of proof.</div><div><br></div><div>I've just been saying "what we want to achieve" and not "how we can achieve it".</div><div><br></div><div>The statements that people make about the system should be in terms</div><div>of belief rather than proof.</div><div><br></div><div> I'd say "I believe we have reliable message passing"</div><div>It would be plain daft to say "we have reliable message passing" or</div><div>"we can prove it be correct" since there is no way of validating this.</div><div><br></div><div>Call me old fashioned but I think that claims that, for example,</div><div>"we have unlimited storage" and so on are just nuts ...</div><div><br></div><div>Just say it how it is - we believe this to be the case, and here is our evidence ...</div><div><br></div><div>Cheers</div><div><br></div><div>/Joe</div><div><br></div><div><br></div><div><br></div><div><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 25, 2017 at 11:05 PM, Miles Fidelman <span dir="ltr"><<a href="mailto:mfidelman@meetinghouse.net" target="_blank">mfidelman@meetinghouse.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<p>Hi Joe,</p>
<p>Thanks for the reply. But... it raises a few follow-up questions
& comments:<br>
</p><span class="">
<p>Joe Armstrong <a class="m_3102531641877986655moz-txt-link-rfc2396E" href="mailto:erlang-questions@erlang.org" target="_blank"><erlang-questions@erlang.org></a> wrote:<br>
</p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">I think I should add - that "in the absence of errors message passing
is ordered"
I think we should deliberately separate errors which are detected by
sockets closing, pings timing out etc. from the message passing behaviour.
Imagine a client sends numbered messages 1,2,3,4,5 in order to a server.
If no errors have been observed and the server receives message 5 we can
assume that messages 1..4 have also been received in order.</pre>
</blockquote>
<p></p>
</span><p>It's the error cases that raise all the interesting questions!
What happens if message 5 arrives, but message 4 doesn't, or if it
arrives later? Those define the special cases that application
logic might have to handle!<br>
</p>
<p>------- context of question -----</p>
<p>I was re-reading your thesis the other day (I think a quora
interchange with Alan Kay sparked me to do so), and these lines
particularly caught my eye:</p>
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)"><span class=""><i>"2. Message passing between a pair of processes is assumed to be ordered
</i><i>meaning that if a sequence of messages is sent and received between any pair
</i><i>of processes then the messages will be received in the same order they were
</i><i>sent."
</i><i>
</i><i>"Note that point two is a design decision, and does not reflect any under-
</i><i>lying semantics in the network used to transmit messages. The underlying
</i><i>network might reorder the messages, but between any pair of processes these
</i><i>messages can be buffered, and re-assembled into the correct order before
</i><i>delivery. This assumption makes programming message passing applications
</i><i>much easier than if we had to always allow for out of order messages."</i></span><i>
but... </i><i><i>"Message passing is assumed to be unreliable with no guarantee of delivery."</i>
</i></pre>
<p>Somehow, I don't see how this makes "programming message passing
applications much easier" - maybe it makes the underlying run-time
easier, but not the applications. An awful lot of applications
can go south very quickly if messages are lost (account balances
in transaction processing systems comes to mind as the obvious
example). If the underlying environment doesn't provide BOTH
reliable delivery AND ordered delivery, one pretty much has to
write one's own protocol to guaranty reliable, ordered message
transmission.</p>
<p>Which leads back to the questions of what, in detail, does Erlang
do, and how much of that behavior is guaranteed going forward!</p>
<p>------- end context ---------<br>
</p>
<p><Note: When I ask about a message "showing up" there's the
obvious distinction between making it from one processor/node to
another, as opposed to being placed in the receiving processes
inbox, ready to be read?></p>
<p>What happens if messages 1, 2, 3, 5 (but not 4) show up (are
there sequence numbers available to the internal message passing
mechanisms)? <br>
</p>
<p>What happens if 1, 2, 3, 5 show up, and 4 shows up just a tad
later - but before 5 has been read by the receiving process? <br>
</p>
<p>What about if 1,2,3,5 have all been read, and then 4 shows up?<span class=""><br>
</span></p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">The client will never know how many messages the server has received
unless the server tells it.</pre>
</blockquote>
<p></p>
<p>Well, doesn't that have to do with whether there are sequence
numbers embedded in the message passing mechanism?<span class=""><br>
</span></p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">This is what the system is supposed to do - how it does it will depend
on time (ie how it does it today will differ from how it was done 10 years ago)</pre>
</blockquote>
<p></p>
<p><br>
</p>
<p>Well... it also depends on how the semantics of message passing
are defined. <br>
</p>
<p><span class=""><br>
</span></p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">In the old days there was just a single socket between a client and
server - so we assumed that what you wrote to the socket
got reead in the order it was send. This true at the application level
packets might get fragmented but they are not reordered.
(In lower levels of the TCP stack, out of order packages are reordered
and missing packets resent).
So In the absence of errors (meaning the TCP socket had not closed)
what comes out of a socket has the same ordering as what went in.
(Note: not true for UDP)
I guess we also make assumptions that the underlying layers are also
reliable - So Erlang messaging should be reliable if TCP is reliable.</pre>
</blockquote>
Hence my question about mechanisms. The BEAM Book gives all the
gory details about how messages are passed (now) in both
single-processor & multi-processor environments; but details
are not provided on how the distributed case is handled. <br>
<p></p>
<p>By the way, TCP may be reliable, but if the connection is broken
and a new connection established, stuff can get dropped - it's a
higher level decision as to whether lost traffic is resent. And
that's where "design decisions" come in - what gets implemented in
the run-time system, and what is left to applications.<span class=""><br>
</span></p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">The subject is complicated by a load of theorems saying that various
things are mathematically impossible (distributed consensus, exactly
once delivery if messages) -
Add multicore processors and multiple sockets between nodes and
the situation because a lot more complicated.</pre>
</blockquote>
<p></p>
<p>Precisely what sparks my interest. <br>
</p>
<p>Inquiring minds want to know! :-)<br>
</p>
Best,
<p>Miles<br>
</p>
<p><br>
</p><blockquote type="cite">
<pre style="white-space:pre-wrap;color:rgb(0,0,0);font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;background-color:rgb(255,255,255)">Cheers
/Joe
On Mon, Sep 25, 2017 at 6:02 PM, Miles Fidelman
<<img src="http://erlang.org/pipermail/erlang-questions/emailaddrs/ema-5537.png" border="0">> wrote:
><i> On 9/24/17 11:53 PM, Raimo Niskanen wrote:
</i><div><div class="h5">><i>
</i>><i> On Sun, Sep 24, 2017 at 11:24:31PM -0700, Miles Fidelman wrote:
</i>><i>
</i>><i> See below....
</i>><i>
</i>><i>
</i>><i> On 9/24/17 6:10 PM, zxq9 wrote:
</i>><i>
</i>><i> On 2017年09月24日 日曜日 16:50:45 Miles Fidelman wrote:
</i>><i>
</i>><i> Folks,
</i>><i>
</i>><i> I've just been re-reading Joe Armstrong's thesis, and I'm reminded of a
</i>><i> question that's been nagging me.
</i>><i>
</i>><i> As I understand it, message delivery is not guaranteed, but message
</i>><i> order IS. So how, exactly does that work? What's the underlying
</i>><i> mechanism that imposes sequencing, but allows messages to get lost?
</i>><i> (Particularly across a network.) What are the various scenarios at play?
</i>><i>
</i>><i> This is sort of backwards.
</i>><i>
</i>><i> Message delivery is guaranteed, assuming the process you are sending a
</i>><i> message to exists and is available, BUT from the perspective of the
</i>><i> sender there is no way to tell whether the receiver actually got it,
</i>><i> has crashed, disappeared, fell into a network blackhole, or whatever.
</i>><i> Monitoring can tell you whether the process you are trying to reach
</i>><i> is available right at that moment, but that's it.
</i>><i>
</i>><i> The point is, though, that whether the receiver is unreachable, has
</i>><i> crashed, got the message and did its work but was unable to report
</i>><i> back about it, or whatever -- its all the same reality from the
</i>><i> perspective of the sender. "Unavailable" means "unavailable", not matter
</i>><i> what the cause -- because the cause cannot be determined from the
</i>><i> perspective of the sender. You can only know this with an out of
</i>><i> context check of some sort, and that is basically the role the runtime
</i>><i> plays for you with regard to monitors and links.
</i>><i>
</i>><i> The OTP synchronous "call" mechanism is actually a complex procedure
</i>><i> built from asynchronous messages, unique reference tags, and monitors.
</i>><i>
</i>><i> Note that I didn't ask about the synchronous calls, I asked about raw
</i>><i> interprocess messages.
</i>><i>
</i>><i> What IS guaranteed is the ordering of messages *relative to two processes*
</i>><i>
</i>><i> If A sends B the messages 1, 2 and 3 in that order, they will certainly
</i>><i> arrive in that order (assuming they arrive at all -- meaning that B is
</i>><i> available from the perspective of A).
</i>><i>
</i>><i> But that's the question. Particularly when sent via network, 1, 2, 3
</i>><i> may be sent in that order, but, at the protocol level, they may not
</i>><i> arrive in that order.
</i>><i>
</i>><i> What protocol level?
</i>><i>
</i>><i> Erlang distribution has to use or implement a reliable protocol. Today
</i>><i> TCP, but anything is possible. Note that this protocol is between two
</i>><i> nodes, both containing many processes. But the emulator relies on the
</i>><i> transport protocol being reliable.
</i>><i>
</i>><i>
</i>><i> No. It doesn't. It could simply send UDP packets. I'm asking about
</i>><i> implementation details. In Joe's thesis, he says that the behavior is a
</i>><i> "design choice." I'm asking about the implementation details. How does
</i>><i> BEAM actually handle message delivery - locally, via network?
</i>><i>
</i>><i> With a reliable transport protocol - say TCP - if the message-containing
</i>><i> packets arrived as 1, 3, 2, the protocol engine would wait for 2 to
</i>><i> arrive and deliver 1,2,3 in that order. If It received 1 & 3, but 2 got
</i>><i> lost, it would request a re-transmit, wait for it to arrive, and again,
</i>><i> deliver in that order.
</i>><i>
</i>><i> But the implication of Erlang's stated rules is that an unreliable
</i>><i> transport protocol is being used, if you send 1, 2, 3, and what arrives
</i>><i>
</i>><i> What? What is stated?
</i>><i>
</i>><i> From Joe Armstrong's Thesis:
</i>><i>
</i>><i> "Message passing is assumed to be unreliable with no guarantee of delivery."
</i>><i>
</i>><i> "Since we made no assumptions about reliable message passing, and must write
</i>><i> our application so that it works in the presence of unreliable message
</i>><i> passing it should indeed work in the presence of message passing errors. The
</i>><i> initial ecort involved will reward us when we try to scale up our systems."
</i>><i>
</i>><i> "2. Message passing between a pair of processes is assumed to be ordered
</i>><i> meaning that if a sequence of messages is sent and received between any pair
</i>><i> of processes then the messages will be received in the same order they were
</i>><i> sent."
</i>><i>
</i>><i> "Note that point two is a design decision, and does not reflect any under-
</i>><i> lying semantics in the network used to transmit messages. The underlying
</i>><i> network might reorder the messages, but between any pair of processes these
</i>><i> messages can be buffered, and re-assembled into the correct order before
</i>><i> delivery. This assumption makes programming message passing applications
</i>><i> much easier than if we had to always allow for out of order messages."
</i>><i>
</i>><i> ---
</i>><i> I read this as saying, messages will be delivered in order, but some may be
</i>><i> missing.
</i>><i>
</i>><i> I'm really interested in this design decision, and how it's implemented.
</i>><i> (I'm also interested in the logic of why it's easier to program around
</i>><i> missing messages than out-of-order messages.)
</i>><i>
</i>><i> Miles
</i>><i>
</i>><i> --
</i>><i> In theory, there is no difference between theory and practice.
</i>><i> In practice, there is. .... Yogi Berra
</i>><i>
</i>><i>
</i>><i> ______________________________<wbr>_________________
</i>><i> erlang-questions mailing list
</i></div></div>><i> <img src="http://erlang.org/pipermail/erlang-questions/emailaddrs/ema-36.png" border="0">
</i>><i> <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/<wbr>listinfo/erlang-questions</a>
</i>></pre>
</blockquote>
<br>
<p></p><span class="">
<pre class="m_3102531641877986655moz-signature" cols="72">--
In theory, there is no difference between theory and practice.
In practice, there is. .... Yogi Berra</pre>
</span></div>
<br>______________________________<wbr>_________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/<wbr>listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div></div></div>