The area of distributed monitoring requires tracking the value of a function of distributed data as new observations are made. An important case is when attention is restricted to only a recent time period, such as th...
详细信息
So far, the distributedcomputing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These ...
详细信息
Gathering data from nodes in a network is at the heart of many distributed applications, most notably, while performing a global task. We consider information spreading among n nodes of a network, where each node v ha...
详细信息
ISBN:
(纸本)9780898719932
Gathering data from nodes in a network is at the heart of many distributed applications, most notably, while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running times for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, after which messages are sent across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has a large weak conductance, from polynomial to polylogarithmic number of rounds. We demonstrate the power of fast information spreading in accomplishing global tasks on the leader election problem, which lies at the core of distributedcomputing. Our results yield an algorithm for leader election that has a scalable running time on graphs with large weak conductance, improving significantly upon previous results.
We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and >>n selfish agents that unilate...
详细信息
ISBN:
(纸本)9780898719932
We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and >>n selfish agents that unilaterally decide to move from one vetex to another if this improves their experienced load. We present several protocols for concurrent migration that satisfy desirable properties such as being based only on local information and computation and the absence of global coordination or cooperation of agents. Our main contribution is to show rapid convergence of the resulting migration process to states that satisfy different stability or balance criteria. In particular, the convergence time to a Nash equilibrium is only logarithmic in m and polynomial in n, where the polynomial depends on the graph structure. Using a slight modification with neutral moves, a perfectly balanced state can be reached after additional time polynomial in n. In addition, we show reduced convergence times to approximate Nash equilibria. Finally, we extend our results to networks of machines with different speeds or to agents that have different weights and show similar results for convergence to approximate and exact Nash equilibria.
The area of distributed monitoring requires tracking the value of a function of distributed data as new observations are made. An important case is when attention is restricted to only a recent time period, such as th...
详细信息
ISBN:
(纸本)9781450307192
The area of distributed monitoring requires tracking the value of a function of distributed data as new observations are made. An important case is when attention is restricted to only a recent time period, such as the last hour of readings---the sliding window case. In this announcement, we outline a novel paradigm for handling such monitoring problems, which we dub the "forward/backward" approach. This provides clean solutions for several fundamental problems, such as counting, tracking frequent items, and maintaining order statistics. We obtain efficient protocols for these problems that improve on previous work, and are easy to implement. Specifically, we obtain optimal O(k/ε log(ε n/k)) communication per window of n updates for tracking counts and heavy hitters with accuracy ε across k sites; and near-optimal communication of O(k/epsilon log2(1/ε) log (n/k)) for quantiles.
We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bo...
详细信息
ISBN:
(纸本)9781595939890
We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing an MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.
The proceedings contain 88 papers. The topics discussed include: transactional predication: high-performance concurrent sets and maps for STM;the multiplicative power of consensus numbers;the k-bakery: local-spin k-ex...
ISBN:
(纸本)9781605588889
The proceedings contain 88 papers. The topics discussed include: transactional predication: high-performance concurrent sets and maps for STM;the multiplicative power of consensus numbers;the k-bakery: local-spin k-exclusion using non-atomic reads and writes;on asymmetric progress conditions;on enhancing concurrency in distributed transactional memory;queuing or priority queuing? on the design of cache-coherence protocols for distributed transactional memory;verifying linearizability with hindsight;eventually linearizable shared objects;towards robust medium access in multi-hop networks;complexity and solution of the send-receive correlation problem;superpeer formation amidst churn and rewiring;adaptive randomized mutual exclusion in sub-logarithmic expected time;distributed computational complexities: are you Volvo-addicted or Nascar-obsessed?;and adaptive system anomaly prediction for large-scale hosting infrastructures.
暂无评论