Data provenance, or data lineage, describes the life cycle of data. In scientific workflows on HPC systems, scientists often seek diverse provenance (e.g., origins of data products, usage patterns of datasets). Unfort...
详细信息
ISBN:
(纸本)9781450391993
Data provenance, or data lineage, describes the life cycle of data. In scientific workflows on HPC systems, scientists often seek diverse provenance (e.g., origins of data products, usage patterns of datasets). Unfortunately, existing provenance solutions cannot address the challenges due to their incompatible provenance models and/or system implementations. In this paper, we analyze three representative scientific workflows in collaboration with the domain scientists to identify concrete provenance needs. Based on the first-hand analysis, we propose a provenance framework called PROV-IO, which includes an I/O-centric provenance model for describing scientific data and the associated I/O operations and environments precisely. Moreover, we build a prototype of PROV-IO to enable end-to-end provenance support on real HPC systems with little manual effort. The PROV-IO framework provides flexibility in selecting various classes of provenance. Our experiments with realistic workflows show that PROV-IO can address the provenance needs of the domain scientists effectively with reasonable performance (e.g., less than 3.5% tracking overhead for most experiments). Moreover, PROV-IO outperforms a state-of-the-art system (i.e., ProvLake) in our experiments.
Interplanetary distributed systems, such as the Interplanetary Internet, and the Global Positioning System (GPS) are subject to the effects of Einstein's theory of relativity. In this paper, we study relativistic ...
详细信息
ISBN:
(纸本)9798400718854
Interplanetary distributed systems, such as the Interplanetary Internet, and the Global Positioning System (GPS) are subject to the effects of Einstein's theory of relativity. In this paper, we study relativistic distributed systems, which are subject to the relativity of simultaneity. We formulate a unified computational model for relativistic and classical distributed systems and study the relationship between properties of distributed algorithms deployed on the two types of systems. Classical executions are totally ordered in time, whereas the steps of a relativistic execution are only partially ordered by the relation of relativistic causality. We relate these two physics-dependent execution types through a third—purely mathematical—notion of a computational execution, which partially orders steps by the relation of computational causality. We relate relativistic, classical, and computational executions of distributed algorithms through a central theorem, which states that the following are equivalent for any distributed algorithm A: (1) A satisfies a property P classically; (2) every relativistic execution of A satisfies P in the reference frame of every observer; and (3) every total ordering of every computational execution of A satisfies P. As a direct consequence, we prove the equivalence of the standard, relativistic, and computational formulations of linearizability. Our results show that a host of algorithms originally designed for classical distributed systems will behave consistently when deployed in relativistic, interplanetary distributed systems.
We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance t...
详细信息
ISBN:
(纸本)9798400718854
We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. The better the prediction, the fewer rounds the algorithm should perform. We present a framework for evaluating distributed graph algorithms with predictions and some methods for transforming existing algorithms without predictions to effectively use predictions. Our approach is illustrated using the Maximal Independent Set problem.
Resolving an open question from 2006 [14], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple O(log∗ n)-round distr...
详细信息
Current-day data centers and high-volume cloud services employ a broad set of heterogeneous servers. In such settings, client requests typically arrive at multiple entry points, and dispatching them to servers is an u...
详细信息
ISBN:
(纸本)9781450385480
Current-day data centers and high-volume cloud services employ a broad set of heterogeneous servers. In such settings, client requests typically arrive at multiple entry points, and dispatching them to servers is an urgent distributed systems problem. This paper presents an efficient solution to the load balancing problem in such systems that improves on and overcomes problems of previous solutions. The load balancing problem is formulated as a stochastic optimization problem, and an efficient algorithmic solution is obtained based on a subtle mathematical analysis of the problem. Finally, extensive evaluation of the solution on simulated data shows that it outperforms previous solutions. Moreover, the resulting dispatching policy can be computed very efficiently, making the solution practically viable.
We show that graphs excluding K2,t as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate...
详细信息
ISBN:
(纸本)9798400718854
We show that graphs excluding K2,t as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.
distributed consensus algorithms such as Paxos have been studied extensively. Many different liveness properties and assumptions have been stated for them, but there are no systematic comparisons for better understand...
详细信息
ISBN:
(纸本)9781450385480
distributed consensus algorithms such as Paxos have been studied extensively. Many different liveness properties and assumptions have been stated for them, but there are no systematic comparisons for better understanding of these properties. This paper systematically studies and compares different liveness properties stated for over 30 prominent consensus algorithms and variants. We introduced a precise high-level language and formally specified these properties in the language. We then create a hierarchy of liveness properties combining two hierarchies of the assumptions used and a hierarchy of the assertions made, and compare the strengths and weaknesses of algorithms that ensure these properties. Our formal specifications and systematic comparisons led to the discovery of a range of problems in various stated liveness properties. We also developed TLA+ specifications of these liveness properties, and we used model checking of execution steps to illustrate liveness patterns for Paxos.
We study the replacement paths problem in the CONGEST model of distributedcomputing. Given an s-t shortest path P, the goal is to compute, for every edge e in P, the shortest-path distance from s to t avoiding e. For...
详细信息
ISBN:
(纸本)9798400718854
We study the replacement paths problem in the CONGEST model of distributedcomputing. Given an s-t shortest path P, the goal is to compute, for every edge e in P, the shortest-path distance from s to t avoiding e. For unweighted directed graphs, we establish the tight randomized round complexity bound for this problem as [EQUATION] by showing matching upper and lower bounds. Our upper bound extends to (1 + ϵ)-approximation for weighted directed graphs. Our lower bound applies even to the second simple shortest path problem, which asks only for the smallest replacement path length. These results improve upon the very recent work of Manoharan and Ramachandran (SIROCCO 2024), who showed a lower bound of [EQUATION] and an upper bound of [EQUATION], where hst is the number of hops in the given s-t shortest path P.
We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandur...
详细信息
ISBN:
(纸本)9798400718854
We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandurangan PODC 2020) and defines the awake complexity (also called energy complexity), which measures the maximum number of rounds that any node is awake throughout the execution. Only awake nodes can send and receive messages in a given round and all messages sent to sleeping nodes are lost. We present new deterministic consensus algorithms that tolerate up to f < n crash failures, where n is the number of nodes. Our algorithms match the optimal time complexity lower bound of f + 1 rounds. For multi-value consensus, where the input values are chosen from some possibly large set, we achieve an energy complexity of [EQUATION] rounds, whereas for binary consensus, we show that [EQUATION] rounds are possible.
The Freeze-Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. While there exists a wide literature on the centralized setting, where the locations of the robots are known in a...
详细信息
ISBN:
(纸本)9798400718854
The Freeze-Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. While there exists a wide literature on the centralized setting, where the locations of the robots are known in advance, we focus on the distributed version where the locations of the robots, P, are unknown, and where awake robots only detect other robots up to distance 1. Assuming that moving at distance δ takes a time δ, we show that waking up the whole swarm takes O(ρ + ℓ2 log(ρ/ℓ)), where ρ is the largest distance from the initial robot to any point of P, and ℓ is the connectivity threshold of P. Moreover, the result is complemented by a matching lower bound. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.
暂无评论