ML p(r)ior | Distributed Online Data Aggregation in Dynamic Graphs

Distributed Online Data Aggregation in Dynamic Graphs

2016-02-02
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.
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2018-12-01

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

Highlights - Most important sentences from the article

2018-11-05

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

Highlights - Most important sentences from the article

2018-05-18

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

Highlights - Most important sentences from the article

2015-10-26

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

Highlights - Most important sentences from the article

2016-05-06

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

Highlights - Most important sentences from the article

2018-09-02

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

Highlights - Most important sentences from the article

2019-01-02

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

Highlights - Most important sentences from the article

2016-11-19

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

Highlights - Most important sentences from the article

2016-07-11

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

Highlights - Most important sentences from the article

2018-09-10

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

Highlights - Most important sentences from the article

2014-04-09

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

Highlights - Most important sentences from the article

2012-07-08

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

Highlights - Most important sentences from the article

2013-02-15

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

Highlights - Most important sentences from the article

2013-08-13

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

Highlights - Most important sentences from the article

2013-07-05
1307.1690 | cs.DS

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