Love and Strife in large-scale decentralized systems

Large-scale complex decentralized systems are governed by synergies, opposing forces and trade-offs. Empedocles would describe these properties and features as the result of Love and Strife that elements of nature appear: “These (elements) never cease changing place continually, now being all united by Love into one, now each borne apart by the hatred engendered of Strife, until they are brought together in the unity of the all, and become subject to it.” Aggregation of information is required in decentralized system and their applications to make available aggregates locally that are computed by aggregating a distributed sample of information in a network. The average load of a system, the total bandwidth available in a network or the size of a network are some aggregation examples. Aggregates do not only simply provide a summarized knowledge to users but they can be used to dynamically adapt the operations and behavior of a system and align this system to its objectives. The problem of dynamic and large-scale decentralized aggregation is part of my PhD research.

I have recently had the opportunity to present DIAS, the Dynamic Intelligent Aggregation Service at TU Dresden. I was invited to give this talk by Professor Christof Fetzer. His group has developed the XSiena Bloom Filter library used by DIAS to detect aggregation inconsistencies that cause inaccuracies to the computed aggregates. My interaction with Professor Fetzer and his group has been very constructive by having an in-depth discussion and exchanging various ideas about DIAS, its performance and fault-teolerance.

An abstract of my talk follows:

 

Dynamic Intelligent Aggregation Services – Love and Strife in Large-scale Decentralized Systems

The computation of aggregate information provides crucial management information to distributed applications. Aggregate information may concern measurements such as the average load, the maximum bandwidth capacity or the size of a network/system. Performing centralized aggregation is straightforward as the input sample of an aggregation function is available at a single location. However, centralized aggregation is not always an option or desired. Aggregation of information distributed in large-scale decentralized systems of arbitrary interconnected nodes is challenging. Existing methodologies for decentralized aggregation have three crucial limitations: (i) They are designed to compute specific aggregation functions, e.g. average or count. (ii) They are based on specific routing mechanisms, e.g. trees, to prevent duplicates. (iii) They cannot adapt the aggregates in case the input sample changes, and therefore they perform expensive recomputations. This presentation illustrates an alternative mechanism for decentralized aggregation: DIAS, the Dynamic Intelligent Aggregation Service. DIAS is able to compute almost any aggregation function over an unstructured overlay network and under a dynamically changing input sample. Both (i) duplicate and (ii) outdated input values are detected by introducing a distributed consistency mechanism based on probabilistic data structures: bloom filters. Experimental evaluation shows that DIAS computes aggregates accurately even under the effect of false positives in the bloom filters.