| 1. |
- Zeng, Jingna, 1985-
(författare)
-
Augmenting Transactional Memory with the Future Abstraction
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The advent of multicore systems spurred great interest in Transactional Memory (TM). TM is a parallel programming paradigm that coordinates concurrent threads by incorporating transactions into programming languages. TM shifts the burden of coordinating and synchronizing concurrent threads from programmers to the compiler, run-time environment, or even hardware.Unfortunately, though, current state-of-the-art TM implementations lack support for a powerful and intuitive abstraction that is widely used in modern parallel programming environments (e.g., C++, Java and JavaScript), namely "futures". The future abstraction is widely used due to its ability to express in a natural way opportunities for parallelism as well as logical dependencies among parallel tasks. Yet, perhaps surprisingly, the problem of how to support the future abstraction in a TM implementation has not been studied in the literature, although futures represent a natural and convenient means to enable intra-transaction parallelism in long-running transactions.This dissertation aims at filling precisely this relevant gap in the literature by investigating how to reconcile the TM and the future abstractions.This limitation is tackled by introducing a novel abstraction, called transactional futures,i.e., transactions that execute wrapped within futures and that are spawned and evaluated by other transactions or transactional futures.The semantics of transactional futures describes the allowed behaviors with regards to properties such as atomicity and isolation. Multiple semantics are defined, and the trade-offs between ease of use and efficiency are explored for each. Based on these semantics, this dissertation presents two novel TM implementations. The efficiency of the proposed transactional futures abstraction is evaluated in a real system using the TM implementations.Finally, this dissertation addresses the problem of self-tuning the parallelism degree in TM systems that support intra-transaction parallelism. This goal is achieved by presenting an online learning system that combines model-driven (Sequential Based Bayesian Optimization) and local searches techniques, as well as adaptive performance monitoring techniques.
|
|
| 2. |
- Al-Shishtawy, Ahmad, 1978-
(författare)
-
Self-Management for Large-Scale Distributed Systems
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Autonomic computing aims at making computing systems self-managing by using autonomic managers in order to reduce obstacles caused by management complexity. This thesis presents results of research on self-management for large-scale distributed systems. This research was motivated by the increasing complexity of computing systems and their management.In the first part, we present our platform, called Niche, for programming self-managing component-based distributed applications. In our work on Niche, we have faced and addressed the following four challenges in achieving self-management in a dynamic environment characterized by volatile resources and high churn: resource discovery, robust and efficient sensing and actuation, management bottleneck, and scale. We present results of our research on addressing the above challenges. Niche implements the autonomic computing architecture, proposed by IBM, in a fully decentralized way. Niche supports a network-transparent view of the system architecture simplifying the design of distributed self-management. Niche provides a concise and expressive API for self-management. The implementation of the platform relies on the scalability and robustness of structured overlay networks. We proceed by presenting a methodology for designing the management part of a distributed self-managing application. We define design steps that include partitioning of management functions and orchestration of multiple autonomic managers.In the second part, we discuss robustness of management and data consistency, which are necessary in a distributed system. Dealing with the effect of churn on management increases the complexity of the management logic and thus makes its development time consuming and error prone. We propose the abstraction of Robust Management Elements, which are able to heal themselves under continuous churn. Our approach is based on replicating a management element using finite state machine replication with a reconfigurable replica set. Our algorithm automates the reconfiguration (migration) of the replica set in order to tolerate continuous churn. For data consistency, we propose a majority-based distributed key-value store supporting multiple consistency levels that is based on a peer-to-peer network. The store enables the tradeoff between high availability and data consistency. Using majority allows avoiding potential drawbacks of a master-based consistency control, namely, a single-point of failure and a potential performance bottleneck.In the third part, we investigate self-management for Cloud-based storage systems with the focus on elasticity control using elements of control theory and machine learning. We have conducted research on a number of different designs of an elasticity controller, including a State-Space feedback controller and a controller that combines feedback and feedforward control. We describe our experience in designing an elasticity controller for a Cloud-based key-value store using state-space model that enables to trade-off performance for cost. We describe the steps in designing an elasticity controller. We continue by presenting the design and evaluation of ElastMan, an elasticity controller for Cloud-based elastic key-value stores that combines feedforward and feedback control.
|
|
| 3. |
- Niazi, Salman, 1982-
(författare)
-
Scaling Distributed Hierarchical File Systems Using NewSQL Databases
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- For many years, researchers have investigated the use of database technology to manage file system metadata, with the goal of providing extensible typed metadata and support for fast, rich metadata search. However, earlier attempts failed mainly due to the reduced performance introduced by adding database operations to the file system’s critical path. Recent improvements in the performance of distributed in-memory online transaction processing databases (NewSQL databases) led us to re-investigate the possibility of using a database to manage file system metadata, but this time for a distributed, hierarchical file system, the Hadoop Distributed File System (HDFS). The single-host metadata service of HDFS is a well-known bottleneck for both the size of the HDFS clusters and their throughput.In this thesis, we detail the algorithms, techniques, and optimizations used to develop HopsFS, an open-source, next-generation distribution of the HDFS that replaces the main scalability bottleneck in HDFS, single node in-memory metadata service, with a no-shared state distributed system built on a NewSQL database. In particular, we discuss how we exploit recent high-performance features from NewSQL databases, such as application-defined partitioning, partition pruned index scans, and distribution aware transactions, as well as more traditional techniques such as batching and write-ahead caches, to enable a revolution in distributed hierarchical file system performance.HDFS’ design is optimized for the storage of large files, that is, files ranging from megabytes to terabytes in size. However, in many production deployments of the HDFS, it has been observed that almost 20% of the files in the system are less than 4 KB in size and as much as 42% of all the file system operations are performed on files less than 16 KB in size. HopsFS introduces a tiered storage solution to store files of different sizes more efficiently. The tiers range from the highest tier where an in-memory NewSQL database stores very small files (<1 KB), to the next tier where small files (<64 KB) are stored in solid-state-drives (SSDs), also using a NewSQL database, to the largest tier, the existing Hadoop block storage layer for very large files. Our approach is based on extending HopsFS with an inode stuffing technique, where we embed the contents of small files with the metadata and use database transactions and database replication guarantees to ensure the availability, integrity, and consistency of the small files. HopsFS enables significantly larger cluster sizes, more than an order of magnitude higher throughput, and significantly lower client latencies for large clusters.Lastly, coordination is an integral part of the distributed file system operations protocols. We present a novel leader election protocol for partially synchronous systems that uses NewSQL databases as shared memory. Our work enables HopsFS, that uses a NewSQL database to save the operational overhead of managing an additional third-party service for leader election and deliver performance comparable to a leader election implementation using a state-of-the-art distributed coordination service, ZooKeeper.
|
|
| 4. |
- Roverso, Roberto, 1982-
(författare)
-
A System, Tools and Algorithms for Adaptive HTTP-live Streaming on Peer-to-peer Overlays
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In recent years, adaptive HTTP streaming protocols have become the de facto standard in the industry for the distribution of live and video-on-demand content over the Internet. In this thesis, we solve the problem of distributing adaptive HTTP live video streams to a large number of viewers using peer-to-peer (P2P) overlays. We do so by assuming that our solution must deliver a level of quality of user experience which is the same as a CDN while trying to minimize the load on the content provider’s infrastructure. Besides that, in the design of our solution, we take into consideration the realities of the HTTP streaming protocols, such as the pull-based approach and adaptive bitrate switching.The result of this work is a system which we call SmoothCache that provides CDN-quality adaptive HTTP live streaming utilizing P2P algorithms. Our experiments on a real network of thousands of consumer machines show that, besides meeting the the CDN-quality constraints, SmoothCache is able to consistently deliver up to 96% savings towards the source of the stream in a single bitrate scenario and 94% in a multi-bitrate scenario. In addition, we have conducted a number of pilot deployments in the setting of large enterprises with the same system, albeit tailored to private networks. Results with thousands of real viewers show that our platform provides an average offloading of bottlenecks in the private network of 91.5%.These achievements were made possible by advancements in multiple research areas that are also presented in this thesis. Each one of the contributions is novel with respect to the state of the art and can be applied outside of the context of our application. However, in our system they serve the purposes described below.We built a component-based event-driven framework to facilitate the development of our live streaming application. The framework allows for running the same code both in simulation and in real deployment. In order to obtain scalability of simulations and accuracy, we designed a novel flow-based bandwidth emulation model.In order to deploy our application on real networks, we have developed a network library which has the novel feature of providing on-the-fly prioritization of transfers. The library is layered over the UDP protocol and supports NAT Traversal techniques. As part of this thesis, we have also improved on the state of the art of NAT Traversal techniques resulting in higher probability of direct connectivity between peers on the Internet.Because of the presence of NATs on the Internet, discovery of new peers and collection of statistics on the overlay through peer sampling is problematic. Therefore, we created a peer sampling service which is NAT-aware and provides one order of magnitude fresher samples than existing peer sampling protocols.Finally, we designed SmoothCache as a peer-assisted live streaming system based on a distributed caching abstraction. In SmoothCache, peers retrieve video fragments from the P2P overlay as quickly as possible or fall back to the source of the stream to keep the timeliness of the delivery. In order to produce savings, the caching system strives to fill up the local cache of the peers ahead of playback by prefetching content. Fragments are efficiently distributed by a self-organizing overlay network that takes into account many factors such as upload bandwidth capacity, connectivity constraints, performance history and the currently being watched bitrate.
|
|
| 5. |
- Yalew, Sileshi Demesie
(författare)
-
Mobile Device Security with ARM TrustZone
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Mobile devices such as smartphones are becoming the majority of computing devices due to their evolving capabilities. Currently, service providers such as nancial and healthcare institutions oer services to their clients using smartphone applications (apps). Many of these apps run on Android, the most adopted mobile operating system (OS) today. Since smartphones are designed to be carried around all the time, many persons use them to store their private data. However, the popularity of Android and the open nature of its app marketplaces make it a prime target for malware. This situation puts data stored in smartphones in jeopardy, as it can be stealthily stolen or modied by malware that infects the device.With the increasing popularity of smartphones and the increasing amount of personal data stored on these devices, mobile device security has drawn signicant attention from both industry and academia. As a result, several security mechanisms and tools such as anti-malware software have been proposed for mobile OSs to improve the privacy of private data and to mitigate some of the security risks associated with mobile devices. However, these tools and mechanisms run in the device and assume that the mobile OS is trusted, i.e., that it is part of the trusted computing base (TCB). However, current malware often disables anti-malware software when it infects a device. For mobile phones this trend started more than a decade ago with malware such as the Metal Gear Trojan and Cabir.M, and continues to this day, e.g., with HijackRAT. In this work, we use the ARM TrustZone, a security extension for ARM processors that provides a hardware-assisted isolated environment, to implement security services that are protected from malware even if the mobile OS is compromised.In this thesis, we investigate two approaches to address some of the security risks associated with Android-based devices. In the rst approach, we present security services to detect intrusions in mobile devices. We design and implement services for posture assessment (which evaluates the level of trust we can have in the device), for dynamic analysis (which performs dynamic (runtime) analysis of apps using traces of Android application programming interface (API) function calls and kernel syscalls to detect apps for malware), and for authenticity detection (which provides assurance of the authenticity and integrity of apps running on mobile devices). In the second approach, we design and implement a backup and recovery system to protect mobile devices from attacks caused by ransomware attacks, system errors, etc. Finally, we develop a software framework to facilitate the development of security services for mobile devices by combining components of the above services. As proof-of-concept, we implemented a prototype for each service and made experimental evaluations using an i.MX53 development board with an ARM processor with TrustZone.
|
|
| 6. |
- Al-Shishtawy, Ahmad, 1978-
(författare)
-
Enabling and Achieving Self-Management for Large Scale Distributed Systems : Platform and Design Methodology for Self-Management
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Autonomic computing is a paradigm that aims at reducing administrative overhead by using autonomic managers to make applications self-managing. To better deal with large-scale dynamic environments; and to improve scalability, robustness, and performance; we advocate for distribution of management functions among several cooperative autonomic managers that coordinate their activities in order to achieve management objectives. Programming autonomic management in turn requires programming environment support and higher level abstractions to become feasible. In this thesis we present an introductory part and a number of papers that summaries our work in the area of autonomic computing. We focus on enabling and achieving self-management for large scale and/or dynamic distributed applications. We start by presenting our platform, called Niche, for programming self-managing component-based distributed applications. Niche supports a network-transparent view of system architecture simplifying designing application self-* code. Niche provides a concise and expressive API for self-* code. The implementation of the framework relies on scalability and robustness of structured overlay networks. We have also developed a distributed file storage service, called YASS, to illustrate and evaluate Niche. After introducing Niche we proceed by presenting a methodology and design space for designing the management part of a distributed self-managing application in a distributed manner. We define design steps, that includes partitioning of management functions and orchestration of multiple autonomic managers. We illustrate the proposed design methodology by applying it to the design and development of an improved version of our distributed storage service YASS as a case study. We continue by presenting a generic policy-based management framework which has been integrated into Niche. Policies are sets of rules that govern the system behaviors and reflect the business goals or system management objectives. The policy based management is introduced to simplify the management and reduce the overhead, by setting up policies to govern system behaviors. A prototype of the framework is presented and two generic policy languages (policy engines and corresponding APIs), namely SPL and XACML, are evaluated using our self-managing file storage application YASS as a case study. Finally, we present a generic approach to achieve robust services that is based on finite state machine replication with dynamic reconfiguration of replica sets. We contribute a decentralized algorithm that maintains the set of resource hosting service replicas in the presence of churn. We use this approach to implement robust management elements as robust services that can operate despite of churn.
|
|
| 7. |
- Arad, Cosmin Ionel, 1981-
(författare)
-
Programming Model and Protocols for Reconfigurable Distributed Systems
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Distributed systems are everywhere. From large datacenters to mobile devices, an ever richer assortment of applications and services relies on distributed systems, infrastructure, and protocols. Despite their ubiquity, testing and debugging distributed systems remains notoriously hard. Moreover, aside from inherent design challenges posed by partial failure, concurrency, or asynchrony, there remain significant challenges in the implementation of distributed systems. These programming challenges stem from the increasing complexity of the concurrent activities and reactive behaviors in a distributed system on the one hand, and the need to effectively leverage the parallelism offered by modern multi-core hardware, on the other hand.This thesis contributes Kompics, a programming model designed to alleviate some of these challenges. Kompics is a component model and programming framework for building distributed systems by composing message-passing concurrent components. Systems built with Kompics leverage multi-core machines out of the box, and they can be dynamically reconfigured to support hot software upgrades. A simulation framework enables deterministic execution replay for debugging, testing, and reproducible behavior evaluation for largescale Kompics distributed systems. The same system code is used for both simulation and production deployment, greatly simplifying the system development, testing, and debugging cycle.We highlight the architectural patterns and abstractions facilitated by Kompics through a case study of a non-trivial distributed key-value storage system. CATS is a scalable, fault-tolerant, elastic, and self-managing key-value store which trades off service availability for guarantees of atomic data consistency and tolerance to network partitions. We present the composition architecture for the numerous protocols employed by the CATS system, as well as our methodology for testing the correctness of key CATS algorithms using the Kompics simulation framework.Results from a comprehensive performance evaluation attest that CATS achieves its claimed properties and delivers a level of performance competitive with similar systems which provide only weaker consistency guarantees. More importantly, this testifies that Kompics admits efficient system implementations. Its use as a teaching framework as well as its use for rapid prototyping, development, and evaluation of a myriad of scalable distributed systems, both within and outside our research group, confirm the practicality of Kompics.
|
|
| 8. |
- Ardelius, John, 1978-
(författare)
-
On the Performance Analysis of Large Scale, Dynamic, Distributed and Parallel Systems.
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Evaluating the performance of large distributed applications is an important and non-trivial task. With the onset of Internet wide applications there is an increasing need to quantify reliability, dependability and performance of these systems, both as a guide in system design as well as a means to understand the fundamental properties of large-scale distributed systems. Previous research has mainly focused on either formalised models where system properties can be deduced and verified using rigorous mathematics or on measurements and experiments on deployed applications. Our aim in this thesis is to study models on an abstraction level lying between the two ends of this spectrum. We adopt a model of distributed systems inspired by methods used in the study of large scale system of particles in physics and model the application nodes as a set of interacting particles each with an internal state whose actions are specified by the application program. We apply our modeling and performance evaluation methodology to four different distributed and parallel systems. The first system is the distributed hash table (DHT) Chord running in a dynamic environment. We study the system under two scenarios. First we study how performance (in terms of lookup latency) is affectedon a network with finite communication latency. We show that an average delay in conjunction with other parameters describing changes in the network (such as timescales for network repair and join and leave processes)induces fundamentally different system performance. We also verify our analytical predictions via simulations.In the second scenario we introduce network address translators (NATs) to the network model. This makes the overlay topology non-transitive and we explore the implications of this fact to various performance metrics such as lookup latency, consistency and load balance. The latter analysis is mainly simulation based.Even though these two studies focus on a specific DHT, many of our results can easily be translated to other similar ring-based DHTs with long-range links, and the same methodology can be applied evento DHT's based on other geometries.The second type of system studied is an unstructured gossip protocol running a distributed version of the famous Belman-Ford algorithm. The algorithm, called GAP, generates a spanning tree over the participating nodes and the question we set out to study is how reliable this structure is(in terms of generating accurate aggregate values at the root) in the presence of node churn. All our analytical results are also verified using simulations.The third system studied is a content distribution network (CDN) of interconnected caches in an aggregation access network. In this model, content which sits at the leaves of the cache hierarchy tree, is requested by end users. Requests can then either be served by the first cache level or sent further up the tree. We study the performance of the whole system under two cache eviction policies namely LRU and LFU. We compare our analytical results with traces from related caching systems.The last system is a work stealing heuristic for task distribution in the TileraPro64 chip. This system has access to a shared memory and is therefore classified as a parallel system. We create a model for the dynamic generation of tasks as well as how they are executed and distributed among the participating nodes. We study how the heuristic scales when the number of nodes exceeds the number of processors on the chip as well as how different work stealing policies compare with each other. The work on this model is mainly simulation-based.
|
|
| 9. |
- Gholami, Ali, 1978-
(författare)
-
Security and Privacy of Sensitive Data in Cloud Computing
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Cloud computing offers the prospect of on-demand, elastic computing, provided as a utility service, and it is revolutionizing many domains of computing. Compared with earlier methods of processing data, cloud computing environments provide significant benefits, such as the availability of automated tools to assemble, connect, configure and reconfigure virtualized resources on demand. These make it much easier to meet organizational goals as organizations can easily deploy cloud services. However, the shift in paradigm that accompanies the adoption of cloud computing is increasingly giving rise to security and privacy considerations relating to facets of cloud computing such as multi-tenancy, trust, loss of control and accountability. Consequently, cloud platforms that handle sensitive information are required to deploy technical measures and organizational safeguards to avoid data protection breakdowns that might result in enormous and costly damages. Sensitive information in the context of cloud computing encompasses data from a wide range of different areas and domains. Data concerning health is a typical example of the type of sensitive information handled in cloud computing environments, and it is obvious that most individuals will want information related to their health to be secure. Hence, with the growth of cloud computing in recent times, privacy and data protection requirements have been evolving to protect individuals against surveillance and data disclosure. Some examples of such protective legislation are the EU Data Protection Directive (DPD) and the US Health Insurance Portability and Accountability Act (HIPAA), both of which demand privacy preservation for handling personally identifiable information. There have been great efforts to employ a wide range of mechanisms to enhance the privacy of data and to make cloud platforms more secure. Techniques that have been used include: encryption, trusted platform module, secure multi-party computing, homomorphic encryption, anonymization, container and sandboxing technologies. However, it is still an open problem about how to correctly build usable privacy-preserving cloud systems to handle sensitive data securely due to two research challenges. First, existing privacy and data protection legislation demand strong security, transparency and audibility of data usage. Second, lack of familiarity with a broad range of emerging or existing security solutions to build efficient cloud systems. This dissertation focuses on the design and development of several systems and methodologies for handling sensitive data appropriately in cloud computing environments. The key idea behind the proposed solutions is enforcing the privacy requirements mandated by existing legislation that aims to protect the privacy of individuals in cloud-computing platforms. We begin with an overview of the main concepts from cloud computing, followed by identifying the problems that need to be solved for secure data management in cloud environments. It then continues with a description of background material in addition to reviewing existing security and privacy solutions that are being used in the area of cloud computing. Our first main contribution is a new method for modeling threats to privacy in cloud environments which can be used to identify privacy requirements in accordance with data protection legislation. This method is then used to propose a framework that meets the privacy requirements for handling data in the area of genomics. That is, health data concerning the genome (DNA) of individuals. Our second contribution is a system for preserving privacy when publishing sample availability data. This system is noteworthy because it is capable of cross-linking over multiple datasets. The thesis continues by proposing a system called ScaBIA for privacy-preserving brain image analysis in the cloud. The final section of the dissertation describes a new approach for quantifying and minimizing the risk of operating system kernel exploitation, in addition to the development of a system call interposition reference monitor for Lind - a dual sandbox.
|
|
| 10. |
- Jimenez, Raul, 1982-
(författare)
-
Distributed Peer Discovery in Large-Scale P2P Streaming Systems : Addressing Practical Problems of P2P Deployments on the Open Internet
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Peer-to-peer (P2P) techniques allow users with limited resources to distribute content to a potentially large audience by turning passive clients into peers. Peers can self-organize to distribute content to each other, increasing the scalability of the system and decreasing the publisher’s costs, compared to a publisher distributing the data himself using a content delivery network (CDN) or his own servers.Peer discovery is the mechanism that peers use to find each other. Peer discovery is a critical component of any P2P-based system, because P2P networks are dynamic by nature. That is, peers constantly join and leave the network and each individual peer is assumed to be unreliable. This thesis addresses practical issues in distributed peer discovery mech- anisms in the context of three different large-scale P2P streaming systems: a (1) BitTorrent-based streaming system, (2) Spotify, and (3) our own mobile P2P streaming system based on the upcoming Peer-to-peer Streaming Protocol (PPSP) Internet standard.We dramatically improve peer discovery performance in BitTorrent’s Mainline DHT, the largest distributed hash table (DHT) overlay on the open Internet. Our implementation’s median lookup latency is an order of magnitude lower than the best performing measurement reported in the literature and does not exhibit a long tail of high-latency lookups, which is critical for P2P streaming applications.We have achieved these results by studying how connectivity artifacts on the underlying network —probably caused by network address translation (NAT) gateways— affect the DHT overlay. Our measurements of more than three million nodes reveal that connectivity artifacts are widespread and can severely degrade DHT performance.This thesis also addresses the practical issues of integrating mobile devices into P2P streaming systems. In particular, we enable P2P on Spotify’s Android app, study how distributed peer discovery affects energy consumption, and implement and evaluate backwards-compatible modifications which dramatically reduce energy consumption on 3G.Then, we build the first complete system that not only is capable of streaming content to mobile devices but also allows them to publish content directly into the P2P system, even when they are behind a NAT gateway, with minimal impact on their battery and data usage.While our preferred approach is implementing backwards-compatible modifications, we also propose and analyze backwards-incompatible ones. The former allow us to evaluate them in the existing large-scale systems and allow developers to deploy our modifications into the actual system. The latter free us to propose deeper changes. In particular, we propose (1) a DHT-based peer discovery mechanism that improves scalability and introduces localityawareness, and (2) modifications on Spotify’s gossip-like peer discovery to better accommodate mobile devices
|
|
| 11. |
- Jimenez, Raúl
(författare)
-
Kademlia on the Open Internet : How to Achieve Sub-Second Lookups in a Multimillion-Node DHT Overlay
- 2011
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Distributed hash tables (DHTs) have gained much attention from the research community in the last years. Formal analysis and evaluations on simulators and small-scale deployments have shown good scalability and performance. In stark contrast, performance measurements in large-scale DHT overlays on the Internet have yielded disappointing results, with lookup latencies measured in seconds. Others have attempted to improve lookup performance with very limited success, their lowest median lookup latency at over one second and a long tail of high-latency lookups. In this thesis, the goal is to to enable large-scale DHT-based latency-sensitive applications on the Internet. In particular, we improve lookup latency in Mainline DHT, the largest DHT overlay on the open Internet, to identify and address practical issues on an existing system. Our approach is implementing and measuring backward-compatible modifications to facilitate their incremental adoption into Mainline DHT (and possibly other Kademlia-based overlays). Thus, enabling our research to have impact on a real-world system. Our results close the performance gap between small- and large-scale DHT overlays. With a median lookup latency below 200 ms and a 99\superscript{th} percentile of just above 500 ms, our median lookup latency is one order of magnitude lower than the best performing measurement reported in the literature. Moreover, our results do not show a long tail of high-latency lookups, unlike previous reports. We have achieved these results by studying how connectivity artifacts on the underlying network ---probably caused by firewalls and NAT devices on the Internet--- affect the DHT overlay. Our measurements of the connectivity of more than 3 million nodes reveal that connectivity artifacts are widespread and can severely degrade lookup performance. Scalability and locality-awareness have also been explored in this thesis, where different mechanisms have been proposed. Some of the mechanisms are planned to be integrated into Mainline DHT in future work.
|
|
| 12. |
- Lagerkvist, Mikael Zayenz, 1981-
(författare)
-
Techniques for Efficient Constraint Propagation
- 2008
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis explores three new techniques for increasing the efficiency of constraint propagation: support for incremental propagation, improved representation of constraints, and abstractions to simplify propagation. Support for incremental propagation is added to a propagator centered propagation system by adding a new intermediate layer of abstraction, advisors, that capture the essential aspects of a variable centered system. Advisors are used to give propagators a detailed view of the dynamic changes between propagator runs. Advisors enable the implementation of optimal algorithms for important constraints such as extensional constraints and Boolean linear in-equations, which is not possible in a propagator centered system lacking advisors. Using Multivalued Decision Diagrams (MDD) as the representation for extensional constraints is shown to be useful for several reasons. Classical operations on MDDs can be used to optimize the representation, and thus speeding up the propagation. In particular, the reduction operation is stronger than the use of DFA minimization for the regular constraint. The use of MDDs is contrasted and compared to a recent proposal where tables are compressed. Abstractions for constraint programs try to capture small and essential features of a model. These features may be much cheaper to propagate than the unabstracted program. The potential for abstraction is explored using several examples. These three techniques work on different levels. Support for incremental propagation is essential for the efficient implementation of some constraints, so that the algorithms have the right complexity. On a higher level, the question of representation looks at what a propagator should use for propagation. Finally, the question of abstraction can potentially look at several propagators, to find cases where abstractions might be fruitful. An essential feature of this thesis is a novel model for general placement constraints that uses regular expressions. The model is very versatile and can be used for several different kinds of placement problems. The model applied to the classic pentominoes puzzle will be used through-out the thesis as an example and for experiments.
|
|
| 13. |
- Payberah, Amir H.
(författare)
-
Distributed Optimization of P2P Media Delivery Overlays
- 2011
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Media streaming over the Internet is becoming increasingly popular. Currently, most media is delivered using global content-delivery networks, providing a scalable and robust client-server model. However, content delivery infrastructures are expensive. One approach to reduce the cost of media delivery is to use peer-to-peer (P2P) overlay networks, where nodes share responsibility for delivering the media to one another. The main challenges in P2P media streaming using overlay networks include: (i) nodes should receive the stream with respect to certain timing constraints, (ii) the overlay should adapt to the changes in the network, e.g., varying bandwidth capacity and join/failure of nodes, (iii) nodes should be intentivized to contribute and share their resources, and (iv) nodes should be able to establish connectivity to the other nodes behind NATs. In this work, we meet these requirements by presenting P2P solutions for live media streaming, as well as proposing a distributed NAT traversal solution. First of all, we introduce a distributed market model to construct an approximately minimal height multiple-tree streaming overlay for content delivery, in gradienTv. In this system, we assume all the nodes are cooperative and execute the protocol. However, in reality, there may exist some opportunistic nodes, free-riders, that take advantage of the system, without contributing to content distribution. To overcome this problem, we extend our market model in Sepidar to be effective in deterring free-riders. However, gradienTv and Sepidar are tree-based solutions, which are fragile in high churn and failure scenarios. We present a solution to this problem in GLive that provides a more robust overlay by replacing the tree structure with a mesh. We show in simulation, that the mesh-based overlay outperforms the multiple-tree overlay. Moreover, we compare the performance of all our systems with the state-of-the-art NewCoolstreaming, and observe that they provide better playback continuity and lower playback latency than that of NewCoolstreaming under a variety of experimental scenarios. Although our distributed market model can be run against a random sample of nodes, we improve its convergence time by executing it against a sample of nodes taken from the Gradient overlay. The Gradient overlay organizes nodes in a topology using a local utility value at each node, such that nodes are ordered in descending utility values away from a core of the highest utility nodes. The evaluations show that the streaming overlays converge faster when our market model works on top of the Gradient overlay. We use a gossip-based peer sampling service in our streaming systems to provide each node with a small list of live nodes. However, in the Internet, where a high percentage of nodes are behind NATs, existing gossiping protocols break down. To solve this problem, we present Gozar , a NAT-friendly gossip-based peer sampling service that: (i) provides uniform random samples in the presence of NATs, and (ii) enables direct connectivity to sampled nodes using a fully distributed NAT traversal service. We compare Gozar with the state-of-the-art NAT-friendly gossip-based peer sampling service, Nylon, and show that only Gozar supports one-hop NAT traversal, and its overhead is roughly half of Nylon’s.
|
|
| 14. |
- Rahimian, Fatemeh
(författare)
-
Gossip-based Algorithms for Information Dissemination and Graph Clustering
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Decentralized algorithms are becoming ever more prevalent in almost all real-world applications that are either data intensive, computation intensive or both. This thesis presents a few decentralized solutions for large-scale (i) data dissemination, (ii) graph partitioning, and (iii) data disambiguation. All these solutions are based on gossip, a light weight peer-to-peer data exchange protocol, and thus, appropriate for execution in a distributed environment.For efficient data dissemination, we make use of the publish/subscribe communication model and provide two distributed solutions, one for topicbased and one for content-based subscriptions, named Vitis and Vinifera respectively. These systems propagate large quantities of data to interested users with a relatively low overhead. Without any central coordinator and only with the use of gossip, we build a novel topology that enables efficient routing in an unstructured overlay. We construct a hybrid system by injecting structure into an otherwise unstructured network. The resulting structure resembles a navigable small-world network that spans along clusters of nodes that have similar subscriptions. The properties of such an overlay make it an ideal platform for efficient data dissemination in large-scale systems. Our solutions significantly outperforms their counterparts on various subscription and churn scenarios, from both synthetic models and real-world traces.We then investigate how gossiping protocols can be used, not for overlay construction, but for operating on fixed overlay topologies, which resemble graphs. In particular we study the NP-Complete problem of graph partitioning and present a distributed partitioning solution for very large graphs. This solution, called Ja-be-Ja, is based on local search and does not require access to the entire graph simultaneously. It is, therefore, appropriate for graphs that can not even fit into the memory of a single computer. Once again gossip-based algorithms prove efficient as they enable implementing light-weight peer sampling services, which supply graph nodes with partial knowledge about other nodes in the graph. The performance of our partitioning algorithm is comparable to centralized graph partitioning algorithms, and yet it is scalable and can be executed on several machines in parallel or even in a completely distributed peer-to-peer overlay. It can be used for both edge-cut and vertex-cut partitioning of graphs and can produce partition sizes of any given distribution.We further extend the use of gossiping protocols to find natural clusters in a graph instead of producing a given number of partitions. This problem, known as graph community detection, has extensive application in various fields and communities. We take the use of our community detection algorithm to the realm of linguistics and address a well-known problem of data disambiguation. In particular, we provide a parallel community detection algorithm for cross-document coreference problem. We operate on graphs that we construct by representing documents’ keywords as nodes and the co-location of those keywords in a document as edges. We then exploit the particular nature of such graphs, which is coreferent words are topologically clustered, and thus, can be efficiently discovered by our community detection algorithm.
|
|
| 15. |
- Roverso, Roberto, 1982-
(författare)
-
Design and Implementation of Centrally-Coordinated Peer-to-Peer Live-streaming
- 2011
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis, we explore the use of a centrally-coordinated peer-to-peer overlay as a possible solution to the live streaming problem. Our contribution lies in showing that such approach is indeed feasible given that a number of key challenges are met. The motivation behind exploring an alternative design is that, although a number of approaches have been investigated in the past, e.g. mesh-pull and tree-push, hybrids and best-of-both-worlds mesh-push, no consensus has been reached on the best solution for the problem of peer-to-peer live streaming, despite current deployments and reported successes. In the proposed system, we model sender/receiver peer assignments as an optimization problem. Optimized peer selection based on multiple utility factors, such as bandwidth availability, delays and connectivity compatibility, make it possible to achieve large source bandwidth savings and provide high quality of user experience. Clear benefits of our approach are observed when Network Address Translation constraints are present on the network. We have addressed key scalability issues of our platform by parallelizing the heuristic which is the core of our optimization engine and by implementing the resulting algorithm on commodity Graphic Processing Units (GPUs). The outcome is a Linear Sum Assignment Problem (LSAP) solver for time-constrained systems which produces near-optimal results and can be used for any instance of LSAP, i.e. not only in our system. As part of this work, we also present our experience in working with Network Address Translators (NATs) traversal in peer-to-peer systems. Our contribution in this context is threefold. First, we provide a semi-formal model of state of the art NAT behaviors. Second, we use our model to show which NAT combinations can be theoretically traversed and which not. Last, for each of the combinations, we state which traversal technique should be used. Our findings are confirmed by experimental results on a real network. Finally, we address the problem of reproducibility in testing, debugging and evaluation of our peer-to-peer application. We achieve this by providing a software framework which can be transparently integrated with any already-existing software and which is able to handle concurrency, system time and network events in a reproducible manner.
|
|
| 16. |
- Tallat Mahmood, Shafaat, 1982-
(författare)
-
Partition Tolerance and Data Consistency in Structured Overlay Networks
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Structured overlay networks form a major class of peer-to-peer systems, which are used to build scalable, fault-tolerant and self-managing distributed applications. This thesis presents algorithms for structured overlay networks, on the routing and data level, in the presence of network and node dynamism.On the routing level, we provide algorithms for maintaining the structure of the overlay, and handling extreme churn scenariossuch as bootstrapping, and network partitions and mergers. Since any long lived Internet-scale distributed system is destined to face network partitions, we believe structured overlays should intrinsically be able to handle partitions and mergers. In this thesis, we discuss mechanisms for detecting a network partition and merger, and provide algorithms for merging multiple ring-based overlays. Next, we present a decentralized algorithm for estimating the number of nodes in a peer-to-peer system. Lastly, we discussthe causes of routing anomalies (lookup inconsistencies), their effect on data consistency, and mechanisms on the routing level to reduce data inconsistency.On the data level, we provide algorithms for achieving strong consistency and partition tolerance in structured overlays. Based on our solutions on the routing and data level, we build a distributed key-value store for dynamic partially synchronous networks, which is linearizable, self-managing, elastic, and exhibits unlimited linear scalability. Finally, we present a replication scheme for structured overlays that is less sensitive to churn than existing schemes, and allows different replication degrees for different key ranges that enables using higher number of replicas for hotspots and critical data.
|
|
| 17. |
- Carbone, Paris, 1986-
(författare)
-
Scalable and Reliable Data Stream Processing
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Data-stream management systems have for long been considered as a promising architecture for fast data management. The stream processing paradigm poses an attractive means of declaring persistent application logic coupled with state over evolving data. However, despite contributions in programming semantics addressing certain aspects of data streaming, existing approaches have been lacking a clear, universal specification for the underlying system execution. We investigate the case of data stream processing as a general-purpose scalable computing architecture that can support continuous and iterative state-driven workloads. Furthermore, we examine how this architecture can enable the composition of reliable, reconfigurable services and complex applications that go even beyond the needs of scalable data analytics, a major trend in the past decade.In this dissertation, we specify a set of core components and mechanisms to compose reliable data stream processing systems while adopting three crucial design principles: blocking-coordination avoidance, programming-model transparency, and compositionality. Furthermore, we identify the core open challenges among the academic and industrial state of the art and provide a complete solution using these design principles as a guide. Our contributions address the following problems: I) Reliable Execution and Stream State Management, II) Computation Sharing and Semantics for Stream Windows, and III) Iterative Data Streaming. Several parts of this work have been integrated into Apache Flink, a widely-used, open-source scalable computing framework, and supported the deployment of hundreds of long-running large-scale production pipelines worldwide.
|
|
| 18. |
- Ghodsi, Ali, 1978-
(författare)
-
Distributed k-ary System: Algorithms for Distributed Hash Tables
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described.
|
|
| 19. |
- Kroll, Lars, 1989-, et al.
(författare)
-
Arc : An IR for batch and stream programming
- 2019
-
Ingår i: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450367189 ; , s. 53-58
-
Konferensbidrag (refereegranskat)abstract
- In big data analytics, there is currently a large number of data programming models and their respective frontends such as relational tables, graphs, tensors, and streams. This has lead to a plethora of runtimes that typically focus on the efficient execution of just a single frontend. This fragmentation manifests itself today by highly complex pipelines that bundle multiple runtimes to support the necessary models. Hence, joint optimization and execution of such pipelines across these frontend-bound runtimes is infeasible. We propose Arc as the first unified Intermediate Representation (IR) for data analytics that incorporates stream semantics based on a modern specification of streams, windows and stream aggregation, to combine batch and stream computation models. Arc extends Weld, an IR for batch computation and adds support for partitioned, out-of-order stream and window operators which are the most fundamental building blocks in contemporary data streaming.
|
|
| 20. |
|
|
| 21. |
- Payberah, Amir H., 1978-
(författare)
-
Live Streaming in P2P and Hybrid P2P-Cloud Environments for the Open Internet
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Peer-to-Peer (P2P) live media streaming is an emerging technology that reduces the barrier to stream live events over the Internet. However, providing a high quality media stream using P2P overlay networks is challenging and gives raise to a number of issues: (i) how to guarantee quality of the service (QoS) in the presence of dynamism, (ii) how to incentivize nodes to participate in media distribution, (iii) how to avoid bottlenecks in the overlay, and (iv) how to deal with nodes that reside behind Network Address Translators gateways (NATs).In this thesis, we answer the above research questions in form of new algorithms and systems. First of all, we address problems (i) and (ii) by presenting our P2P live media streaming solutions: Sepidar, which is a multiple-tree overlay, and GLive, which is a mesh overlay. In both models, nodes with higher upload bandwidth are positioned closer to the media source. This structure reduces the playback latency and increases the playback continuity at nodes, and also incentivizes the nodes to provide more upload bandwidth.We use a reputation model to improve participating nodes in media distribution in Sepidar and GLive. In both systems, nodes audit the behaviour of their directly connected nodes by getting feedback from other nodes. Nodes who upload more of the stream get a relatively higher reputation, and proportionally higher quality streams.To construct our streaming overlay, we present a distributed market model inspired by Bertsekas auction algorithm, although our model does not rely on a central server with global knowledge. In our model, each node has only partial information about the system. Nodes acquire knowledge of the system by sampling nodes using the Gradient overlay, where it facilitates the discovery of nodes with similar upload bandwidth.We address the bottlenecks problem, problem (iii), by presenting CLive that satisfies real-time constraints on delay between the generation of the stream and its actual delivery to users. We resolve this problem by borrowing some resources (helpers) from the cloud, upon need. In our approach, helpers are added on demand to the overlay, to increase the amount of total available bandwidth, thus increasing the probability of receiving the video on time. As the use of cloud resources costs money, we model the problem as the minimization of the economical cost, provided that a set of constraints on QoS is satisfied.Finally, we solve the NAT problem, problem (iv), by presenting two NAT-aware peer sampling services (PSS): Gozar and Croupier. Traditional gossip-based PSS breaks down, where a high percentage of nodes are behind NATs. We overcome this problem in Gozar using one-hop relaying to communicate with the nodes behind NATs. Croupier similarly implements a gossip-based PSS, but without the use of relaying.
|
|
| 22. |
- Rahimian, Fatemeh
(författare)
-
Enabling Internet-Scale Publish/Subscribe In Overlay Networks
- 2011
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- As the amount of data in todays Internet is growing larger, users are exposedto too much information, which becomes increasingly more difficult tocomprehend. Publish/subscribe systems leverage this problem by providingloosely-coupled communications between producers and consumers of data ina network. Data consumers, i.e., subscribers, are provided with a subscriptionmechanism, to express their interests in a subset of data, in order to be notifiedonly when some data that matches their subscription is generated by theproducers, i.e., publishers. Most publish/subscribe systems today, are basedon the client/server architectural model. However, to provide the publish/-subscribe service in large scale, companies either have to invest huge amountof money for over-provisioning the resources, or are prone to frequent servicefailures. Peer-to-peer overlay networks are attractive alternative solutions forbuilding Internet-scale publish/subscribe systems. However, scalability comeswith a cost: a published message often needs to traverse a large number ofuninterested (unsubscribed) nodes before reaching all its subscribers. Werefer to this undesirable traffic, as relay overhead. Without careful considerations,the relay overhead might sharply increase resource consumption for therelay nodes (in terms of bandwidth transmission cost, CPU, etc) and couldultimately lead to rapid deterioration of the system’s performance once therelay nodes start dropping the messages or choose to permanently abandonthe system. To mitigate this problem, some solutions use unbounded numberof connections per node, while some other limit the expressiveness of thesubscription scheme. In this thesis work, we introduce two systems called Vitis and Vinifera, fortopic-based and content-based publish/subscribe models, respectively. Boththese systems are gossip-based and significantly decrease the relay overhead.We utilize novel techniques to cluster together nodes that exhibit similarsubscriptions. In the topic-based model, distinct clusters for each topic areconstructed, while clusters in the content-based model are fuzzy and do nothave explicit boundaries. We augment these clustered overlays by links thatfacilitate routing in the network. We construct a hybrid system by injectingstructure into an otherwise unstructured network. The resulting structuresresemble navigable small-world networks, which spans along clusters of nodesthat have similar subscriptions. The properties of such overlays make theman ideal platform for efficient data dissemination in large-scale systems. Thesystems requires only a bounded node degree and as we show, through simulations,they scale well with the number of nodes and subscriptions and remainefficient under highly complex subscription patterns, high publication rates,and even in the presence of failures in the network. We also compare bothsystems against some state-of-the-art publish/subscribe systems. Our measurementsshow that both Vitis and Vinifera significantly outperform theircounterparts on various subscription and churn scenarios, under both syntheticworkloads and real-world traces.
|
|
| 23. |
- Shafaat, Tallat Mahmood, 1982-
(författare)
-
Dealing with Network Partitions and Mergers in Structured Overlay Networks
- 2009
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.
|
|
| 24. |
- Vasiloudis, Theodore
(författare)
-
Scalable Machine Learning through Approximation and Distributed Computing
- 2019
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Machine learning algorithms are now being deployed in practically all areas of our lives. Part of this success can be attributed to the ability to learn complex representations from massive datasets. However, computational speed increases have not kept up with the increase in the sizes of data we want to learn from, leading naturally to algorithms that need to be resource-efficient and parallel. As the proliferation of machine learning continues, the ability for algorithms to adapt to a changing environment and deal with uncertainty becomes increasingly important.In this thesis we develop scalable machine learning algorithms, with a focus on efficient, online, and distributed computation. We make use of approximations to dramatically reduce the computational cost of exact algorithms, and develop online learning algorithms to deal with a constantly changing environment under a tight computational budget. We design parallel and distributed algorithms to ensure that our methods can scale to massive datasets.We first propose a scalable algorithm for graph vertex similarity calculation and concept discovery. We demonstrate its applicability to multiple domains, including text, music, and images, and demonstrate its scalability by training on one of the largest text corpora available. Then, motivated by a real-world use case of predicting the session length in media streaming, we propose improvements to several aspects of learning with decision trees. We propose two algorithms to estimate the uncertainty in the predictions of online random forests. We show that our approach can achieve better accuracy than the state of the art while being an order of magnitude faster. We then propose a parallel and distributed online tree boosting algorithm that maintains the correctness guarantees of serial algorithms while providing an order of magnitude speedup on average. Finally, we propose an algorithm that allows for gradient boosted trees training to be distributed across both the data point and feature dimensions. We show that we can achieve communication savings of several orders of magnitude for sparse datasets, compared to existing approaches that can only distribute the computation across the data point dimension and use dense communication.
|
|
