Sum-Networks from Incidence Structures: Construction and Capacity Analysis
Abstract
A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.
Recommended Citation
A. S. Tripathy and A. Ramamoorthy, "Sum-Networks from Incidence Structures: Construction and Capacity Analysis," IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3461 - 3480, Institute of Electrical and Electronics Engineers (IEEE), May 2018.
The definitive version is available at https://doi.org/10.1109/TIT.2017.2765661
Department(s)
Computer Science
Keywords and Phrases
Characteristic; Function Computation; Incidence Structures; Network Coding; Sum-Networks
International Standard Serial Number (ISSN)
0018-9448; 1557-9654
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2018 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 May 2018
Comments
This work was supported by the National Science Foundation under Grant CCF-1149860, Grant CCF-1320416, Grant CCF-1718470, and Grant DMS-1120597.
This paper was presented in part at the 2014 52nd Allerton Conference on Communication, Control, and Computing and the 2015 IEEE International Symposium on Information Theory.