English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider optimal distributed computation of a given function ofdistributed data. The input (data) nodes and the sink node that receives thefunction form a connected network that is described by an undirected weightednetwork graph. The algorithm to compute the given function is described by aweighted directed acyclic graph and is called the computation graph. Anembedding defines the computation communication sequence that obtains thefunction at the sink. Two kinds of optimal embeddings are sought, the embeddingthat---(1)~minimizes delay in obtaining function at sink, and (2)~minimizescost of one instance of computation of function. This abstraction is motivatedby three applications---in-network computation over sensor networks, operatorplacement in distributed databases, and module placement in distributedcomputing.  We first show that obtaining minimum-delay and minimum-cost embeddings areboth NP-complete problems and that cost minimization is actually MAX SNP-hard.Next, we consider specific forms of the computation graph for which polynomialtime solutions are possible. When the computation graph is a tree, a polynomialtime algorithm to obtain the minimum delay embedding is described. Next, forthe case when the function is described by a layered graph we describe analgorithm that obtains the minimum cost embedding in polynomial time. Thisalgorithm can also be used to obtain an approximation for delay minimization.We then consider bounded treewidth computation graphs and give an algorithm toobtain the minimum cost embedding in polynomial time.

Optimal Embedding of Functions for In-Network Computation: Complexity Analysis and Algorithms