作者：
Kuhn, FabianMIT
Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA
We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum ...
详细信息
ISBN:
(纸本)9781605586069
We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d > 0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k > 0, we call a coloring k-partially proper if every node v has at least min {k, deg(v)} neighbors with a different color We show that for all d is an element of {1, ... , Delta}, it is possible to compute a O(Delta(2)/d(2))-coloring with defect d in time O(log* n) where Delta is the largest degree of the network graph. Similarly, for all k is an element of {1, ... , Delta}, a k-partially proper O(k(2))-coloring can be computed in O(log* n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Delta + log* n), a (Delta + 1)-coloring can be computed, a task for which the best previous algorithm required time O(Delta log Delta + log* n). The same result holds for the problem of computing a maximal independent set.
One of the main methods for achieving fault tolerance in distributed systems is recovery of the state of failed components. Though generic recovery methods like check-pointing and message logging exist, in many cases ...
详细信息
ISBN:
(纸本)0769516599
One of the main methods for achieving fault tolerance in distributed systems is recovery of the state of failed components. Though generic recovery methods like check-pointing and message logging exist, in many cases the recovery has to be application specific. In this paper we propose a general model for a node state reconstruction after crash failures. In our model the reconstruction operation is defined only by the requirements it fulfills, without referring to the specific application dependent way it is performed. The model provides a framework for formal treatment of algorithm-specific and system-specific recovery procedures. It is used to specify node state reconstruction procedures for several widely used distributed algorithms and systems, as well as to prove their correctness.
The MIN ENERGY BROADCAST problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize t...
详细信息
ISBN:
(纸本)9781605582351
The MIN ENERGY BROADCAST problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. MIN ENERGY BROADCAST is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a root n x root n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. By using information-theoretic arguments, we prove a lower bound (1 - epsilon) n/pi on the energy cost of any feasible solution for this problem. Then, we provide an efficient solution of energy cost not larger than 1.1204n/pi. Finally, we present a fully-distributed protocol that constructs a broadcast range assignment of energy cost not larger than 8n, thus still yielding constant approximation. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is asymptotically optimal. The completion time of the protocol is only a O(logn) factor slower than the optimum. The approximation quality of our distributed solution is also experimentally evaluated. All bounds hold with probability at least 1 - 1/n(circle minus(1)).
In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) ...
详细信息
ISBN:
(纸本)9781450361842
In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model. LP-type problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover. In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random. Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions. Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LP-type problem is constant, even if the size of the given LP-type problem is polynomially large in the number of nodes.
A technique to model and to verify distributed algorithms is suggested. This technique (based on Petri nets) reduces the modelling and analysis effort to a reasonable level. The paper outlines the technique using the ...
详细信息
A technique to model and to verify distributed algorithms is suggested. This technique (based on Petri nets) reduces the modelling and analysis effort to a reasonable level. The paper outlines the technique using the example of a typical network algorithm, the echo algorithm.
The Fisher market is one of the most fundamental models for resource allocation. However, Fisher markets are less amenable for resource allocation settings when agents have additional linear constraints beyond the bud...
详细信息
The Fisher market is one of the most fundamental models for resource allocation. However, Fisher markets are less amenable for resource allocation settings when agents have additional linear constraints beyond the budget constraints of buyers and the capacity constraints of goods. Thus, in this work, we introduce a modified Fisher market, where agents may have additional linear constraints, and study the properties of the resulting equilibria. To set equilibrium prices, we introduce a budget-adjusted social optimization problem (BA-SOP), whose optimal dual variables correspond to the equilibrium prices. Since solving BA-SOP can be computationally intensive and requires centralized knowledge of all agents' utilities, we propose a new class of distributed algorithms based on the Alternating Direction Method of Multipliers (ADMM) to compute equilibrium prices. Our ADMM approach has strong convergence guarantees and provides a general-purpose method for computing market equilibria for Fisher markets with homogeneous linear constraints and classical Fisher markets. & COPY;2023 Published by Elsevier Inc.
Weak adversaries are a way to model the uncertainty due to asynchrony in randomized distributed algorithms. They are a standard notion in correctness proofs for distributed algorithms, and express the property that th...
详细信息
ISBN:
(数字)9783030670672
ISBN:
(纸本)9783030670665;9783030670672
Weak adversaries are a way to model the uncertainty due to asynchrony in randomized distributed algorithms. They are a standard notion in correctness proofs for distributed algorithms, and express the property that the adversary (scheduler), which has to decide which messages to deliver to which process, has no means of inferring the outcome of random choices, and the content of the messages. In this paper, we introduce a model for randomized distributed algorithms that allows us to formalize the notion of weak adversaries. It applies to randomized distributed algorithms that proceed in rounds and are tolerant to process failures. For this wide class of algorithms, we prove that for verification purposes, the class of weak adversaries can be restricted to simple ones, so-called round-rigid adversaries, that keep the processes tightly synchronized. As recently a verification method for round-rigid adversaries has been introduced, our new reduction theorem paves the way to the parameterized verification of randomized distributed algorithms under the more realistic weak adversaries.
Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1, 1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node...
详细信息
ISBN:
(纸本)9781611974782
Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1, 1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their d...
详细信息
ISBN:
(纸本)9781509016631
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their developments and their proofs. Moreover, the proofs which have been presented are done manually. In this paper, we propose a reuse based approach for specifying and proving distributed algorithms in dynamic networks. It consists in developing a formal pattern using Event-B method, based on refinement techniques. The proposed pattern allows to handle topological events in dynamic networks and to characterize the concept of time. Our solution relies on evolving graphs as a powerful model to record the evolution of a network topology. To illustrate it, we present an example of a distributed counting algorithm. The proof statistics related to the development of the pattern and the algorithm show the efficiency of our solution.
In this study, we investigate the problem of accelerating distributed algorithms for solving linear equations over multi-agent networks. While almost all distributed algorithms in the literature assume that the equati...
详细信息
In this study, we investigate the problem of accelerating distributed algorithms for solving linear equations over multi-agent networks. While almost all distributed algorithms in the literature assume that the equations are not shared with the neighboring agents, it is shown that the assumption is not restrictive, and an algorithm has been proposed which can be used to determine the equations of the neighbors. We also present a numerical example to illustrate that the convergence rate of a distributed algorithm can be significantly improved by using the proposed algorithm. (C) 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
暂无评论