The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known ...
详细信息
ISBN:
(纸本)9781595936165
The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known Unit Disk Graphs. In contrast to the fastest (time-optimal) existing approach [11], we assume that no geometric information (e.g., distances in the graph's embedding) is given. Instead, nodes employ randomization for their decisions. Our algorithm computes a MIS in O(log log n . log* n) rounds with very high probability for graphs with bounded growth, where n denotes the number of nodes in the graph. In view of Linial's Omega(log* n) lower bound for computing a MIS in ring networks [2] which was extended to randomized algorithms independently by Naor [18] and Linial [13], our solution is close to optimal. In a nutshell, our algorithm shows that for computing a MIS, randomization is a viable alternative to distance information.
The proceedings contain 65 papers. The topics discussed include: the greedy spanner is existentially optimal;distributed algorithms for planar networks i: planar embedding;brief announcement: labeling schemes for powe...
ISBN:
(纸本)9781450339643
The proceedings contain 65 papers. The topics discussed include: the greedy spanner is existentially optimal;distributed algorithms for planar networks i: planar embedding;brief announcement: labeling schemes for power-law graphs;brief announcement: sublinear-space distance labeling using hubs;brief announcement: optimal leader election in multi-hop radio networks;brief announcement: the small world of curious beings;a randomized concurrent algorithm for disjoint set union;brief announcement: local independent set approximation;deterministic objects: life beyond consensus;unbeatable set consensus via topological and combinatorial reasoning;and a polylogarithmic gossip algorithm for plurality consensus.
Mutual exclusion is a topic that Leslie Lamport has returned to many times throughout his career. This article, which is being written in celebration of Lamport's sixtieth birthday, is an attempt to survey some of...
详细信息
Mutual exclusion is a topic that Leslie Lamport has returned to many times throughout his career. This article, which is being written in celebration of Lamport's sixtieth birthday, is an attempt to survey some of his many contributions to research on this topic.
A new model is proposed for measuring the expected cost of a network operation. The model exhibits monotonicity which means that the cost for site s to communicate with site t must be no greater than the cost for site...
详细信息
ISBN:
(纸本)9780897918008
A new model is proposed for measuring the expected cost of a network operation. The model exhibits monotonicity which means that the cost for site s to communicate with site t must be no greater than the cost for site s to communicate with both site t and some other set of sites. Moreover, by assigning a meaningful cost to all transactions, including unsuccessful one, the cost model allow to minimize the overall network cost independent of data availability. This in contrast to a cost model that minimizes the overall network cost by minimizing data availability.
We propose a new system model for asynchronous distributed systems that we call the message classification model. Motivation for this model is its ability 1) to support a restricted but useful form of `communication b...
详细信息
We propose a new system model for asynchronous distributed systems that we call the message classification model. Motivation for this model is its ability 1) to support a restricted but useful form of `communication by time' by classifying messages as either `slow' or `fast' but without incorporating neither real-time clocks nor `time-outs', and 2) to describe transient and permanent network partitions. The message classification model allows the definition of different classes of classification schemes. To show that the model is indeed useful, we show how one can solve the consensus and the election problem for a certain class of message classification schemes.
Erasure coding can reduce the space and bandwidth overheads of redundancy in fault-tolerant data storage and delivery systems. But it introduces the fundamental difficulty of ensuring that all erasure-coded fragments ...
详细信息
ISBN:
(纸本)9781595936165
Erasure coding can reduce the space and bandwidth overheads of redundancy in fault-tolerant data storage and delivery systems. But it introduces the fundamental difficulty of ensuring that all erasure-coded fragments correspond to the same block of data. Without such assurance, a different block may be reconstructed from different subsets of fragments. This paper develops a technique for providing this assurance without the bandwidth and computational overheads associated with current approaches. The core idea is to distribute with each fragment what we call homomorphic fingerprints. These fingerprints preserve the structure of the erasure code and allow each fragment to be independently verified as corresponding to a specific block. We demonstrate homomorphic fingerprinting functions that are secure, efficient, and compact.
A new model that depicts a network of randomized finite state machines operating in an asynchronous environment is introduced. This model, that can be viewed as a hybrid of the message passing model and cellular autom...
详细信息
ISBN:
(纸本)9781450320658
A new model that depicts a network of randomized finite state machines operating in an asynchronous environment is introduced. This model, that can be viewed as a hybrid of the message passing model and cellular automata is suitable for applying the distributedcomputing lens to the study of networks of sub-microprocessor devices, e.g., biological cellular networks and man-made nano-networks. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of an abstract computer, we show that some of the most important and extensively studied distributedcomputing problems can still be solved efficiently. Copyright 2013 acm.
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.
暂无评论