NDLI: Aggregation in dynamic networks

Please wait, while we are loading the content...

Faster randomized consensus with an oblivious adversary

Random walks which prefer unvisited edges.: exploring high girth even degree expanders in linear time.

The cost of fault tolerance in multi-party communication complexity

Brief announcement: what can be computed without communication?

Wait-freedom with advice

Distributed selfish load balancing with weights and speeds

Distributed maximal matching: greedy is optimal

Aggregation in dynamic networks

Brief announcement: achieving reliability in master-worker computing via evolutionary dynamics

Asynchronous failure detectors

A simple approach for adapting continuous load balancing processes to discrete settings

On the (limited) power of non-equivocation

Brief announcement: network formation games can give rise to realistic networks

Distributed algorithms for scheduling on line and tree networks

Faster than optimal snapshots (for a while): preliminary version

On the liveness of transactional memory

Information spreading in dynamic graphs

The communication complexity of distributed task allocation

Brief announcement: distributed algorithms for throughput performance in wireless networks

Universal constructions that ensure disjoint-access parallelism and wait-freedom

Making evildoers pay: resource-competitive broadcast in sensor networks

Lower bounds for local approximation

Distributed connectivity of wireless networks

Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary

Simulations and reductions for colorless tasks

Dynamic packet scheduling in wireless networks

On the price of equivocation in byzantine agreement

Brief announcement: network-destabilizing attacks

Optimal distributed all pairs shortest paths and applications

Strongly linearizable implementations: possibilities and impossibilities

On the time and space complexity of randomized test-and-set

Coalescing random walks and voting on graphs

Collaborative search on the plane without communication

Brief announcement: distributed cryptography using trinc

Generalized lattice agreement

Distributed public key schemes secure against continual leakage

Weak models of distributed computing, with connections to modal logic

Leader election in shared spectrum radio networks

Brief announcement: maintaining large dense subgraphs on dynamic networks

A closer look at fault tolerance

Competitive and fair throughput for co-existing networks under adversarial interference

Byzantine broadcast in point-to-point networks using local linear coding

Brief announcement: tolerating permanent and transient value faults

Iterative approximate byzantine consensus in arbitrary directed graphs

Brief announcement: reconfigurable state machine replication from non-reconfigurable building blocks

Brief announcement: decentralized network supercomputing in the presence of malicious and crash-prone workers

Brief announcement: efficient causality tracking in distributed storage systems with dotted version vectors

Brief announcement: all-to-all gradecast using coding with byzantine failures

Brief announcement: order-preserving renaming in synchronous message passing systems with byzantine faults

Brief announcement: increasing the power of the iterated immediate snapshot model with failure detectors

Brief announcement: there are plenty of tasks weaker than perfect renaming and stronger than set agreement

Brief announcement: an obstacle to scalability in wireless networks

Brief announcement: delay or deliver dilemma in organization networks

Brief announcement: waiting in dynamic networks

Brief announcement: on the resilience of routing tables

Brief announcement: live streaming with utilities, quality and cost

Brief announcement: optimal amortized secret sharing with cheater identification

Brief announcement: a tight RMR lower bound for randomized mutual exclusion

Brief announcement: a calculus of policy-based routing systems

Brief announcement: efficient optimally resilient statistical AVSS and its applications

Brief announcement: From sequential to concurrent: correctness and relative efficiency

Aggregation in dynamic networks

Content Provider	ACM Digital Library
Author	Newport, Calvin Cornejo, Alejandro Gilbert, Seth
Abstract	The aggregation problem assumes that every process starts an execution with a unique token (an abstraction for data). The goal is to collect these tokens at a minimum number of processes by the end of the execution. This problem is particularly relevant to mobile networks where peer-to-peer communication is cheap (e.g., using 802.11 or Bluetooth), but uploading data to a central server can be costly (e.g., using 3G/4G). With this in mind, we study this problem in a dynamic network model, in which the communication graph can change arbitrarily from round to round. We start by exploring global bounds. First we prove a negative result that shows that in general dynamic graphs no algorithm can achieve any measure of competitiveness against the optimal offline algorithm. Guided by this impossibility result, we focus our attention to dynamic graphs where every node interacts, at some point in the execution, with at least a p-fraction of the total number of nodes in the graph. We call these graphs p-clusters. We describe a distributed algorithm that in p-clusters aggregates the tokens to O(log n) processes with high probability. We then turn our attention to local bounds. Specifically we ask whether its possible to aggregate to O(log n) processes in parts of the graph that locally form a p-cluster. Here we prove a negative result: this is only possible if the local p-clusters are sufficiently isolated from the rest of the graph. We then match this result with an algorithm that achieves the desired aggregation given (close to) the minimal required p-cluster isolation. Together, these results imply a "paradox of connectivity": in some graphs, increasing connectivity can lead to inherently worse aggregation performance. We conclude by considering what seems to be a promising performance metric to circumvent our lower bounds for local aggregation algorithms. However, perhaps surprisingly, we show that no aggregation algorithm can perform well with respect to this metric, even in very well connected and very well isolated clusters.
Starting Page	195
Ending Page	204
Page Count	10
File Format	PDF
ISBN	9781450314503
DOI	10.1145/2332432.2332468
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Aggregation Dynamic graphs
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Non-altering time scales for aggregation of dynamic networks into series of graphs

Efficient aggregation for graph summarization

Geographic gossip: efficient aggregation for sensor networks

Quantitative Evaluation of Snapshot Graphs for the Analysis of Temporal Networks

Random walks in time-graphs

Optimized query planning of continuous aggregation queries in dynamic data dissemination networks

Brief announcement: waiting in dynamic networks

Scalable data aggregation for dynamic events in sensor networks

Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs

Aggregation in dynamic networks

Similar Documents

Non-altering time scales for aggregation of dynamic networks into series of graphs

Efficient aggregation for graph summarization

Geographic gossip: efficient aggregation for sensor networks

Quantitative Evaluation of Snapshot Graphs for the Analysis of Temporal Networks

Random walks in time-graphs

Optimized query planning of continuous aggregation queries in dynamic data dissemination networks

Brief announcement: waiting in dynamic networks

Scalable data aggregation for dynamic events in sensor networks

Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs

Aggregation in dynamic networks