whereas the newer ones are complex and offer insufficient advantage to users.

Complexity in computer science also offers problems in the design of hardware as well as software. Such a problem is the optimal interconnection of parallel processors having large numbers of computational modes. Networks derived from hypercubes form the basis for architectures of such systems as the BBN Butterfly, the IBM RP3 and GF11, the Intel iPSC, the Connection Machine, and the NCUBE. However, such architectures introduce worst-case communication problems for which the run time scales as the square root of N, where N is the number of processors.

Tom Leighton, of the Massachusetts Institute of Technology, notes that randomly wired interconnected networks represent a useful alternative. Such networks are not wholly random; the randomness is subject to constraints. Even so, they can outperform traditional well-structured networks in several important respects. The worst-case problems disappear; all problems offer run times that scale as ln N. In addition, randomly wired networks have exceptional fault tolerance because they offer multiple redundant paths. They are well suited for both packet-routing and circuit-switching applications.