We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that w...
详细信息
ISBN:
(纸本)9781581138023
We determine the weakest failure detectors to solve several fundamental problems in distributed message-passing systems, for all environments - i.e., regardless of the number and timing of crashes. The problems that we consider are: implementing an atomic register, solving consensus, solving quittable consensus (a variant of consensus in which processes have the option to decide 'quit' if a failure occurs), and solving non-blocking atomic commit.
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementati...
详细信息
ISBN:
(纸本)9781581138023
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t
The proceedings contains 31 papers from the proceedings of the twenty-thirdacm SIGMOD-SIGACT-SIGART symposium on principles of Database Systems. The topics discussed include: conditional XPath, the first order comple...
详细信息
The proceedings contains 31 papers from the proceedings of the twenty-thirdacm SIGMOD-SIGACT-SIGART symposium on principles of Database Systems. The topics discussed include: conditional XPath, the first order complete XPath dialect;frontiers for tractability for typechecking simple XML transformations;positive active XML;the past, present and future of web information retrieval;comparing and aggregating rankings with ties and specification and verification of data-driven web services.
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.
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by f...
详细信息
ISBN:
(纸本)9781581138023
We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2,/k) and Ω(Δ1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/ log log n) and Ω(log Δ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] co...
详细信息
ISBN:
(纸本)9781581138023
This paper presents a new algorithm to answer top-k queries (e.g. "find the k objects with the highest aggregate values") in a distributed network. Existing algorithms such as the Threshold Algorithm [10] consume an excessive amount of bandwidth when the number of nodes, m, is high. We propose a new algorithm called "Three-Phase Uniform Threshold" (TPUT). TPUT reduces network bandwidth consumption by pruning away ineligible objects, and terminates in three round-trips regardless of data input. The paper presents two sets of results about TPUT. First, trace-driven simulations show that, depending on the size of the network, TPUT reduces network traffic by one to two orders of magnitude compared to existing algorithms. Second, TPUT is proven to be instance-optimal on common data series. In particular, analysis shows that by using a pruning parameter α
Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove...
详细信息
ISBN:
(纸本)9781581138023
Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce Hag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.
A snapshot is an important object in distributedcomputing whose implementation in asynchronous systems has been studied extensively. It consists of a collection of m > 1 components, each storing a value, and suppo...
详细信息
ISBN:
(纸本)9781581138023
A snapshot is an important object in distributedcomputing whose implementation in asynchronous systems has been studied extensively. It consists of a collection of m > 1 components, each storing a value, and supports two atomic operations: an UPDATE of a specified component's value and a SCAN of all components to determine their values at some point in time. In this paper, we investigate implementations of a multiwriter snapshot object in a synchronous shared memory model. In this setting, we show that a snapshot object can be efficiently implemented and prove a tight tradeoff between the complexity of the SCAN and the UPDATE operations. First, we describe a wait-free implementation that performs UPDATE in O(1) time and SCAN in O(m) time, using only slightly more than twice the amount of space needed to simply store the m values. We also describe a variant that performs UPDATE in O(1) time and SCAN in O(n) time. Second, we describe a wait-free implementation that performs UPDATE in O(log m) time and SCAN in O(1) time, and a variant that performs UPDATE in O(log n) time and SCAN in O(1) time. third, we show how to combine these implementations to realize two implementations that perform UPDATE in θ(log(m/c)) time and SCAN in θ(c) time, for 1 ≤ c ≤ m, or perform UPDATE in θ(log(n/c)) time and SCAN in Θ(c) time, for 1 ≤ c ≤ n. This implies that Time[UPDATE] Ε O( log(min{m, n}/Time[SCAN]) ). We also prove that Time[UPDATE] Ε Ω (log (min {m, n]/Time[SCAN])), which matches our upper bound.
Many lock-free data structures in the literature exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up...
详细信息
ISBN:
(纸本)9781581138023
Many lock-free data structures in the literature exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, "64-bit-clean" lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: load-linked/store-conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software, our implementations also improve on previous ones in that they are space-adaptive and do not require knowledge of the number of threads that will access them.
暂无评论