BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating...
详细信息
ISBN:
(纸本)9781450385480
BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating a minority corruption, recently, in Crypto'19, a weaker synchrony assumption called mobile sluggish faults was introduced. In this work, we investigate the support for mobile sluggish faults in existing synchronous protocols such as Dfinity, Streamlet, Sync HotStuff, OptSync and the optimal latency BFT protocol. We identify key principles that can be used to "compile" these synchronous protocols to tolerate mobile sluggish faults.
This work focuses on understanding the quantum message complexity of two central problems in distributedcomputing, namely, leader election and agreement in synchronous message-passing communication networks. We show ...
详细信息
ISBN:
(纸本)9798400718854
This work focuses on understanding the quantum message complexity of two central problems in distributedcomputing, namely, leader election and agreement in synchronous message-passing communication networks. We show that quantum communication gives an advantage for both problems by presenting quantum distributed algorithms that significantly outperform their respective classical counterparts under various network *** prior works have studied and analyzed quantum distributed algorithms in the context of (improving) round complexity, a key conceptual contribution of our work is positing a framework to design and analyze the message complexity of quantum distributed algorithms. We present and demonstrate how quantum algorithmic techniques, such as Grover search, quantum counting, and quantum walks, can significantly enhance the message efficiency of distributed *** particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity. To the best of our knowledge, this is the first such application of quantum walks in distributedcomputing.
Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance e of each other. Many variants of this task have been considered in the literature: cont...
详细信息
ISBN:
(纸本)9781450385480
Approximate agreement is a weaker version of consensus where two or more processes must agree on a real number within a distance e of each other. Many variants of this task have been considered in the literature: continuous or discrete ones;multi-dimensional ones;as well as agreement on graphs and other spaces. We focus on two variants of approximate agreement on graphs, edge agreement and clique agreement. We show that both tasks arise as special cases of a more general, higher-dimensional, approximate agreement task, where the processes must agree on the vertices of a simplex in a given simplicial complex. This new point of view gives rise to a novel topological perspective on the solvability of clique agreement.
Real-time data processing applications with low latency requirements have led to the increasing popularity of stream processing systems. While such systems offer convenient APIs that can be used to achieve data parall...
详细信息
ISBN:
(纸本)9781450392044
Real-time data processing applications with low latency requirements have led to the increasing popularity of stream processing systems. While such systems offer convenient APIs that can be used to achieve data parallelism automatically, they offer limited support for computations that require synchronization between parallel nodes. In this paper, we propose dependency-guided synchronization (DGS), an alternative programming model for stateful streaming computations with complex synchronization requirements. In the proposed model, the input is viewed as partially ordered, and the program consists of a set of parallelization constructs which are applied to decompose the partial order and process events independently. Our programming model maps to an execution model called synchronization plans which supports synchronization between parallel nodes. Our evaluation shows that APIs offered by two widely used systems-Flink and Timely Dataflow-cannot suitably expose parallelism in some representative applications. In contrast, DGS enables implementations with scalable performance, the resulting synchronization plans offer throughput improvements when implemented manually in existing systems, and the programming overhead is small compared to writing sequential code.
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part....
详细信息
Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial gl...
详细信息
ISBN:
(纸本)9781450385480
Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin et al. has shown that the counting predicates x >= eta have state complexity O(log eta) for leaderless protocols and O(log log eta) for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of x >= eta is Omega(log log log eta) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.
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.
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary m-facet polytopes in.. variables with seed length poly-logarithmic in m,n, concluding a sequence...
详细信息
ISBN:
(纸本)9781450392648
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary m-facet polytopes in.. variables with seed length poly-logarithmic in m,n, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, Zuckerman (SICOMP 2013) for fooling linear and polynomial threshold functions, respectively. In this work, we consider a natural extension of PRGs for intersections of positive spectrahedra. A positive spectrahedron is a Boolean function f(x) = [x(1)A(1) + center dot center dot center dot+x(n)A(n) <= B] where the A(1)s are kxk positive semidefinite matrices. We construct explicit PRGs that delta-fool "regular" width-M positive spectrahedra (i.e., when none of the A(1)s are dominant) over the Boolean space with seed length poly(logk, logn,M, 1/delta). Our main technical contributions are the following: We first prove an invariance principle for positive spectrahedra via the well-known Lindeberg method. As far as we are aware such a generalization of the Lindeberg method was unknown. Second, we prove an upper bound on noise sensitivity and a LittlewoodOfford theorem for positive spectrahedra. Using these results, we give applications for constructing PRGs for positive spectrahedra, learning theory, discrepancy sets for positive spectrahedra (over the Boolean cube) and PRGs for intersections of structured polynomial threshold functions.
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.
暂无评论