Many distributed applications in the current Internet (e.g., cloud computing, world-scale web search, online banking, content-distribution systems, social networks) are now massively replicated, which ensures unsurpassed data robustness and scalability. However, constant data churn (i.e., update of the source) and delayed synchronization lead to staleness, which refers to deviation of the information being served to clients and/or processed by the system from that at the source. This project studied replication under non-Poisson update processes, general cost functions, and multi-hop operation. Until now, these topics have remained virtually unexplored, which prevented accurate characterization of extreme-scale distributed systems, creation of alternative replication paradigms, and new theoretical insight into data churn. In this work, we addressed these issues by pioneering a stochastic theory of data replication that could tackle non-trivial dependency issues in synchronization of general non-Poisson point processes, designed more accurate sampling and prediction algorithms for measuring data churn, solved novel multi-source and multi-replica joint staleness-optimization problems, established new fundamental understanding of cooperative and multi-hop replication, and modeled non-stationary update processes of real sources. 

Accurate modeling of data churn has remained one of the most elusive topics in the literature, while being of paramount importance to improving the design and scalability of existing networks, databases, cloud applications, and large-scale distributed systems. The theory component of this work formalized data evolution using random process theory and achieved novel results in the understanding of staleness, our ability to sample network sources through random observation, and recovery of interval-censored data using non-parametric estimation algorithms. By studying the effect of various data-update distributions and refresh techniques on staleness, this work also produced insight into how to better design future replication solutions and achieve higher resilience to failure in existing systems. The experimental part of this work measured existing Internet sources (such as Wikipedia and Yelp) to verify the assumptions and performance of the proposed models and created novel data-churn characterization that achieved higher fidelity in practice than prior techniques. This, coupled with our unifying modeling framework, has increased the body of practical and theoretical knowledge about caching networks, their performance, optimality, and various avenues for achieving more scalable operation. 

This project blended a variety of cross-disciplinary scientific areas including random process theory, stochastic modeling, renewal theory, databases, content retrieval, networking, distributed systems, and experimental Internet data sampling and measurement. The educational component of this project reached out to the student population at Texas A&M and engaged them in research activities they would not be otherwise exposed to. Outcomes include attraction of students to cross-disciplinary research programs, training of well-rounded PhD students knowledgeable in both theoretical and experimental aspects of large-scale networked systems, engagement of under-represented student groups in STEM fields, and information dissemination through publications/presentations.

Last Modified: 11/30/2017
Modified by: Dmitri Loguinov