Postscript document

next up previous
Next: Discussion Up: Robustness Previous: Protocol Unification

Cascaded Events

 

Since network disruptions are random and unpredictable, it is natural to consider the possibility of so-called cascaded membership events. In fact, cascaded events and their impact on group protocols are often considered in group communication literature, but, alas, frequently neglected in the security literature. Furthermore, the probability of a cascaded event is much higher on a wide area network. A cascaded event occurs when one membership change occurs while another is being handled. For example, a partition can occur while a prior partition is processed, resulting in a cascade of size two.

We claim that the STRpartition protocol is self-stabilizing, i.e., robust against cascaded network events. In general, self-stabilization is a very desirable feature since lack thereof requires extensive and complicated protocol "coating" to either 1) shield the protocol from cascaded events, or 2) harden it sufficiently to make the protocol robust with respect to cascaded events (essentially, by making it re-entrant). The latter is often very complicated and inefficient as seen from [AKNR+01].

The pseudocode for the self-stabilizing protocol is shown as below.


boxedverbatim718

Based on view synchrony discussed in Section 2, we provide an informal proof that the above protocol terminates on any finite number of consecutive cascaded events. Due to view synchrony, every member has the same membership view. We can further assume that the ordering of members in the group communication system is same as that of the key tree. By Remark 1, at least a member, say Mi can compute the group key if all of the blinded session randoms are known. All members can then compute the group key using the broadcast message of the member Mi by Remark 2.

Hence, it is enough to show that at least one member knows every other member's session random, eventually. In the above pseudocode, the sponsor is the node below the lowest node whose blinded session random is missing. Now, if a sponsor Ms cannot compute the group key since some of the blinded keys are missing, it broadcasts the key tree which includes every blinded session random and blinded keys Ms knows. Then the sponsor of the next round will be the one who owns the missing blinded session random. Note that every member will have strictly more blinded session randoms and blinded keys as number of round increases. Hence, as cascaded events stabilize in the group communication system, the STRprotocol also terminates.


next up previous
Next: Discussion Up: Robustness Previous: Protocol Unification

Adrian Perrig
Sat Mar 31 16:41:33 PST 2001