A shared disk implementation on distributed storage requires consistent behavior of disk operations. Deterministic consensus on such behavior is impossible when even a single storage node can fail. Atomic registers sh...
详细信息
ISBN:
(纸本)9781605588889
A shared disk implementation on distributed storage requires consistent behavior of disk operations. Deterministic consensus on such behavior is impossible when even a single storage node can fail. Atomic registers show how consistency can be achieved without reaching consensus, but suffer from a crash consistency problem. the presented shared disk algorithm, based on atomic registers and probabilistic consensus, can survive multiple storage node failures, as long as a majority of nodes respond.
distributed transactional memory (TM) models based on globally-consistent contention management policies may abort many transactions that could potentially commit without violating correctness. To reduce unnecessary a...
详细信息
ISBN:
(纸本)9781605588889
distributed transactional memory (TM) models based on globally-consistent contention management policies may abort many transactions that could potentially commit without violating correctness. To reduce unnecessary aborts and increase concurrency, we propose the distributed dependency-aware (or DDA) model for distributed TM, which manages dependencies between conflicting and uncommitted transactions so that they can commit safely. We present a distributed algorithm to decide whether to abort a transaction based on local precedence graphs that model the established dependency relationships. We analyze the performance of our algorithm and illustrate the inherent tradeoff of the DDA model between communication cost and concurrency.
We study the stable marriage problem in a distributed setting. the communication network is a bipartite graph, with men on one side and women on the other. Acceptable partners are connected by edges, and each particip...
详细信息
ISBN:
(纸本)9781605588889
We study the stable marriage problem in a distributed setting. the communication network is a bipartite graph, with men on one side and women on the other. Acceptable partners are connected by edges, and each participant has chosen a linear order on the adjacent nodes, indicating the matching preferences. the classical Gale-Shapley algorithm could be simulated in such a network to find a stable matching. However, the stable matching problem is inherently global: the worst-case running time of any distributed algorithm is linear in the diameter of the network. Our work shows that if we tolerate a tiny fraction of unstable edges, then a solution can be found by a fast local algorithm: simply truncating a distributed simulation of the Gale-Shapley algorithm is sufficient. Among others, this shows that an almost stable matching can be maintained efficiently in a very large network that undergoes frequent changes.
We study a simple Bellman-Ford-like protocol which performs network size estimation over a tree-shaped overlay. A continuous time Markov model is constructed which allows key protocol characteristics to be estimated u...
详细信息
ISBN:
(纸本)9781605588889
We study a simple Bellman-Ford-like protocol which performs network size estimation over a tree-shaped overlay. A continuous time Markov model is constructed which allows key protocol characteristics to be estimated under churn, including the expected number of nodes at a given (perceived) distance to the root and, for each such node, the expected (perceived) size of the subnetwork rooted at that node. We validate the model by simulations, using a range of network sizes, node degrees, and churn-to-protocol rates, with convincing results.
In this paper, we present a framework for achieving anonymity and trust, two seemingly contradictory properties, in distributed systems. Our approach builds on webs of trust, a well-established and widely deployed dec...
详细信息
ISBN:
(纸本)9781605588889
In this paper, we present a framework for achieving anonymity and trust, two seemingly contradictory properties, in distributed systems. Our approach builds on webs of trust, a well-established and widely deployed decentralized infrastructure for establishing the authenticity of the binding between public keys and users, and more generally, trust relationships among users. We introduce the concept of anonymous webs of trust an extension of webs of trust where users can authenticate messages and determine each other's trust level without compromising their anonymity. Our framework comprises novel cryptographic protocols based on zero-knowledge proofs for achieving anonymity in webs of trust and a prototype implementation based on GnuPG. We conduct an automated analysis to formally verify the security of our protocol and an experimental evaluation to demonstrate the effectiveness of our approach.
An edge dominating set for a graph g is a set D of edges such that each edge of g is in D or adjacent to at least one edge in D. this work studies deterministic distributed approximation algorithms for finding minimum...
详细信息
ISBN:
(纸本)9781605588889
An edge dominating set for a graph g is a set D of edges such that each edge of g is in D or adjacent to at least one edge in D. this work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. the focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ... , d. the present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 - 6/(d + 1) for an odd d and to within 4 - 2/d for an even d;and in graphs with maximum degree Delta, to within 4 - 2/(Delta - 1) for an odd Delta and to within 4 - 2/Delta for an even Delta. these approximation ratios are tight for all values of d and Delta: there are matching lower bounds.
We focus on range query processing on large-scale, typically distributed infrastructures. In this work we present the ART (Autonomous Range Tree) structure, which outperforms the most popular decentralized structures,...
详细信息
ISBN:
(纸本)9781605588889
We focus on range query processing on large-scale, typically distributed infrastructures. In this work we present the ART (Autonomous Range Tree) structure, which outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. ART supports the join/leave and range query operations in O(log log N) and O(log(b)(2) log N + vertical bar A vertical bar) expected w.h.p number of hops respectively, where the base b is a double-exponentially power of two, N is the total number of peers and vertical bar A vertical bar the answer size.
In distributed transactional memory (TM) systems, boththe management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. We formalize two classes of cache-coherence protoc...
详细信息
ISBN:
(纸本)9781605588889
In distributed transactional memory (TM) systems, boththe management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. We formalize two classes of cache-coherence protocols: distributed queuing cache-coherence (DQC) protocols and distributed priority queuing cache-coherence (DPQC) protocols, both of which can be implemented based on a given distributed queuing protocol. We analyze the two classes of protocols for a set of dynamically generated transactions and compare their time complexities against that of an optimal offline clairvoyant algorithm. We show that a DQC protocol is O(N log (D) over bar (delta))-competitive and a DPQC protocol is O(log (D) over bar (delta))-competitive for a set of N transactions, where (D) over bar (delta) is the normalized maximum communication latency provided by the underlying distributed queuing protocol.
Consider a distributed network in which events occur at arbitrary nodes and at unpredicted times. An event occurring at node u is sensed only by u which in turn may invoke a communication protocol that allows nodes to...
详细信息
ISBN:
(纸本)9781605588889
Consider a distributed network in which events occur at arbitrary nodes and at unpredicted times. An event occurring at node u is sensed only by u which in turn may invoke a communication protocol that allows nodes to exchange messages withtheir neighbors. We are interested in the following threshold detection (TD) problem inherent to distributedcomputing: Given some threshold k, the goal of a TD protocol is to broadcast a termination signal when at least k events have occurred (throughout the network). In this paper we develop a randomized TD protocol that may fail with negligible probability but which significantly improves previous results in terms of the message complexity, namely, the total number of messages sent by all participating nodes. Withthe right choice of parameters our randomized protocol turns into a deterministic one that guarantees low communication burden for any node. this is a principal complexity measure in many applications of wireless networks and which, to the best of our knowledge, has not been bounded before in the context of such problems.
暂无评论