-1
$\begingroup$

I think I remember a claim that asynchronous message passing can be implemented by synchronous message passing but not vice versa. Unfortunately, I don't remember an article name, an author, or even a field. Does this ring a bell, or am I delusional?

$\endgroup$

1 Answer 1

2
$\begingroup$

You can create a synchronous messaging system with an asynchronous messaging system. This is done by waiting for an acknowledgement directly after sending a message.

An example for this is the actor model which is able to build a synchronous messaging system like CSP.

But you also can simulate a asynchronous messaging system. When you use buffers to store the message. So the Receiver can access it when he wants to.

An example for this would be the email system which works with TCP.

In Synchronous, asynchronous, and causally ordered communications they make the statement that the simulation of both is a well known fact.

In Actors, a model of concurrent computation Agha makees the statement that synchronous messages are always build out of asynchonous messages.

EDIT: I changed my original answer, thanks to the comments. I really thought that Tanenbaum had made a comment on this, but he didn't and since i come from the actor model background i always assume message to be asynchonous even synchronous ones.

$\endgroup$
8
  • 1
    $\begingroup$ No it's not. asynchronous = synchronous + buffer processes. $\endgroup$
    – Kai
    May 29, 2013 at 9:15
  • $\begingroup$ He is Tanenbaum. $\endgroup$
    – beroal
    May 29, 2013 at 10:53
  • 1
    $\begingroup$ @Kai, it depends on exactly what the terms mean. For example, if you combine synchronous message passing with buffers and the buffers preserver message order, then you do not get asynchrony proper (where message order can change in transit). Also, buffers are an additional mechanism. You can implement synchrony in terms of asynchrony by handshaking, which does not (simplifying a bit) need anything else. $\endgroup$ May 29, 2013 at 15:07
  • 1
    $\begingroup$ @RaphaelAhrens Consider $\pi$-calculus. Let $tr(P)$ be the translation function from the synchronous into the asynchronous variant. The key clauses are $tr(\overline{x}\langle \vec{y} \rangle.P) = (\nu a)(\overline{x}\langle a\vec{y} \rangle\ |\ a().tr(P))$ and $tr(x(\vec{y}).P) = x(a\vec{y}).( \overline{a}\langle \rangle\ |\ tr(P))$. To prove full abstraction of this encoding you'd probably need to impose a typing discipline. A variant of this encoding has been studied by Quaglia and Walker in "On Synchronous and Asynchronous Mobile Processes" $\endgroup$ May 30, 2013 at 11:35
  • 1
    $\begingroup$ @Martin It depends indeed, also on the definition of asynchrony. The original poster made no restrictions. Buffers can be processes. That's not necessarily a new mechanism. Whether these processes preserve message order depends on how you model the buffer processes, not necessarily the process model itself. (See Chapter 14 of Lynch's book [1].) The distributed computing literature clarified that e.g. in the presence of faults, synchrony can be strictly stronger than asynchrony (Chapter 22 of [1]: groups.csail.mit.edu/tds/distalgs.html .) $\endgroup$
    – Kai
    May 31, 2013 at 2:02

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.