Network Coding for Computing: Cut-Set Bounds

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