In my presentation I will propose a new link-layer model for distributedcomputing based on so-called relays that promises to be useful for the design of robust and secure distributed systems based on overlay networks...
详细信息
We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a ...
详细信息
ISBN:
(纸本)9781450357951
We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a A-coloring in 0((log log n)2) rounds when A E [3, 0(1)]. Both these algorithms improve on an 0 (log3 n/log A) round algorithm of Panconesi and Srinivasan [STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Q (log log n) round lower bound of Brandt et al. [STOC'16].
Over the years, developments such as cloud computing, Internet of Things, and now edge and fog computing, have probably caused paradigm fatigue among practitioners. The question arises whether adopting a specific para...
详细信息
The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the deterministic leader election problem with an asymptotically optimal round c...
详细信息
ISBN:
(纸本)9781450357951
The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the deterministic leader election problem with an asymptotically optimal round complexity. Using this result, we obtain an asymptotically optimal randomized leader election algorithm for anonymous networks, as well as improved algorithms for symmetry-breaking and communication primitives. The techniques that we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model.
We bound the performance guarantees that follow from Turan-like bounds for unweighted and weighted independent sets in bounded degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round dist...
详细信息
ISBN:
(纸本)9781450357951
We bound the performance guarantees that follow from Turan-like bounds for unweighted and weighted independent sets in bounded degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight (Delta + 1)/2-approximation in unweighted graphs of maximum degree Delta, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Delta + 1)-approximation, but a simple modification results in an asymptotic expected 0.529(Delta + 1)-approximation.
The tutorial provides an overview of the principles and "pearls" of constructing, maintaining and optimizing network topologies, such as peer-to-peer overlays or datacenter interconnects. The tutorial consis...
详细信息
ISBN:
(纸本)9781450357951
The tutorial provides an overview of the principles and "pearls" of constructing, maintaining and optimizing network topologies, such as peer-to-peer overlays or datacenter interconnects. The tutorial consists of two parts: Self-stabilization: In the first part, we start simple by discussing basic mechanisms to reconfigure networks while maintaining connectivity. You will then learn how to design and analyze self-stabilizing algorithms for line topologies as well as more sophisticated networks such as hypercubes. A self-stabilizing algorithm guarantees that the network will automatically reconfigure to a "good topology" from an arbitrary initial state. Self-optimization: After we have learned how to design self-stabilizing networks, we will consider algorithms to design self-adjusting resp. "self-optimizing" networks: networks which not only "repair" themselves but also optimize themselves towards the demand. The study of such selfadjusting networks is motivated by emerging technologies in the context of datacenters and wide-area networks, allowing to reconfigure networks at runtime.
We introduce a new distributedcomputing model called m&m that allows processes to both pass messages and share memory. Motivated by recent hardware trends, we find that this model improves the power of the pure m...
详细信息
ISBN:
(纸本)9781450357951
We introduce a new distributedcomputing model called m&m that allows processes to both pass messages and share memory. Motivated by recent hardware trends, we find that this model improves the power of the pure message-passing and shared-memory models. As we demonstrate by example with two fundamental problems-consensus and eventual leader election-the added power leads to new algorithms that are more robust against failures and asynchrony. Our consensus algorithm combines the superior scalability of message passing with the higher fault tolerance of shared memory, while our leader election algorithms reduce the system synchrony needed for correctness. These results point to a wide new space for future exploration of other problems, techniques, and benefits.
We present a deterministic distributed algorithm to compute all pairs shortest paths (APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in (O) over tilde (n(3/2)) rounds in the Congest model, ...
详细信息
ISBN:
(纸本)9781450357951
We present a deterministic distributed algorithm to compute all pairs shortest paths (APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in (O) over tilde (n(3/2)) rounds in the Congest model, where n is the number of nodes in the graph. This is the first o(n(2)) rounds deterministic distributed algorithm for the weighted APSP problem. Our algorithm is fairly simple and incorporates a deterministic distributed algorithm we develop for computing a `blocker set' [14], which has been used earlier in sequential dynamic computation of APSP.
In the minimum k-edge-connected spanning subgraph (k-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to k - 1 edge failures. This is a central problem in network design, and a natural gen...
详细信息
ISBN:
(纸本)9781450357951
In the minimum k-edge-connected spanning subgraph (k-ECSS) problem the goal is to find the minimum weight subgraph resistant to up to k - 1 edge failures. This is a central problem in network design, and a natural generalization of the minimum spanning tree (MST) problem. While the MST problem has been studied extensively by the distributedcomputing community, for k > 2 less is known in the distributed setting. In this paper, we present fast randomized distributed approximation algorithms for k-ECSS in the CONGEST model. Our first contribution is an (O) over tilde (D + root n)-round O(log n)-approximation for 2-ECSS, for a graph with n vertices and diameter D. The time complexity of our algorithm is almost tight and almost matches the time complexity of the MST problem. For larger constant values of k we give an (O) over tilde (n)-round O(log n)-approximation. Additionally, in the special case of unweighted 3-ECSS we show how to improve the time complexity to O(D log(3) n) rounds. All our results significantly improve the time complexity of previous algorithms.
This paper gives a brief presentation of a comprehensive study on the necessary and sufficient state space conditions for the deterministic naming task in the population protocol model. This problem is studied under v...
详细信息
ISBN:
(纸本)9781450357951
This paper gives a brief presentation of a comprehensive study on the necessary and sufficient state space conditions for the deterministic naming task in the population protocol model. This problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is given.
暂无评论