The wiring economy principle for designing inference networks

The wiring economy principle in neuroscience has explained many experimentally observed properties of neuronal networks by asserting the need to keep the axons and dendrites that connect neurons small in length. Just like neuronal networks, many distributed systems are physical constructs that incur deployment and maintenance costs for their communication infrastructure. Taking wiring economy as a design goal for engineering systems that perform distributed coordination and inference, this paper formulates and studies the tradeoff between performance and wiring cost. It is shown that separated communication topology design and physical node placement yields optimal design. Designing optimal networks is shown to be NP-complete. The natural relaxation to the integer network design problem is shown to be a reverse convex program. Small optimal networks are computed. Optimally placed random network topologies are demonstrated to have good performance.