Churn Possibilities and Impossibilities - Sorbonne Université Access content directly
Conference Papers Year : 2019

Churn Possibilities and Impossibilities


Churn is processes joining or leaving the peer-to-peer overlay network. We study handling of various churn variants. Cooperative churn requires leaving processes to participate in the churn algorithm while adversarial churn allows the processes to just quit. Infinite churn considers unbounded number of churning processes throughout a single computation. Unlimited churn does not place a bound on the number of concurrently churning processes. Fair churn handling requires that each churn request is eventually satisfied. A local solution involves only a limited part of the network in handing a churn request. We prove that it is impossible to handle adversarial unlimited churn. We sketch a global solution to all variants of cooperative churn and focus on local churn handling. We prove that a local fair solution to infinite churn, whether limited or unlimited, is impossible. On the constructive side, we present an algorithm that maintains a linear topology and handles the least restrictive unfair churn: infinite and unlimited. We extend this solution to a 1-2 skip list, describe enhancements for generalized skip lists and skip graphs.

Dates and versions

hal-02076478 , version 1 (22-03-2019)



Dianne Foreback, Mikhail Nesterenko, Sébastien Tixeuil. Churn Possibilities and Impossibilities. NETYS 2018 - 6th International Conference on Networked Systems, May 2018, Essaouira, Morocco. pp.303-317, ⟨10.1007/978-3-030-05529-5_20⟩. ⟨hal-02076478⟩
34 View
0 Download



Gmail Facebook X LinkedIn More