Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!ken
From: ken@gvax.cs.cornell.edu (Ken Birman)
Newsgroups: comp.sys.isis
Subject: A technical question
Keywords: Bypass protocols
Message-ID: <35521@cornell.UUCP>
Date: 27 Dec 89 18:11:04 GMT
Sender: nobody@cornell.UUCP
Reply-To: ken@cs.cornell.edu (Ken Birman)
Distribution: comp
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 35

You've all heard about BYPASS CBCAST by now, and are no doubt wondering
if we plan to do a blindingly fast ABCAST protocol as well.

Here's the situation:  BYPASS CBCAST works now, and Pat is instrumenting
performance to post here and for the paper we have written on the mechanism
(should be out in mid to late January).  

We can easily implement a BYPASS ABCAST protocol too; it would perform
almost identically with CBCAST (for most situations, BY-ABCAST==BY-CBCAST
in all respects; in some situations there is a slight background cost).
However, unlike BY-CBCAST, the introduction of BY-ABCAST wouldn't be
transparent.

The problem is related to addressing.  Say that you have two groups 
G1=(p,q,r) and G2=(q,r) and you use the current ISIS ABCAST to send messages
to G1 and G2.   q and r will get both messages; the ABCAST property implies
that they will get them in the same order -- even though they were
sent to different groups.

The BY-ABCAST protocol only provides total ordering for messages sent
to THE SAME logical address.  Thus, two BY-ABCASTS to G1 or G2 will be
received in a total order, but the two BY-ABCAST's described above (one to
G1, one to G2) might be seen in different orders by q and r.  BY-ABCAST,
like the current ISIS ABCAST, always respects causality.

It is so attractive to me to switch to BY-ABCAST (WOW!  What speed!)
that I am inclined to change the promises ISIS makes about ABCAST
addressing to say that "Two messages sent to the same logical addresses
will be delivered in the same order; messages to different addresses
may be delivered in different orders even if some destination processes
receive both".  How do people feel about this idea?  Recall that "bcast"
is a synonym for "abcast", so this change would drastically impact all
existing code... but would it break anything?

Ken