Abstract
Slicing a large-scale distributed system is the process of autonomously partitioning its nodes into k groups, named slices. Slicing is associated to an order on node-specific criteria, such as available storage, uptime, or bandwidth. Each slice corresponds to the nodes between two quantiles in a virtual ranking according to the criteria.
For instance, a system can be split in three groups, one with nodes with the lowest uptimes, one with nodes with the highest uptimes, and one in the middle. Such a partitioning can be used by applications to assign different tasks to different groups of nodes, e.g., assigning critical tasks to the more powerful or stable nodes and less critical tasks to other slices.
Assigning a slice to each node in a large-scale distributed system, where no global knowledge of nodes’ criteria exists, is not trivial. Recently, much research effort was dedicated to guaranteeing a fast and correct convergence in comparison to a global sort of the nodes.
Unfortunately, state-of-the-art slicing protocols exhibit flaws that preclude their application in real scenarios, in particular with respect to cost and stability. In this paper, we identify steadiness issues where nodes in a slice border constantly exchange slice and large memory requirements for adequate convergence, and provide practical solutions for the two. Our solutions are generic and can be applied to two different state-of-the-art slicing protocols with little effort and while preserving the desirable properties of each. The effectiveness of the proposed solutions is extensively studied in several simulated experiments.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Almeida, P.S., Baquero, C., Preguiça, N., Hutchison, D.: Scalable Bloom Filters. Information Processing Letters (2007)
Bhagwan, R., Savage, S., Voelker, G.M.: Understanding availability. In: International Workshop on Peer-to-Peer Systems (2003)
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM (1970)
Cheng, K., Xiang, L., Iwaihara, M.: Time-decaying Bloom Filters for data streams with skewed distributions. In: International Workshop on Research Issues in Data Engineering: Stream Data Mining and Applications (2005)
Eugster, P.T., Guerraoui, R., Handurukande, S.B., Kouznetsov, P., Kermarrec, A.-M.: Lightweight probabilistic broadcast. ACM Transactions on Computer Systems (2003)
Fernandez, A., Gramoli, V., Jimenez, E., Kermarrec, A.-M., Raynal, M.: Distributed Slicing in Dynamic Systems. In: International Conference on Distributed Computing Systems (2007)
Gantz, J.: The Diverse and Exploding Digital Universe. Technical report, IDC White Paper - sponsored by EMC (2008)
Gramoli, V., Vigfusson, Y., Birman, K., Kermarrec, A.-M., van Renesse, R.: Sliver, A fast distributed slicing algorithm. In: ACM Symposium on Principles of Distributed Computing (2008)
Gramoli, V., Vigfusson, Y., Birman, K., Kermarrec, A.-M., van Renesse, R.: Slicing Distributed Systems. IEEE Transactions on Computers (2009)
Jelasity, M., Voulgaris, S., Guerraoui, R., Kermarrec, A.-M., Van Steen, M.: Gossip-based peer sampling. ACM Transactions on Computer Systems (2007)
Matos, M., Vilaca, R., Pereira, J., Oliveira, R.: An epidemic approach to dependable key-value substrates. In: IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (2011)
Montresor, A., Jelasity, M.: PeerSim: A scalable P2P simulator. In: International Conference on Peer-to-Peer (2009)
Montresor, A., Jelasity, M., Babaoglu, O.: Decentralized Ranking in Large-Scale Overlay Networks (2008)
Pruteanu, A., Iyer, V., Dulman, S.: ChurnDetect: A Gossip-Based Churn Estimator for Large-Scale Dynamic Networks. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011, Part II. LNCS, vol. 6853, pp. 289–301. Springer, Heidelberg (2011)
Rivière, E., Voulgaris, S.: Gossip-Based Networking for Internet-Scale Distributed Systems. In: Babin, G., Stanoevska-Slabeva, K., Kropf, P. (eds.) MCETECH 2011. LNBIP, vol. 78, pp. 253–284. Springer, Heidelberg (2011)
Sutter, H.: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb’s Journal (2005)
Voulgaris, S., Gavidia, D., Van Steen, M.: CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays. Journal of Network and Systems Management (2005)
Wang, F., Xiong, Y., Liu, J.: mTreebone: A Collaborative Tree-Mesh Overlay Network for Multicast Video Streaming. IEEE Transactions on Parallel and Distributed Systems (2010)
Yoon, M.: Aging Bloom Filter with Two Active Buffers for Dynamic Sets. IEEE Transactions on Knowledge and Data Engineering (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Maia, F., Matos, M., Rivière, E., Oliveira, R. (2012). Slead: Low-Memory, Steady Distributed Systems Slicing. In: Göschka, K.M., Haridi, S. (eds) Distributed Applications and Interoperable Systems. DAIS 2012. Lecture Notes in Computer Science, vol 7272. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30823-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-30823-9_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30822-2
Online ISBN: 978-3-642-30823-9
eBook Packages: Computer ScienceComputer Science (R0)