ken@gvax.cs.cornell.edu (Ken Birman) (12/28/89)
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
mak@urd.cs.cornell.edu (Mesaac Makpangou) (12/30/89)
In article <35521@cornell.UUCP> ken@cs.cornell.edu (Ken Birman) writes: > .... > >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? Why not define this as a different protocol with a different name, say a Per Group ABCAST. It seems to me that, ISIS already provides a set of protocols enforcing different ordering properties. This will be one more protocol, appropriate for a certain class of applications. Mesaac
ken@gvax.cs.cornell.edu (Ken Birman) (12/30/89)
In article <35564@cornell.UUCP> mak@cs.cornell.edu (Mesaac Makpangou) writes: >Why not define this as a different protocol with a different name, say a >Per Group ABCAST.... It seems to me that, ISIS already provides a set of >protocols enforcing different ordering properties. This will just >one more protocol, appropriate for a certain class of applications. Well, for one thing, ISIS already has too many protocols for any reasonable purpose. I would prefer to pretend we have cbcast and abcast, and gbcast for "special configuration problems". What I am suggesting is that Per Group ABCAST should be the one you get when you say "bcast" or "abcast", e.g. that it be default. I can certainly leave around a way to force ISIS to use the old flavor of abcast -- but since this won't provide ordering relative to the per-group abcast, you will still need to think in per-group terms... Basically, I would like the defaults to be as fast as possible. Ken
wood@hermod.cs.cornell.edu (Mark D. Wood) (12/31/89)
The proposed change to the abcast protocol could present some problems
for Meta, depending on its exact semantics. Meta currently guarantees
that all clients are notified of events in the same order. This
guarantee is trivially provided by the current abcast semantics. The
proposed BY-ABCAST protocol provides total ordering for messages sent
to the same logical address; this will be enough for Meta as long as
it holds for process addresses too, not just group addresses.
In particular, when a sensor perceives that one or more conditions are
satisfied, it sends a broadcast to the list of addresses {S,a,b,...}
where S is the sensor process group (useful if the sensor is
replicated) and {a,b,...} are the addresses of the processes (not
groups) who are being notified. The guarantee that Meta provides is
that if processes a and b receive notifies from two sensors, they
receive the notifies in the same order.
This seems like a useful property, but it often may not be necessary
and so perhaps we are wasting effort enforcing it those times when it
is not needed. What thoughts do others have on this subject? Another
approach would be to have the programmer explicitly inform Meta of
those processes that need to see things in a mutually consistent
ordering; these processes could be made to join a single process
group. Carrying this to the extreme, all clients of a sensor would
join a process group; the sensor would broadcast notifies to this
single group. The problem with this approach is that it results in
extra network traffic and requires clients to filter out unwanted
information.ken@gvax.cs.cornell.edu (Ken Birman) (12/31/89)
In article <35593@cornell.UUCP> wood@cs.cornell.edu (Mark D. Wood) writes: > >The proposed change to the abcast protocol could present some problems >for Meta... > >In particular, when a sensor perceives that one or more conditions are >satisfied, it sends a broadcast to the list of addresses {S,a,b,...} >where S is the sensor process group (useful if the sensor is >replicated) and {a,b,...} are the addresses of the processes (not >groups) who are being notified.... Actually, the proposed change won't affect these types of abcast's: they will still go by the "slow" route and will still be ordered w.r.t. one another. Say that a multicast is addressed to group G if G is its _only_ dest, and that it is addressed to group * if it has any other sort of dest (including a mixture of groups and processes, just processes, etc). The proposal is that abcasts with the same group address in this sense will be ordered wrt each other, but not wrt abcasts to other addresses. Meta seems to fall entirely within group '*'. (However, '*' goes by a slow route...) Ken