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 
and
depth 
. 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 
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.