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 demand for low latency, bandwidth efficiency, and privacy has driven distributed applications to the network edge, where heterogeneous, and untrusted, and uncontrolled networks pose challenges. This paper presents...
详细信息
ISBN:
(纸本)9798400706295
The demand for low latency, bandwidth efficiency, and privacy has driven distributed applications to the network edge, where heterogeneous, and untrusted, and uncontrolled networks pose challenges. This paper presents a software-defined overlay networking (SDON) middleware that simplifies application development through centralized control of edge resources while addressing many challenges prevalent at the edge. SDON enables applications to specify high-level requirements, such as service placement and communication goals. These are automatically translated into device-specific configurations and deployed on appropriate edge resources. The middleware is implemented as fully functional software, published as open-source, and will be evaluated in multiple edge computing use cases, to demonstrate its application optimization potential.
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.
We use "unplugged" activities to introduce parallel concepts in a first-year seminar for Computer Science majors. Student teams explore parallel approaches to computational tasks. Pre- and post-activity surv...
详细信息
ISBN:
(纸本)9781450390705
We use "unplugged" activities to introduce parallel concepts in a first-year seminar for Computer Science majors. Student teams explore parallel approaches to computational tasks. Pre- and post-activity surveys, and a reflection paper, measure the impact of these activities on students' views about parallel programming. Our goal is to encourage parallel thinking about programming tasks before sequential approaches become ingrained. Computer Science curricula have traditionally focused on sequential approaches to programming, which were well matched to earlier computer systems. However, current systems almost all use multiprocessor CPUs, and are frequently used in clusters or networks of multiple computers. Recent curricular guidelines from organizations such as acm and ABET recommend exposure to parallel computing concepts.
Esparza and Reiter have recently conducted a systematic comparative study of models of distributedcomputing consisting of a network of identical finite-state automata that cooperate to decide if the underlying graph ...
详细信息
ISBN:
(纸本)9781450385480
Esparza and Reiter have recently conducted a systematic comparative study of models of distributedcomputing consisting of a network of identical finite-state automata that cooperate to decide if the underlying graph of the network satisfies a given property. The study classifies models according to four criteria, and shows that twenty-four initially possible combinations collapse into seven equivalence classes with respect to their decision power, i.e. the properties that the automata of each class can decide. However, Esparza and Reiter only show (proper) inclusions between the classes, and so do not characterise their decision power. In this paper we do so for labelling properties, i.e. properties that depend only on the labels of the nodes, but not on the structure of the graph. In particular, majority (whether more nodes carry label a than b) is a labelling property. Our results show that only one of the seven equivalence classes identified by Esparza and Reiter can decide majority for arbitrary networks. We then study the expressive power of the classes on bounded-degree networks, and show that three classes can. In particular, we present an algorithm for majority that works for all bounded-degree networks under adversarial schedulers, i.e. even if the scheduler must only satisfy that every node makes a move infinitely often, and prove that no such algorithm can work for arbitrary networks.
Given a graph G = (V, E), a β-ruling set is a subset S ⊆ V that is i) independent, and ii) every node υ ∈ V has a node of S within distance β. In this paper we present almost optimal distributed algorithms for fin...
详细信息
ISBN:
(纸本)9798400718854
Given a graph G = (V, E), a β-ruling set is a subset S ⊆ V that is i) independent, and ii) every node υ ∈ V has a node of S within distance β. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an O(log log n)-round randomized algorithm for computing 2-ruling sets on trees, almost matching the Ω (log log n/log log log n) lower bound given by Balliu et al. [FOCS'20]. Second, we show that 2-ruling sets can be solved in Õ(log5/3 log n) rounds in high-girth graphs. Lastly, we show that O(log log log n)-ruling sets can be computed in Õ(log log n) rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance β.
This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined ...
详细信息
ISBN:
(纸本)9781450391467
This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined by an adversary. The adversary promises that in every T consecutive rounds, the T (potentially different) topologies in those.. rounds contain a common connected subgraph that spans all nodes. Within such a context, we propose novel algorithms for solving some fundamental distributedcomputing problems such as Count/Consensus/Max. Our algorithms are the first algorithms whose complexities do not contain an Omega(N) term, under constant T values. Previous sublinear algorithms require significantly larger T values.
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as t...
详细信息
ISBN:
(纸本)9781450385480
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes. We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, fault-tolerant subset distance preservers and +4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults.
Over the most recent years, quantized graph neural network (QGNN) attracts lots of research and industry attention due to its high robustness and low computation and memory overhead. Unfortunately, the performance gai...
详细信息
ISBN:
(纸本)9781450392044
Over the most recent years, quantized graph neural network (QGNN) attracts lots of research and industry attention due to its high robustness and low computation and memory overhead. Unfortunately, the performance gains of QGNN have never been realized on modern GPU platforms. To this end, we propose the first Tensor Core (TC) based computing framework, QGTC, to support any-bitwidth computation for QGNNs on GPUs. We introduce a novel quantized low-bit arithmetic design based on the low-bit data representation and bit-decomposed computation. We craft a novel TC-tailored CUDA kernel design by incorporating 3D-stacked bit compression, zero-tile jumping, and non-zero tile reuse technique to improve the performance systematically. We incorporate an effective bandwidth-optimized subgraph packing strategy to maximize the transferring efficiency between CPU host and GPU device. We integrate QGTC with Pytorch for better programmability and extensibility. Extensive experiments demonstrate that QGTC can achieve evident inference speedup (on average 2.7x) compared with the state-of-the-art DGL framework across diverse settings.
暂无评论