Increasing the Applicablity of Quorum Protocols to Real-World Structures

18. September 2017, 14:00 , 15:30

Veranstalter:  Robert Schadek, Universität Oldenburg
Ort:  A4 2-221

Abstract:
Highly available data access is a desired goal of distributed systems. Highly available data access can be implemented by means of quorum protocols. Quorum protocols use replication of data to increase the avail-ability of access to that data. Effective quorum protocols arrange these replicas in specialized structures that allow for high availability and low costs. If these specialized structures do not have a real-world counterpart in the network topology of the distributed system, then these quorum protocols will likely be unable deliver their promised properties. In the vast majority of cases, the network topology will not match those specialized structures.


Therefore, we developed the so-called Mapping approach that efficiently paires quorum protocols and their specialized structures with the topological structures found in the realworld. The Mapping approach analyzes the properties of an existing quorum protocol when it is applied to a real-world structure. Unfortunately, the Mapping approach is computationally complex. To master this complexity, we developed a technique to apply the k-nearest neighbors method, a technique from the machine learning domain, to estimate the result of the Mapping approach. This allows us to decide whether executing the Mapping approach is a worthwhile endeavour. With a growing number of replicas, the Mapping approach becomes computational unfeasible. Therefore, we propose two new quorum protocols. These quorum protocols do not use specialized structures. Instead, they directly use the real-world structure they encounter in the distributed system. This allows them to be analyzed with respect to their properties without being compromised due to a mapping. Finally, we present the results of a thorough analysis of the performance of these new quorum protocols, as well as of the Mapping approach when applied to different efficient quorum protocols.


Betreuer: Prof. Dr.-Ing. Oliver Theel