Using AVL trees for fault-tolerant group key management

In this paper we describe an efficient algorithm for the management of group keys for group communication systems. Our algorithm is based on the notion of key graphs, previously used for managing keys in large Internet-protocol multicast groups. The standard protocol requires a centralized key server that has knowledge of the full key graph. Our protocol does not delegate this role to any one process. Rather, members enlist in a collaborative effort to create the group key graph. The key graph contains n keys, of which each member learns log₂n of them. We show how to balance the key graph, a result that is applicable to the centralized protocol. We also show how to optimize our distributed protocol, and provide a performance study of its capabilities.

Authors and Affiliations

1. The Hebrew University Jerusalem, Institute of Computer Science, Jerusalem 91904, Israel; E-mail: {orodeh,dolev}@cs.huji.ac-il, , , , , , IL

   Ohad Rodeh & Danny Dolev

2. Cornell University Ithaca, Department of Computer Science, 4119 Upson Hall, New York 14853, USA; E-mail: ken@cs.cornell.edu, , , , , , US

   Kenneth P. Birman

Published online: 26 October 2001

Reprints and permissions