next up previous
Next: 1.6 Outline Up: 1 Introduction Previous: 1.4 Our results

1.5 Related work

Randomly-wired splitter networks and multibutterflies have appeared in a number of different contexts. In 1974, Bassalygo and Pinsker [3] used (randomly-wired) splitter networks with expansion to construct the first nonblocking network of size tex2html_wrap_inline1423 and depth tex2html_wrap_inline1425 . In 1980, Fahlman [7] proposed a randomly-wired network called the Hashnet. In 1989, Upfal [29] studied splitter networks with expansion (which he called multibutterflies - a term attributed to Ron Fagin) and described a simple deterministic algorithm for routing in tex2html_wrap_inline1427 steps on an N-input multibutterfly. In another paper, Arora, Leighton, and Maggs [2] developed a circuit-switching algorithm for multibutterfly and multi-Benes networks and showed that the algorithm can be used to establish connections in a nonblocking fashion. Most recently, DeHon, Knight, and Minsky [5] designed a 64-processor switching network using a randomly-wired splitter network for processor to memory communications. Experimental work on randomly-wired splitter networks is described in [4, 5, 13, 15, 21]. See also [6, 8] for other applications in which expanders are used to tolerate faults.

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996