Reliable Data Aggregation
Many applications of data aggregation require high degrees of robustness. For example, data analysis tools that use schemes based on anomaly detection risk missing outlier behavior if only partial data are aggregated. However, the expected failure rates of existing and imminent petascale systems have raised serious concerns over current recovery models, which are based on explicit state replication mechanisms like checkpointing or message logging.In response to these concerns, we have developed a technique called state compensation for robust, high-performance data aggregation in the face of transient or permanent fail-stop failures, detectable failures that cause processes to cease output production. Our central observation is that many TBŌN-based computations naturally maintain redundant state amongst the processes in the system. Intuitively, as information is propagated from the TBŌN leaves to its root, aggregation state, which generally encapsulates the history of processed information, is replicated at successive levels in the tree. State compensation uses this redundant state from processes that survive failures to compensate for information lost due to failures. This approach completely avoids explicit data replication and, generally, only requires that aggregation operations be associative and commutative. We have extended MRNet with an implementation of one of our compensation mechanisms and used this framework to show that for TBŌNs supporting up to millions of application processes, state compensation can yield millisecond failure recovery latencies with unnoticeable application perturbation. Current work in this area includes studying aggregations comprised of heterogeneous filters, implementing other compensation mechanisms and studying the applicability of the state compensation approach for more general computations.
This project is part of a UNM/Wisconsin collaboration.