Download Slides (PDF, converted from KEYNOTE)

By Francisco Maia, HASLab /INESC TEC and University of Minho

Abstract. Considering the state-of-the-art systems for data management, it is observable that they exhibit two main frailties when deployed in a large scale system. On one hand, coordination protocols used in traditional relational database management systems do not perform well when the system grows beyond tens of nodes. On the other hand, data management approaches that relax consistency guarantees, thus avoiding coordination, struggle with high levels of system churn.

In this dissertation, we present a completely decentralized, coordination- free, scalable and robust data store. Our design is aimed at environments with several thousands of nodes and high levels of churn. Offering the current ubiquitous key-value data structures and programming interfaces, we describe how to overcome challenges raised by the need to distribute data - essential for load balancing, to replicate data - the crux of fault tolerance, and to route requests - key to performability.

Alongside the design of our data store, we make several contributions in the context of distributed systems slicing. We propose a novel slicing protocol that overcomes state-of-the-art limitations. Additionally, we propose a novel epidemic algorithm for scalable and decentralized organization of system nodes into groups. This algorithm is used as an alternative to slicing at the core of our system. It organises nodes into groups of parameterizable size without the need to have nodes knowing the system size. The contributions made on slicing protocols and the proposed group construction protocol are independent from the design of the data store. They are generic and can also be used as building blocks for other applications.

Keywords. Epidemic protocols; key-value stores; scalability.

Coffee session: 10:30AM in  Auditorium A2, 2nd floor.
Talk session: 10:45AM in Auditorium A2, 2nd floor.