----------------------------------------------
|          TECHNICAL REPORT ECE-96-1           |
|                January 1996                  |
| Dept. of Electrical and Computer Engineering |
|           University of Victoria             |
 ----------------------------------------------

TITLE:   Optimal Total Exchange in Cayley Graphs

AUTHORS: V. V. Dimakopoulos and N. J. Dimopoulos

NOTE:    Submitted for publication

ABSTRACT

Consider  an  interconnection  network   and   the   following
situation: every node needs to send  a  different  message  to
every other node. This  is  the  {\itshape  total  exchange\/}
problem, one of a number of information dissemination problems
known as collective communications. Under the assumption  that
a node can send and receive only  one  message  at  each  step
({\itshape single-port\/} model) it is seen that  the  minimum
time required to solve the problem is governed by  the  status
(or total distance) of the nodes in the  network.  We  present
here a time-optimal solution for any  Cayley  network.  Rings,
hypercubes,  cube-connected  cycles,  butterflies   are   some
well-known Cayley networks which can  take  advantage  of  our
method. The solution is based on a class of  algorithms  which
we  call  {\itshape  node-invariant\/}  algorithms  and  which
behave uniformly across the network.

KEYWORDS:  Cayley graphs, collective communications, intercon-
           nection networks, total exchange (multiscattering)

AMS(MOS) SUBJECT CLASSIFICATIONS: 
           94C15, 68M10, 68R10, 68Q22, 05C25