{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:43Z","timestamp":1750220623567,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T00:00:00Z","timestamp":1575936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>Characterizing user churn has become an important research area of networks and distributed systems, both in theoretical analysis and system design. A realistic churn model, often measured using periodic observation, should replicate two key properties of deployed systems -- (1) the arrival process and (2) the lifetime distribution of participating agents. Because users can be sampled only by sending packets to them and eliciting responses, there is an inherent tradeoff between overhead (i.e., bandwidth needed to perform the measurement) and accuracy of obtained results. Furthermore, all observations are censored, i.e., rounded up or down to a multiple of \u0394, where \u0394 is the minimum delay between repeat visits to the same user. Assuming a stationary arrival process, previous work shows that consistent (i.e., asymptotically accurate) estimation of the lifetime distribution is possible; however, the problem remains open for non-stationary cases. Questions include what distributions these methods sample when the assumptions on the arrival process are violated, under what conditions consistency is possible with existing techniques, and what avenues exist for improving their accuracy and overhead. To investigate these issues, we first use random-measure theory to develop a novel churn model that allows rather general non-stationary scenarios and even synchronized joins (e.g., flash crowds). We not only dispose with common assumptions, such as existence of arrival rate and ergodicity, but also show that this model can produce all metrics of interest (e.g., sampled lifetime distributions, bandwidth overhead) using simple expressions. We apply these results to study the accuracy of prior techniques and discover that they are biased unless user lifetimes are exponential or the arrival measure is stationary. To overcome these limitations, we then create a new lifetime-sampling technique that remains asymptotically robust under all periodic arrival measures and provide a methodology for undoing the bias in the sampled arrival rate created by missed users. We demonstrate that the proposed approach exhibits accuracy advantages and 1-2 orders of magnitude less bandwidth consumption compared to the alternatives. We finish by implementing the proposed framework and applying it to experimental data from massive crawls of Gnutella.<\/jats:p>","DOI":"10.1145\/3368510","type":"journal-article","created":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T13:21:36Z","timestamp":1575984096000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Consistent Sampling of Churn Under Periodic Non-Stationary Arrivals in Distributed Systems"],"prefix":"10.1145","volume":"4","author":[{"given":"Xiaoming","family":"Wang","sequence":"first","affiliation":[{"name":"Facebook, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Xiao","sequence":"additional","affiliation":[{"name":"Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyong","family":"Li","sequence":"additional","affiliation":[{"name":"Nvidia, Santa Clara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daren B. H.","family":"Cline","sequence":"additional","affiliation":[{"name":"Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3876-1000","authenticated-orcid":false,"given":"Dmitri","family":"Loguinov","sequence":"additional","affiliation":[{"name":"Texas A8M University, College Station, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"M. G. Baker J. H. Hartman M. D. Kupfer K. W. Shirriff and J. K. Ousterhout. 1991. Measurements of a distributed file system. In ACM SOSP. 198--212.  M. G. Baker J. H. Hartman M. D. Kupfer K. W. Shirriff and J. K. Ousterhout. 1991. Measurements of a distributed file system. In ACM SOSP. 198--212.","DOI":"10.1145\/121133.121164"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"R. Bhagwan S. Savage and G. M. Voelker. 2003. Understanding availability. In IPTPS. 256--267.  R. Bhagwan S. Savage and G. M. Voelker. 2003. Understanding availability. In IPTPS. 256--267.","DOI":"10.1007\/978-3-540-45172-3_24"},{"key":"e_1_2_1_3_1","unstructured":"F. E. Bustamante and Y. Qiao. 2003. Friendships that last: Peer lifespan and its role in P2P protocols. In Web Content Caching and Distribution.  F. E. Bustamante and Y. Qiao. 2003. Friendships that last: Peer lifespan and its role in P2P protocols. In Web Content Caching and Distribution."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Junghoo Cho and Hector Garcia-Molina. 2000. Synchronizing a database to improve freshness. In ACM SIGMOD. 117--128.  Junghoo Cho and Hector Garcia-Molina. 2000. Synchronizing a database to improve freshness. In ACM SIGMOD. 117--128.","DOI":"10.1145\/335191.335391"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/857166.857170"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Junghoo Cho and Alexandros Ntoulas. 2002. Effective change detection using sampling. In VLDB. 514--525.  Junghoo Cho and Alexandros Ntoulas. 2002. Effective change detection using sampling. In VLDB. 514--525.","DOI":"10.1016\/B978-155860869-6\/50052-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-0504-0"},{"key":"e_1_2_1_8_1","volume-title":"ITCom Conference","volume":"4868","author":"Chu J.","unstructured":"J. Chu , K. Labonte , and B. N. Levine . 2002. Availability and locality measurements of peer-to-peer file systems . In ITCom Conference , Vol. 4868 . 310--321. J. Chu, K. Labonte, and B. N. Levine. 2002. Availability and locality measurements of peer-to-peer file systems. In ITCom Conference, Vol. 4868. 310--321."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"N. Duffield C. Lund and M. Thorup. 2003. Estimating flow distributions from sampled flow statistics. In ACM SIGCOMM. 325--336.  N. Duffield C. Lund and M. Thorup. 2003. Estimating flow distributions from sampled flow statistics. In ACM SIGCOMM. 325--336.","DOI":"10.1145\/863955.863992"},{"key":"e_1_2_1_10_1","unstructured":"Zakir Durumeric Eric Wustrow and J. A. Halderman. 2013. ZMap: Fast internet-wide scanning and its security applications. In USENIX Security. 605--620.  Zakir Durumeric Eric Wustrow and J. A. Halderman. 2013. ZMap: Fast internet-wide scanning and its security applications. In USENIX Security. 605--620."},{"key":"e_1_2_1_11_1","unstructured":"Z. Ge D. R. Figueiredo S. Jaiswal J. Kurose and D. Towsley. 2003. Modeling peer-peer file sharing systems. In IEEE INFOCOM. 2188--2198.  Z. Ge D. R. Figueiredo S. Jaiswal J. Kurose and D. Towsley. 2003. Modeling peer-peer file sharing systems. In IEEE INFOCOM. 2188--2198."},{"key":"e_1_2_1_12_1","unstructured":"Gnutella. [n.d.].  Gnutella. [n.d.]."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"B. Godfrey S. Shenker and I. Stoica. 2006. Minimizing churn in distributed systems. In ACM SIGCOMM. 147--158.  B. Godfrey S. Shenker and I. Stoica. 2006. Minimizing churn in distributed systems. In ACM SIGCOMM. 147--158.","DOI":"10.1145\/1151659.1159931"},{"key":"e_1_2_1_14_1","unstructured":"S. Guha N. Daswani and R. Jain. 2006. An experimental study of the skype peer-to-peer VoIP system. In IPTPS.  S. Guha N. Daswani and R. Jain. 2006. An experimental study of the skype peer-to-peer VoIP system. In IPTPS."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"J. Heidemann Y. Pradkin R. Govindan C. Papadopoulos G. Bartlett and J. Bannister. 2008. Census and survey of the visible internet. In ACM IMC. 169--182.  J. Heidemann Y. Pradkin R. Govindan C. Papadopoulos G. Bartlett and J. Bannister. 2008. Census and survey of the visible internet. In ACM IMC. 169--182.","DOI":"10.1145\/1452520.1452542"},{"key":"e_1_2_1_16_1","unstructured":"KaZaA. [n.d.].  KaZaA. [n.d.]."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"S. Krishnamurthy S. El-Ansary E. Aurell and S. Haridi. 2005. A statistical theory of chord under churn. In IPTPS. 93--103.  S. Krishnamurthy S. El-Ansary E. Aurell and S. Haridi. 2005. A statistical theory of chord under churn. In IPTPS. 93--103.","DOI":"10.1007\/11558989_9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"A. Kumar M. Sung J. Xu and J. Wang. 2004. Data streaming algorithms for efficient and accurate estimation of flow size distribution. In ACM SIGMETRICS. 177--188.  A. Kumar M. Sung J. Xu and J. Wang. 2004. Data streaming algorithms for efficient and accurate estimation of flow size distribution. In ACM SIGMETRICS. 177--188.","DOI":"10.1145\/1012888.1005709"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Derek Leonard and Dmitri Loguinov. 2010. Demystifying service discovery: Implementing an internet-wide scanner. In ACM IMC. 109--122.  Derek Leonard and Dmitri Loguinov. 2010. Demystifying service discovery: Implementing an internet-wide scanner. In ACM IMC. 109--122.","DOI":"10.1145\/1879141.1879156"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"D. Leonard V. Rai and D. Loguinov. 2005. On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks. In ACM SIGMETRICS. 26--37.  D. Leonard V. Rai and D. Loguinov. 2005. On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks. In ACM SIGMETRICS. 26--37.","DOI":"10.1145\/1071690.1064217"},{"key":"e_1_2_1_21_1","unstructured":"D. Leonard Z. Yao X. Wang and D. Loguinov. 2005. On static and dynamic partitioning behavior of large-scale networks. In IEEE ICNP. 345--357.  D. Leonard Z. Yao X. Wang and D. Loguinov. 2005. On static and dynamic partitioning behavior of large-scale networks. In IEEE ICNP. 345--357."},{"volume-title":"On sample-path staleness in lazy data replication","author":"Li Xiaoyong","key":"e_1_2_1_22_1","unstructured":"Xiaoyong Li , Daren B. H. Cline , and Dmitri Loguinov . 2015. On sample-path staleness in lazy data replication . In IEEE INFOCOM. 1104--1112. Xiaoyong Li, Daren B. H. Cline, and Dmitri Loguinov. 2015. On sample-path staleness in lazy data replication. In IEEE INFOCOM. 1104--1112."},{"volume-title":"Temporal update dynamics under blind sampling","author":"Li Xiaoyong","key":"e_1_2_1_23_1","unstructured":"Xiaoyong Li , Daren B. H. Cline , and Dmitri Loguinov . 2015. Temporal update dynamics under blind sampling . In IEEE INFOCOM. 1634--1642. Xiaoyong Li, Daren B. H. Cline, and Dmitri Loguinov. 2015. Temporal update dynamics under blind sampling. In IEEE INFOCOM. 1634--1642."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2005.07.014"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"D. Liben-Nowell H. Balakrishnan and D. Karger. 2002. Analysis of the evolution of peer-to-peer networks. In ACM PODC. 233--242.  D. Liben-Nowell H. Balakrishnan and D. Karger. 2002. Analysis of the evolution of peer-to-peer networks. In ACM PODC. 233--242.","DOI":"10.1145\/571825.571863"},{"key":"e_1_2_1_26_1","unstructured":"A. Makowski B. Melamed and W. Whitt. 1989. On averages seen by arrivals in discrete time. In IEEE CDC. 1084--1086.  A. Makowski B. Melamed and W. Whitt. 1989. On averages seen by arrivals in discrete time. In IEEE CDC. 1084--1086."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Christopher Olston and Sandeep Pandey. 2008. Recrawl scheduling based on information longevity. In WWW. 437--446.  Christopher Olston and Sandeep Pandey. 2008. Recrawl scheduling based on information longevity. In WWW. 437--446.","DOI":"10.1145\/1367497.1367557"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.814666"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"D. Qiu and R. Srikant. 2004. Modeling and performance analysis of bittorrent-like peer-to-peer networks. In ACM SIGCOMM. 367--378.  D. Qiu and R. Srikant. 2004. Modeling and performance analysis of bittorrent-like peer-to-peer networks. In ACM SIGCOMM. 367--378.","DOI":"10.1145\/1030194.1015508"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"S. Resnick. 1987. Extreme Values Regular Variation and Point Processes. Springer-Verlag.  S. Resnick. 1987. Extreme Values Regular Variation and Point Processes. Springer-Verlag.","DOI":"10.1007\/978-0-387-75953-1"},{"key":"e_1_2_1_31_1","first-page":"1","article-title":"Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design","volume":"6","author":"Ripeanu M.","year":"2002","unstructured":"M. Ripeanu , I. Foster , and A. Iamnitchi . 2002 . Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design . IEEE Internet Comput. J. 6 , 1 (Jan.-Feb. 2002), 50--57. M. Ripeanu, I. Foster, and A. Iamnitchi. 2002. Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Comput. J. 6, 1 (Jan.-Feb. 2002), 50--57.","journal-title":"IEEE Internet Comput. J."},{"volume-title":"USENIX Annual Technical Conference. 41--54","author":"Roselli D.","key":"e_1_2_1_32_1","unstructured":"D. Roselli , J. R. Lorch , and T. E. Anderson . 2000. A comparison of file system workloads . In USENIX Annual Technical Conference. 41--54 . D. Roselli, J. R. Lorch, and T. E. Anderson. 2000. A comparison of file system workloads. In USENIX Annual Technical Conference. 41--54."},{"key":"e_1_2_1_33_1","first-page":"156","article-title":"A measurement study of peer-to-peer file sharing systems","volume":"4673","author":"Saroiu S.","year":"2002","unstructured":"S. Saroiu , P. K. Gummadi , and S. D. Gribble . 2002 . A measurement study of peer-to-peer file sharing systems . In SPIE\/ACM Multimedia Computing and Networking , Vol. 4673. 156 -- 170 . S. Saroiu, P. K. Gummadi, and S. D. Gribble. 2002. A measurement study of peer-to-peer file sharing systems. In SPIE\/ACM Multimedia Computing and Networking, Vol. 4673. 156--170.","journal-title":"SPIE\/ACM Multimedia Computing and Networking"},{"key":"e_1_2_1_34_1","unstructured":"Moritz Steiner Ernst W. Biersack and Taoufik Ennajjary. 2007. Actively monitoring peers in kad. In IPTPS.  Moritz Steiner Ernst W. Biersack and Taoufik Ennajjary. 2007. Actively monitoring peers in kad. In IPTPS."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"D. Stutzbach and R. Rejaie. 2006. Understanding churn in peer-to-peer networks. In ACM IMC. 189--202.  D. Stutzbach and R. Rejaie. 2006. Understanding churn in peer-to-peer networks. In ACM IMC. 189--202.","DOI":"10.1145\/1177080.1177105"},{"volume-title":"Stochastic analysis and improvement of the reliability of DHT-based multicast","author":"Tan Guang","key":"e_1_2_1_36_1","unstructured":"Guang Tan and Stephen Jarvis . May 2007. Stochastic analysis and improvement of the reliability of DHT-based multicast . In IEEE INFOCOM. 2198--2206. Guang Tan and Stephen Jarvis. May 2007. Stochastic analysis and improvement of the reliability of DHT-based multicast. In IEEE INFOCOM. 2198--2206."},{"key":"e_1_2_1_37_1","unstructured":"Jing Tian and Yafei Dai. 2007. Understanding the dynamic of peer-to-peer systems. In IPTPS.  Jing Tian and Yafei Dai. 2007. Understanding the dynamic of peer-to-peer systems. In IPTPS."},{"key":"e_1_2_1_38_1","first-page":"3","article-title":"Residual-based estimation of peer and link lifetimes in P2P networks","volume":"17","author":"Wang X.","year":"2009","unstructured":"X. Wang , Z. Yao , and D. Loguinov . 2009 . Residual-based estimation of peer and link lifetimes in P2P networks . IEEE\/ACM Trans. Networking 17 , 3 (Jun. 2009), 726--739. X. Wang, Z. Yao, and D. Loguinov. 2009. Residual-based estimation of peer and link lifetimes in P2P networks. IEEE\/ACM Trans. Networking 17, 3 (Jun. 2009), 726--739.","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"X. Wang Z. Yao Y. Zhang and D. Loguinov. 2009. Robust lifetime measurement in large-scale P2P systems with non-stationary arrivals. In IEEE P2P. 101--110.  X. Wang Z. Yao Y. Zhang and D. Loguinov. 2009. Robust lifetime measurement in large-scale P2P systems with non-stationary arrivals. In IEEE P2P. 101--110.","DOI":"10.1109\/P2P.2009.5284550"},{"key":"e_1_2_1_40_1","unstructured":"Wikipedia. [n.d.].  Wikipedia. [n.d.]."},{"key":"e_1_2_1_41_1","unstructured":"Wikipedia Dumps. [n.d.].  Wikipedia Dumps. [n.d.]."},{"key":"e_1_2_1_42_1","unstructured":"Wikipedia Stats. [n.d.].  Wikipedia Stats. [n.d.]."},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Mohan Yang Haixun Wang Lipyeow Lim and Min Wang. 2010. Optimizing content freshness of relations extracted from the web using keyword search. In ACM SIGMOD. 819--830.  Mohan Yang Haixun Wang Lipyeow Lim and Min Wang. 2010. Optimizing content freshness of relations extracted from the web using keyword search. In ACM SIGMOD. 819--830.","DOI":"10.1145\/1807167.1807256"},{"key":"e_1_2_1_44_1","first-page":"9","article-title":"Unifying models of churn and resilience for unstructured P2P graphs","volume":"25","author":"Yao Z.","year":"2014","unstructured":"Z. Yao , D. B. H. Cline , X. Wang , and D. Loguinov . 2014 . Unifying models of churn and resilience for unstructured P2P graphs . IEEE Trans. Parallel and Distributed Systems 25 , 9 (Sep. 2014), 2475--2485. Z. Yao, D. B. H. Cline, X. Wang, and D. Loguinov. 2014. Unifying models of churn and resilience for unstructured P2P graphs. IEEE Trans. Parallel and Distributed Systems 25, 9 (Sep. 2014), 2475--2485.","journal-title":"IEEE Trans. Parallel and Distributed Systems"},{"volume-title":"On node isolation under churn in unstructured P2P networks with heavy-tailed lifetimes","author":"Yao Zhongmei","key":"e_1_2_1_45_1","unstructured":"Zhongmei Yao , Xiaoming Wang , Derek Leonard , and Dmitri Loguinov . 2007. On node isolation under churn in unstructured P2P networks with heavy-tailed lifetimes . In IEEE INFOCOM. 2126--2134. Zhongmei Yao, Xiaoming Wang, Derek Leonard, and Dmitri Loguinov. 2007. On node isolation under churn in unstructured P2P networks with heavy-tailed lifetimes. In IEEE INFOCOM. 2126--2134."}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368510","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3368510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:26Z","timestamp":1750197686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3368510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,10]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3368510"],"URL":"https:\/\/doi.org\/10.1145\/3368510","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2019,12,10]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}