A Reliable Protocol for Synchronous Rendezvous

Lucian Wischik, Damon Wischik. University of Bologna Technical Report 2004-1.

Abstract.

In the presence of failure, any protocol for distributed atomic commitment necessarily has a 'window of vulnerability' where the crash of one party makes other parties block. This vulnerability turns out not so serious in one special case - that of synchronous rendezvous. Rendezvous is important because it is the basis for process calculi, which themselves underpin several new experimental languages and also web services.

We give a simplified three phase commit protocol specially tailored to rendezvous. In the presence of arbitrary message loss and permanent site failure, the protocol is strongly non-blocking for one party - the party can always unblock immediately. This is useful for writing a reliable non-blocking web service. If message loss is fair and site failure is not permanent, then the protocol is also weakly non-blocking for the other party – the chance of it remaining blocked tends to zero as time increases. (This yields a solution to the classic 'Two Generals' problem, which is a degenerate case of rendezvous).

The proof of non-blocking uses a novel technique involving Markov processes. It is a general technique that applies to any calculus and any implementation with message loss, so long as the two are bisimilar.

@TechReport{wischik04_protocol,
  author = "Lucian Wischik and Damon Wischik",
  title = "A Reliable Protocol for Synchronous Rendezvous (Note)",
  institution = "University of Bologna",
  year = "2004",
  type = "Technical Report",
  number = "2004-1",
  url = "http:// www.wischik.com/ lu/ research/ verona.html",
}

Download

  • Full version in PDF format, 1.2Mb, 25 pages.
  • Slides/handouts from a talk at Inria Rocq, 9.7Mb, PNG and PPT format.