### Distributed Online Data Aggregation in Dynamic Graphs

**2016-02-02**

1602.01065 | cs.DC

We consider the problem of aggregating data in a dynamic graph, that is,
aggregating the data that originates from all nodes in the graph to a specific
node, the sink. We are interested in giving lower bounds for this problem,
under different kinds of adversaries. In our model, nodes are endowed with
unlimited memory and unlimited computational power. Yet, we assume that
communications between nodes are carried out with pairwise interactions, where
nodes can exchange control information before deciding whether they transmit
their data or not, given that each node is allowed to transmit its data at most
once. When a node receives a data from a neighbor, the node may aggregate it
with its own data. We consider three possible adversaries: the online adaptive
adversary, the oblivious adversary , and the randomized adversary that chooses
the pairwise interactions uniformly at random. For the online adaptive and the
oblivious adversary, we give impossibility results when nodes have no knowledge
about the graph and are not aware of the future. Also, we give several tight
bounds depending on the knowledge (be it topology related or time related) of
the nodes. For the randomized adversary, we show that the Gathering algorithm,
which always commands a node to transmit, is optimal if nodes have no knowledge
at all. Also, we propose an algorithm called Waiting Greedy, where a node
either waits or transmits depending on some parameter, that is optimal when
each node knows its future pairwise interactions with the sink.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-11-28**

1811.11331 | cs.NI

We consider ad-hoc networks consisting of $n$ wireless nodes that are located
on the plane. Any two … show more

**2018-12-01**

1812.00134 | cs.DS

In this paper we introduce the \emph{semi-online} model that generalizes the
classical online comput… show more

**2018-11-05**

1811.01643 | cs.DC

A graph is weakly $2$-colored if the nodes are labeled with colors black and
white such that each bl… show more

**2018-05-18**

1805.07294 | cs.DC

In this paper, we study distributed graph algorithms in networks in which the
nodes have a limited c… show more

**2015-10-26**

1510.07357 | cs.DC

We consider wireless networks with the SINR model of interference when nodes
have very limited indiv… show more

**2016-05-06**

1605.01903 | cs.DC

Leader election is, together with consensus, one of the most central problems
in distributed computi… show more

**2018-09-02**

1809.00273 | cs.DC

This paper focuses on studying the message complexity of implicit leader
election in synchronous dis… show more

**2019-01-02**

1901.00342 | cs.DC

In this paper, we look at the problem of randomized leader election in
synchronous distributed netwo… show more

**2016-11-19**

1611.06343 | cs.DC

Consider the classical problem of information dissemination: one (or more)
nodes in a network have s… show more

**2016-07-11**

1607.02951 | cs.DC

We consider networks of processes which interact with beeps. In the basic
model defined by Cornejo a… show more

**2018-09-10**

1809.03141 | cs.CC

The diffusion of information has been widely modeled as stochastic diffusion
processes on networks. … show more

**2014-04-09**

1404.2387 | cs.NI

We introduce collision free layerings as a powerful way to structure radio
networks. These layerings… show more

**2012-07-08**

1207.1836 | cs.NI

We consider the local broadcasting problem in the SINR model, which is a
basic primitive for gatheri… show more

**2013-02-15**

1302.3828 | cs.DM

Randomized gossip is one of the most popular way of disseminating information
in large scale network… show more

**2013-08-13**

1308.2954 | cs.DS

The network inference problem consists of reconstructing the edge set of a
network given traces repr… show more

**2013-07-05**

1307.1690 | cs.DS

People today typically use multiple online social networks (Facebook,
Twitter, Google+, LinkedIn, et… show more