We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that w...
详细信息
ISBN:
(纸本)9781581138023
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementati...
详细信息
ISBN:
(纸本)9781581138023
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t
The proceedings contain 84 papers. The topics discussed include: social networks spread rumors in sublogarithmic time;quantum one-way communication can be exponentially stronger than classical communication;cover time...
详细信息
ISBN:
(纸本)9781450306911
The proceedings contain 84 papers. The topics discussed include: social networks spread rumors in sublogarithmic time;quantum one-way communication can be exponentially stronger than classical communication;cover times, blanket times, and majorizing measures;the equivalence of the random oracle model and the ideal cipher model, revisited;limits of provable security from standard assumptions;an impossibility result for truthful combinatorial auctions with submodular valuations;towards coding for maximum errors in interactive communication;rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm;pseudorandom generators for combinatorial shapes;electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs;subexponential lower bounds for randomized pivoting rules for the simplex algorithm;distributed verification and hardness of distributed approximation;and the topology of wireless communication.
This paper describes a High Intensity Radiated Fields experiment conducted at the NASA Langley Research Center to validate a tracking performance model for a Boeing 747 digital flight control system implemented on a d...
详细信息
ISBN:
(纸本)9781424495931
This paper describes a High Intensity Radiated Fields experiment conducted at the NASA Langley Research Center to validate a tracking performance model for a Boeing 747 digital flight control system implemented on a distributed recoverable computing platform which is subject to upsets. While the upset data does not appear to be Markov, it is found that a burst model for the upset process can be introduced so that a Markov jump-linear performance model can reliably provide an upper bound on the tracking error of the system.
In most modern networks, nodes have access to various modes of communication each with different characteristics. In this work we consider the Hybrid model of distributedcomputing, introduced recently by Augustine, H...
详细信息
ISBN:
(纸本)9798400706684
In most modern networks, nodes have access to various modes of communication each with different characteristics. In this work we consider the Hybrid model of distributedcomputing, introduced recently by Augustine, Hinnenthal, Kuhn, Scheideler, and Schneider (SODA 2020), where nodes have access to two different communication modes: high-bandwidth local communication along the edges of the graph and low-bandwidth all-to-all communication, capturing the non-uniform nature of modern communication networks. It is noteworthy that the Hybrid model in its most general form covers most of the classical distributed models as marginal *** work in Hybrid has focused on showing existentially optimal algorithms, meaning there exists a pathological family of instances on which no algorithm can do better. This neglects the fact that such worst-case instances often do not appear or can be actively avoided in practice. In this work, we focus on the notion of universal optimality, first raised by Garay, Kutten, and Peleg (FOCS 1993). Roughly speaking, a universally optimal algorithm is one that, given any input graph, runs as fast as the best algorithm designed specifically for that *** show the first universally optimal algorithms in Hybrid, up to polylogarithmic factors. We present universally optimal solutions for fundamental tools that solve information dissemination problems, such as broadcasting and unicasting multiple messages in a Hybrid network. Furthermore, we demonstrate these tools for information dissemination can be used to obtain universally optimal solutions for various shortest paths problems in Hybrid. A major conceptual contribution of this work is the conception of a new graph parameter called neighborhood quality that captures the inherent complexity of many fundamental graph problems in the Hybrid model. We also develop new existentially optimal shortest paths algorithms in Hybrid, which are utilized as key subroutines in our universally optimal al
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchron...
详细信息
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchronous processors start performing tasks in isolation and where an adversary can force an arbitrary pattern of merges. Following a merge, processors are able to share their knowledge about the computational progress prior to the merge.
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by f...
详细信息
ISBN:
(纸本)9781581138023
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2,/k) and Ω(Δ1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/ log log n) and Ω(log Δ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources...
详细信息
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.
The proceedings contain 61 papers. The topics discussed include: programming the world of uncertain things;type theory in type theory using quotient inductive types;system F-omega with equirecursive types for datatype...
ISBN:
(纸本)9781450335492
The proceedings contain 61 papers. The topics discussed include: programming the world of uncertain things;type theory in type theory using quotient inductive types;system F-omega with equirecursive types for datatype-generic programming;a theory of effects and resources: adjunction models and polarized calculi;temporal verification of higher-order functional programs;scaling network verification using symmetry and surgery;model checking for symbolic-heap separation logic with inductive predicates;reducing crash recoverability to reachability;query-guided maximum satisfiability;string solving with word equations and transducers: towards a logic for analyzing mutation XSS;symbolic computation of differential equivalences;and unboundedness and downward closures of higher-order pushdown automata.
Computation in a typical Transformer-based large language model (LLM) can be characterized by batch size, hidden dimension, number of layers, and sequence length. Until now, system works for accelerating LLM training ...
详细信息
暂无评论