Source-linked AI summary
A Survey of Distributed Data Aggregation Algorithms
Paulo Jesus, Carlos Baquero, Paulo Sérgio Almeida
TL;DR
Distributed aggregation enables decentralized computation of global properties, but the variety of algorithms and their trade-offs complicate technique selection. This survey formalizes aggregation, organizes existing algorithms into a taxonomy, and provides selection guidelines; it also identifies important limitations in current approaches and network settings.
Problem
The diversity of distributed aggregation algorithms and their trade-offs makes it difficult to choose an approach for a specific application and environment.
Method
The survey formally defines aggregation, classifies functions and algorithms, describes representative techniques, and summarizes their complexity and scenario suitability.
Results
The survey organizes existing aggregation algorithms by communication and computation perspectives and summarizes their principal characteristics for practical selection.
Takeaways & Limitations
Algorithm choice should be guided by application requirements and environment, including communication, computation, accuracy, fault tolerance, and network dynamics.
Takeaways & Limitations
No ideal general solution exists because existing techniques have shortcomings, and further work is needed for churn, message loss, and mutable inputs.
Abstract
from arXiv · showhide
Distributed data aggregation is an important task, allowing the decentralized determination of meaningful global properties, that can then be used to direct the execution of other applications. The resulting values result from the distributed computation of functions like COUNT, SUM and AVERAGE. Some application examples can found to determine the network size, total storage capacity, average load, majorities and many others. In the last decade, many different approaches have been proposed, with different trade-offs in terms of accuracy, reliability, message and time complexity. Due to the considerable amount and variety of aggregation algorithms, it can be difficult and time consuming to determine which techniques will be more appropriate to use in specific settings, justifying the existence of a survey to aid in this task. This work reviews the state of the art on distributed data aggregation algorithms, providing three main contributions. First, it formally defines the concept of aggregation, characterizing the different types of aggregation functions. Second, it succinctly describes the main aggregation techniques, organizing them in a taxonomy. Finally, it provides some guidelines toward the selection and use of the most relevant techniques, summarizing their principal characteristics.
1 Introduction
Distributed aggregation computes global properties without centralization, supporting applications such as network sizing, load balancing, and storage accounting. This survey addresses the difficulty of choosing among diverse techniques with different trade-offs.
- Motivation: Aggregation determines system-wide properties decentrally, including network size, average load, and total free disk space.These values can guide DHT construction, gossip configuration, local load balancing, and other distributed applications.
- Motivation: Network-size estimation supports P2P DHT construction, gossip target selection, and quorum setup in dynamic settings.
- Research gap: Existing algorithms trade off accuracy, time, communication, and fault tolerance, making global statistics difficult under faults and network dynamism.
- Research gap: Earlier surveys focus mainly on wireless sensor-network aggregation, including resource constraints, energy efficiency, security, and information fusion.
- Survey scope: This survey offers a network-independent view, defines distributed aggregation, classifies solutions, discusses complexity, and gives application-selection guidelines.
2 Problem Definition
The paper formalizes aggregation over multisets and identifies properties that determine how functions can be computed in distributed networks. It distinguishes decomposability and duplicate sensitiveness as central dimensions for distributed suitability and fault tolerance.
- Aggregation definition: An aggregation function maps a multiset from input domain I to an output domain O while summarizing the input.Multisets make order irrelevant and allow repeated values.
- Decomposability: Decomposable functions support distributed computation by splitting the input into sub-multisets and combining intermediate results.Self-decomposable functions combine results directly in the output domain, whereas general decomposable functions may require an auxiliary domain.
- Decomposability: Min, max, sum, and count are self-decomposable because their partition results combine through associative and commutative operators.The paper gives sum, count, and min as examples of such combination rules.
- Decomposability: Average is decomposable but not self-decomposable, requiring auxiliary intermediate values before the final result is computed.The example uses an auxiliary pair domain and a final division operation.
- Duplicate sensitiveness: Idempotent operators can support retransmissions and multipath processing, improving fault tolerance and decentralized processing for suitable functions.The paper notes that this approach is not always possible, including for distinct count.
- Duplicate sensitiveness: Duplicate-insensitive functions depend only on the support set, unlike sum and count, which depend on element multiplicities.
- Taxonomy: The taxonomy ranks non-decomposable and duplicate-sensitive functions as harder to aggregate distributively than their respective alternatives.A duplicate-insensitive approximation using an idempotent operator can provide fault tolerance for some aggregates.
3 Taxonomy
The survey classifies distributed data aggregation algorithms from communication and computation perspectives. Communication concerns routing protocols and network topologies, while computation concerns aggregation functions and underlying principles.
- The taxonomy organizes algorithms according to communication and computation perspectives.These perspectives are presented in Tables 2 and 3.
- The communication perspective covers routing protocols and intrinsic network topologies supporting aggregation.
- The computation perspective identifies the aggregation functions algorithms compute and the principles underlying them.
- Although algorithm attributes are multidimensional, the survey selects two perspectives for clearer presentation.
3.1 Communication
The survey classifies distributed aggregation algorithms by communication structure and describes structured, unstructured, and hybrid approaches, including their efficiency, robustness, and topology requirements.
- Communication taxonomy: Three communication classes are identified: structured, unstructured, and hybrid algorithms.The taxonomy is based on communication patterns and associated network topologies.
- Structured approaches: Structured algorithms depend on specific routing topologies, which can limit use in dynamic environments and expose aggregation to routing failures.Tree-based structures can fail when a node or link disrupts delivery from entire subtrees.
- Unstructured approaches: Unstructured algorithms avoid predefined topologies and commonly use flooding, random walks, or gossip communication patterns.Gossip-based approaches emphasize simplicity, scalability, and robustness.
- Hybrid approaches: Hybrid approaches combine routing strategies to balance the efficiency and accuracy of hierarchical schemes with the fault resilience of gossip schemes.Their goal is to reduce the weaknesses of the component approaches while retaining their advantages.
- Representative approaches: The survey presents tree-based services, gossip protocols, virtual rings, and attribute hierarchies as distinct communication-based aggregation approaches.Examples include TAG, Push-Sum, Astrolabe, and virtual-ring network-size estimation.
- Structured approaches: Multiple-parent DAG routing improves tolerance to message loss over traditional trees, but increases energy consumption and does not eliminate dependence on parent quality.The approach uses path redundancy, while some nodes may still have only one parent.
3.2 Computation
The computation taxonomy identifies six algorithmic classes and relates them to supported aggregation functions, accuracy, reliability, and resource trade-offs. The survey contrasts hierarchical, averaging, sampling, sketch, and flow-based approaches, while also describing representative algorithms and combinations.
- Computation taxonomy: Six computation classes are identified: Hierarchical, Averaging, Sketches, Digests, Deterministic, and Sampling.The taxonomy associates these categories with different kinds of aggregation functions.
- Trade-offs and examples: Distributed aggregation algorithms differ in supported functions, accuracy, reliability, and communication or computational complexity, motivating taxonomy-guided selection.The survey also discusses hybrid designs and practical variants, including gossip-based execution and fault-handling mechanisms.
- Sampling and sketches: Sampling schemes provide lightweight but inaccurate probabilistic counts, whereas sketch-based approaches claim higher accuracy and lower variance while addressing message-size constraints.Sampling asks only part of the network to participate; the sketch results are reported relative to existing sketch schemes.
- Hierarchical approaches: Hierarchical algorithms compute any decomposable function exactly when fault-free, but a single failure can lose all data beneath it.They distribute centralized-equivalent processing and memory across the network, without fault tolerance.
- Averaging approaches: Averaging algorithms iteratively exchange partial aggregates so nodes converge to the global result, while supporting decomposable and duplicate-sensitive functions derived from averages.They use simple arithmetic operations and few computational resources, but mass conservation is required for correctness.
- Averaging approaches: Flow Updating tolerates message loss by keeping inputs unchanged and using idempotent flow updates, delaying convergence without changing the correct limit.The approach is also reported to tolerate node crashes and churn, with protocol restarts required for churn.
4 Summary and Practical Guidelines
The survey compares aggregation classes by accuracy, fault tolerance, communication cost, speed, and routing assumptions, then recommends techniques for different operating conditions.
- Sketch approaches: Sketch techniques work independently of routing topology and provide fast approximations in faulty scenarios, requiring D rounds and ¯dND messages.Extrema Propagation is recommended for a better and unbiased estimate than other sketch algorithms.
- Averaging algorithms: Averaging algorithms converge independently of routing topology and can achieve high-accuracy results at all nodes in faulty environments, but require more time and messages than sketches.Their execution time depends on target accuracy and convergence proceeds exponentially with linear rounds.
- Averaging algorithms: Flow Updating is recommended for dynamic, faulty scenarios requiring accurate estimates without strict message constraints because it adapts continuously without restart.Other averaging approaches are reported to have dependability issues and may not converge to the correct value.
- Sampling and aggregation scope: Sampling techniques generally offer irregular, inaccurate approximations, are usually restricted to count, and can be slow or unreliable under faults.The survey notes that more complex aggregates may be needed when global load averages do not describe value distributions.
5 Final Remarks and Future Directions
The survey formalizes distributed aggregation, organizes existing algorithms into a taxonomy, and summarizes their suitability across scenarios. It concludes that no ideal general solution exists and identifies complex aggregates and dynamic faults as priorities for further research.
- Contributions: The survey formally defines aggregation functions, proposes a taxonomy from communication and computation perspectives, and summarizes algorithm characteristics with scenario-specific guidelines.These contributions are intended to provide a quick, comprehensive overview of the state of the art.
- Conclusion: The survey concludes that no ideal general solution exists because all existing distributed aggregation techniques have pitfalls.The paper therefore expects continued research in the field.
- Future directions: Future work should improve estimation of statistical distributions and support for complex aggregates, churn, message loss, and continuously changing input values.The paper associates existing complex-aggregate approaches with limitations in accuracy and resource consumption.