Source author record

Pooja Vyavahare

Pooja Vyavahare appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Networking and Internet Architecture

Catalog footprint

What is connected

3works

3topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

On the Maximum Rate of Networked Computation in a Capacitated Network

Given a capacitated communication network $\mathcal{N}$ and a function f that needs to be computed on $\mathcal{N},$ we study the problem of generating a computation and communication schedule in $\mathcal{N}$ to maximize the rate of computation of f. Shah et. al.[IEEE Journal of Selected Areas in Communication, 2013] studied this problem when the computation schema $\mathcal{G}$ for f is a tree. We define the notion of a schedule when $\mathcal{G}$ is a general DAG and show that finding an optimal schedule is equivalent to finding the solution of a packing LP. We prove that approximating the maximum rate is MAX SNP-hard by looking at the packing LP. For this packing LP we prove that solving the separation oracle of its dual is equivalent to solving the LP. The separation oracle of the dual reduces to the problem of finding minimum cost embedding given $\mathcal{N},\mathcal{G},$ which we prove to be MAX SNP-hard even when $\mathcal{G}$ has bounded degree and bounded edge weights and $\mathcal{N}$ has just three vertices. We present a polynomial time algorithm to compute the maximum rate of function computation when $\mathcal{N}$ has two vertices by reducing the problem to a version of submodular function minimization problem. For the general $\mathcal{N}$ we study restricted class of schedules and its equivalent packing LP. We observe that for this packing LP also the separation oracle of its dual reduces to finding minimum cost embedding. A version of this minimum cost embedding problem has been studied in literature. We present a quadratic integer program for the minimum cost embedding problem and its linear programming relaxation based on earthmover metric. We also present some approximate algorithms for special classes of $\mathcal{G}.$

preprint2015arXiv

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

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

preprint2012arXiv

In-Network Estimation of Frequency Moments

We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of non-linear functions of the distributed data which is over a large alphabet. We consider three types of networks: point-to-point networks with gossip based communication, random planar networks in the connectivity regime and random planar networks in the percolating regime both of which use the slotted Aloha communication protocol. For each network type, we estimate the scaled $k$-th frequency moments, for $k \geq 2$. Specifically, for every $k \geq 2,$ we give a distributed randomized algorithm that computes, with probability $(1-δ),$ an $ε$-approximation of the scaled $k$-th frequency moment, $F_k/N^k$, using time $O(M^{1-\frac{1}{k-1}} T)$ and $O(M^{1-\frac{1}{k-1}} \log N \log (δ^{-1})/ε^2)$ bits of transmission per communication step. Here, $N$ is the number of nodes in the network, $T$ is the information spreading time and $M=o(N)$ is the alphabet size.