Churn Possibilities and Impossibilities

Abstract : 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.
Complete list of metadatas

https://hal.sorbonne-universite.fr/hal-02076478
Contributor : Sébastien Tixeuil <>
Submitted on : Friday, March 22, 2019 - 10:32:56 AM
Last modification on : Friday, July 5, 2019 - 3:26:03 PM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

36