05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Filters

2013 - 20193

Settings

Institute: search.filters.UBSInstitut.Institut für Parallele und Verteilte SystemeStart date: 2010End date: 2019Author: search.filters.author.Mayer, Christian

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    ItemOpen Access
    Scalable data retrieval in a mobile environment
    (2014) Mayer, Christian
    Retrieving multidimensional data out of distributed systems becomes increasingly important. But applications of these systems are often not only interested in data vectors that match certain queries. Instead, many applications demand for retrieval of data with high quality. In this thesis, we design a distributed system that can be used by applications to retrieve data of high quality for arbitrary multidimensional queries. Major challenges for the quality-based data retrieval are to 1.) find an appropriate formalization of data quality, 2.) design routing algorithms for queries, that are robust in the presence of high dynamics with respect to the participants of the system and the data on the participants and 3.) handle heterogeneous and high-dimensional data in the system. In order to retrieve data quality, we propose 1.) the measure of confidence for a query that is based on clusters of data. When a participant of the system finds, that its confidence for a query is high, it will assume to possess data of high quality for that query. 2.) Further, we design and implement routing strategies in order to route queries to nodes that can answer them with high confidence. Maintaining exact routing tables for each possible query would be infeasible, so nodes have to model the data that can be reached via neighbours in routing models. Such modelling of data is based on structural properties of the data such as how good the data can be clustered. 3.) In the high-dimensional space, we have to overcome the curse of dimensionality: the structure of data can become invisible in higher dimensions. We address this problem with a method for dimensionality reduction that reduces the dimensions with highest data variance. The evaluation of our approaches shows a high accuracy of query routing, even if our approaches do not make use of scalability bottlenecks like flooding of the query or flooding of routing information. Further, we show that the use of dimensionality reduction in routing has positive influence on the routing accuracy. We think that the methods in our approach can be useful instruments, whenever the task of retrieving data of high quality has to be outsourced to a distributed system.
  • Thumbnail Image
    ItemOpen Access
    Scalable graph partitioning for distributed graph processing
    (2019) Mayer, Christian; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)
    Distributed graph processing systems such as Pregel, PowerGraph, or GraphX have gained popularity due to their superior performance of data analytics on graph-structured data such as social networks, web document graphs, and biological networks. These systems scale out graph processing by dividing the graph into k partitions that are processed in parallel by k worker machines. The graph partitioning problem is NP-hard. Yet, finding good solutions for massive graphs is of paramount importance for distributed graph processing systems because it reduces communication overhead and latency of distributed graph processing. A multitude of graph partitioning heuristics emerged in recent years, fueled by the challenge of partitioning large graphs quickly. The goal of this thesis is to tailor graph partitioning to the specifics of distributed graph processing and show that this leads to reduced graph processing latency and communication overhead compared to state-of-the-art partitioning. In particular, we address the following four research questions. (I) Recent partitioning algorithms unrealistically assume a uniform and constant amount of data exchanged between graph vertices (i.e., uniform vertex traffic) and homogeneous network costs between workers hosting the graph partitions. The first research question is: how to consider dynamically changing and heterogeneous graph workload for graph partitioning? (II) Existing graph partitioning algorithms focus on minimal partitioning latency at the cost of reduced partitioning quality. However, we argue that the mere minimization of partitioning latency is not the optimal design choice in terms of minimizing total latency, i.e., the sum of partitioning and graph processing latency. The second research question is: how much latency should we invest into graph partitioning when considering that we often have to pay higher partitioning latency in order to achieve better partitioning quality (and therefore reduced graph processing latency)? (III) Popular user-centric graph applications such as route planning and personalized social network analysis have initiated a shift of paradigms in modern graph processing systems towards multi-query analysis, i.e., processing multiple graph queries in parallel on a shared data graph. These applications generate a dynamic number of localized queries around query hotspots such as popular urban areas. However, the employed methods for graph partitioning and synchronization management disregard query locality and dynamism which leads to high query latency. The third question is: how to dynamically adapt the graph partitioning when multiple localized graph queries run in parallel on a shared graph structure? (IV) Graphs are special cases of hypergraphs where each edge does not necessarily connect exactly two but an arbitrary number of vertices. Like graphs, they need to be partitioned as a pre-processing step for distributed hypergraph processing systems. Real-world hypergraphs have billions of vertices and a skewed degree distribution. However, no existing hypergraph partitioner tailors partitioning to the important subset of hypergraphs that are very large-scale and have a skewed degree distribution. Regarding this, the fourth research question is: how to partition these large-scale, skewed hypergraphs in an efficient way such that neighboring vertices tend to reside on the same partition? We answer these research questions by providing the following four contributions. (I) We developed the graph processing system GrapH that considers both, diverse vertex traffic and heterogeneous network costs. The main idea is to avoid frequent communication over expensive network links using an adaptive edge migration strategy. (II) We developed a static partitioning algorithm ADWISE that allows to control the trade-off between partitioning latency and graph processing latency. Besides providing evidence for efficiency and effectiveness of our approach, we also show that state-of-the-art partitioning approaches invest too little latency into graph partitioning. By investing more latency into partitioning using ADWISE, total latency of partitioning and processing reduces significantly. (III) We developed a distributed graph system QGraph for multi-query graph analysis that allows multiple localized graph queries to run in parallel on a shared graph structure. Our novel query-centric dynamic partitioning approach yields significant speedup as it repartitions the graph such that queries can be executed in a localized manner. This avoids expensive communication overhead while still providing good workload balancing. (IV) We developed a novel hypergraph partitioning algorithm, called HYPE, that partitions the hypergraph by using the idea of neighborhood expansion. HYPE grows k partitions separately - expanding one vertex at a time over the neighborhood relation of the hypergraph. We show that HYPE leads to fast and effective partitioning performance compared to state-of-the-art hypergraph partitioning tools and partitions billion-scale hypergraphs on a single thread. The algorithms and approaches presented in this thesis tailor graph partitioning towards the specifics of distributed graph processing with respect to (I) dynamic and heterogeneous traffic patterns and network costs, (II) the integrated latency of partitioning plus graph processing, and (III) the graph query workload for partitioning and synchronization. On top of that, (IV) we propose an efficient hypergraph partitioner which is specifically tailored to real-world hypergraphs with skewed degree distributions.
  • Thumbnail Image
    ItemOpen Access
    Design and implementation of a coordination service for distributed applications (In-memory Paxos)
    (2013) Mayer, Christian
    Coordination of different, independent processes is a very important aspect in the area of distributed systems. In order to coordinate each other, participants of a distributed system often have to agree on some common knowledge such as locking of a shared resource. The general problem how to reach agreement on some value is also known as consensus problem. In many practical systems, the consensus problem is outsourced to a distributed system consisting of multiple servers to increase its availability. Each server can be contacted by clients that intend to reach consensus about a specific value. Examples are Google's locking service Chubby or Yahoo's distributed file system Zookeeper. The standard Paxos algorithm solves this problem in an environment where nodes may recover after a crash and messages can have infinite delay. However, a system based on the classical Paxos algorithm makes use of expensive stable storage operations to guarantee that a crashed and recovered Paxos server is still able to participate in the protocol. Studies have shown that these disk costs are the bottleneck of the whole system. In this work a performance-oriented version of Paxos will be investigated that still solves the consensus problem, but trades availability of the consensus system against performance by not using stable storage operations. Without careful design this can be problematic, because a Paxos server that has lost its memory can be dangerous for the success of the protocol. This can be solved by not allowing a crashed and recovered Paxos server to participate in the protocol anymore. Instead, a recovered server rejoins the protocol with a new id, so that no active processes assume anything about the recovered process. In order to join the group of active processes, a majority of servers has to be active and agree on this. Our evaluations show, that a coordination system based on the in-memory Paxos approach has a very short response time of only one millisecond and high throughput up to 18000 write requests per second.