Logically Instantaneous Communication on Top of Distributed Memory Parallel Machines

A. Mostefaoui, M. Raynal and P. VerĂ­ssimo

Lecture Notes in Computer Science LNCS 1662, September 1999, Springer-Verlag, editor Victor Malyshkin


Communication is Logically Instantaneous (LI) if it is possible to timestamp communication events with integers in such a way that (1) timestamps increase within each process and (2) the sending and the delivery events associated with each message have the same timestamp. So, there is a logical time frame in which for each message, the send event and the corresponding delivery events occur simultaneously. LI is stronger than Causally Ordered (CO) communication, but weaker than Rendezvous (RDV) communication. LI is attractive as it includes CO and provides more concurrency than RDV. Moreover it allows to adopt the following approach: first design a distributed application assuming Rendezvous communication, and then run it on top of an asynchronous distributed system providing only LI communication.

 This paper explores Logically Instantaneous communication and provides a simple and efficient protocol that implements LI on top of asynchronous distributed systems.


Asynchronous Distributed System, Communication Protocol, Logical Time, Logically Instantaneous Communication, Rendezvous.


author = {A.\ Mostefaoui and M.\ Raynal and P.\ Ver\`{i}ssimo},
title = {Logically Instantaneous Communication on Top of Distributed Memory Parallel Machines},
booktitle = {Proc.\ of the 5th International Conference on Parallel
Computing Technologies (PaCT'99)},
editor = {Victor Malyshkin},
series = {Lecture Notes in Computer Science LNCS 1662},
year = 1999,
publisher = {Springer-Verlag},
month = {September},
pages = {258--270},
address = {St. Petersburg, Russia}

Full Paper

postscript version