Optimality Proofs for an All-to-all Broadcast

TR-CS-97-0025

Jeff Matocha and John C. Lusth
Department of Computer Science
The University of Alabama
Tuscaloosa, AL 35487-0290
[email protected], [email protected]

April 15, 1997

Abstract
Many times in a network, it is necessary to all members of the system to share information with all other members. All-to-all broadcast is a natural method for dispersing such information. In order to keep the expense of such a broadcast low, we are concerned with developing an algorithm in which the number of message steps required is optimal. In this report, we present an algorithm for all-to-all broadcast and the prove its correctness, parsimony, and optimality in terms of the number of message steps.

1 Introduction

All-to-all broadcast is an algorithm which is used when all members of a network find it necessary to distribute information to all other members. Some examples of situations when an all-to-all broadcast is necessary include the sharing of routing information amongst the routers in a LAN and gaining location information about a set of mobile hosts in order to initiate group communication.

In developing any broadcast protocol, one can consider efficiency on two axes, the number of messages and the number of message steps [1]. Similar to the approach to all-to-all broadcast by Chen, Yu, and Wu [2], we consider minimization of the message steps to be most important. A message is defined as the conveyance of information from one group member to another. A message step is a burst of message traffic; a burst lasts until the last message in the burst is received. We assume that a host may send and receive r messages during one message step. In most systems, one would consider r = 1, yet our algorithm generalizes the send/receive step to allow for any r.