We know that in an asynchronous system, no assumptions about process execution speeds or message delivery times are made. My question is: can we present any guarantee in asynchronous systems?

Some examples of the guarantees that I'm looking for are:

  1. Consider two processes $p$ and $q$. $p$ sends a message an infinite number of times to $q$. $q$ delivers the message finally if two processes are correct (a process that never crashes is said to be correct).
  2. If 1. is correct, then: no edge-cut in the network persists forever between the correct processes.

Your question is somewhat unclear. In asynchronous systems we normally assume that any message will eventually be delivered after some finite time. It if perfectly feasible to write an algorithm that sends infinitly many messages:

   Send a message to p;
   If received message form p do <...>

This is valid and will indeed cause infinite number of message exchange. But the timings of these messages are unknown.

I am not sure what you mean at your second point. If there are no link-failures, all edge-cuts remain alive. As long as the processors are correct, the link will be utilized infinitely often.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.