Network Coding for Computing: Cut-Set Bounds

Abstract

The following \textit{network computing} problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function $f$ of the messages. The objective is to maximize the average number of times $f$ can be computed per network usage, i.e., the ``computing capacity''. The \textit{network coding} problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network \textit{min-cut} upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks and for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.

Submitted to the IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Networks); Revised on Aug 9, 2010

References in corpus (2)

• Cascade multiterminal source coding
• Feasible alphabets for communicating the sum of sources over a network

Cited by in corpus (25)

• Streaming Big Data meets Backpressure in Distributed Network Computation
• CONDENSE: A Reconfigurable Knowledge Acquisition Architecture for Future 5G IoT
• Network coding for distributed quantum computation over cluster and butterfly networks
• Multiple Access Channel Simulation
• Linear Coding Schemes for the Distributed Computation of Subspaces
• The Capacity of Classical Summation over a Quantum MAC with Arbitrarily Distributed Inputs and Entanglements
• On Computing a Function of Correlated Sources
• The Capacity of 3 User Linear Computation Broadcast
• Expand-and-Randomize: An Algebraic Approach to Secure Computation
• On Efficiently Explaining Graph-Based Classifiers
• Computation in Multicast Networks: Function Alignment and Converse Theorems
• On the Solvability of 3s/nt Sum-Network---A Region Decomposition and Weak Decentralized Code Method
• Computing linear functions by linear coding over networks
• Communication Cost for Updating Linear Functions when Message Updates are Sparse: Connections to Maximally Recoverable Codes
• Reduced Complexity Sum-Product Algorithm for Decoding Network Codes and In-Network Function Computation
• Scalar Solvability of Network Computation Problems and Representable Matroids
• On Computation Rates for Arithmetic Sum
• Improved Upper Bound on the Network Function Computing Capacity
• Rate Distortion for Lossy In-network Function Computation: Information Dissipation and Sequential Reverse Water-Filling
• Computation Over Gaussian Networks With Orthogonal Components
• Robust Analog Function Computation via Wireless Multiple-Access Channels
• Sum-networks from undirected graphs: construction and capacity analysis
• Capacity of Summation over a Symmetric Quantum Erasure MAC with Partially Replicated Inputs
• On the Maximum Rate of Networked Computation in a Capacitated Network
• Computation over Mismatched Channels