Distributed Approach for Fast Broadcasting and Gathering in Q-ary Cubes

An interesting application of coding theory in network routing is presented. Certain error-correcting codes can be employed to specify a minimal subset of nodes called “stations” which are at distance t from the rest of the nodes. The stations, acting as relay agents, can then broadcast data/control information from central controller to all nodes (or conversely from the nodes to central controller) in no more than t steps. The network considered is the q-ary n-dimensional hypercube. The study shows that for a given t, perfect codes yield the minimal set of stations whereas quasi-perfect codes render suboptimal solution