A Statistical Theory of Chord under Churn

@misc{citeulike:488638, abstract = {Most earlier studies of Distributed Hash Tables (DHTs) under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general.}, author = {Krishnamurthy, Supriya and El-Ansary, Sameh and Aurell, Erik and Haridi, Seif }, citeulike-article-id = {488638}, eprint = {cs.NI/0501069}, keywords = {0-student-shelaev, p2p}, month = {Jan}, posted-at = {2006-02-01 15:40:08}, priority = {3}, title = {A Statistical Theory of Chord under Churn}, url = {http://arxiv.org/abs/cs.NI/0501069}, year = {2005} }

TY - ELEC ID - citeulike:488638 L3 - citeulike-article-id:488638 TI - A Statistical Theory of Chord under Churn N2 - Most earlier studies of Distributed Hash Tables (DHTs) under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general. KW - 0-student-shelaev KW - p2p AU - Krishnamurthy, Supriya AU - El-Ansary, Sameh AU - Aurell, Erik AU - Haridi, Seif PY - 2005/Jan/24/ UR - http://arxiv.org/abs/cs.NI/0501069 ER -