Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such a...
详细信息
Fault-tolerant broadcast is a fundamental service in distributed systems, by which processes can communicate with each other consistently and reliably. It has two main forms: Reliable Broadcast (RB) and Uniform Reliab...
详细信息
ISBN:
(纸本)9781450336178
Fault-tolerant broadcast is a fundamental service in distributed systems, by which processes can communicate with each other consistently and reliably. It has two main forms: Reliable Broadcast (RB) and Uniform Reliable Broadcast (URB). This service has been extensively investigated in non-anonymous distributed systems where processes have unique identifiers, usually assume the communication channels are reliable, which is not always the case in real systems. In this paper, the fault-tolerant broadcast service is studied in an anonymous asynchronous message passing distributed system model with fair lossy communication channels. Firstly, two simple and non-quiescent algorithms implementing RB and URB are given. Secondly, two new classes of failure detectors A Theta and AP* are proposed. Finally, with the information provided by A Theta and AP*, quiescent algorithms for both RB and URB are given.
In the directed single-source reachability problem, input is a directed graph G = (V,E) and a source s is an element of V, and the objective is to identify nodes t for which there is a directed path in G from s to t. ...
详细信息
ISBN:
(纸本)9781450336178
In the directed single-source reachability problem, input is a directed graph G = (V,E) and a source s is an element of V, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai [2] presented a distributed algorithm that solves this problem in (O) over tilde (D + root nD(1/2)) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that improves the round complexity to (O) over tilde (D + root nD(1/4)), thus getting closer to the (Omega) over tilde (D + root n) lower bound of Das Sarma et al. [1].
We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a (4 Delta)-coloring in O(Delta log n) time slo...
详细信息
ISBN:
(纸本)9781450336178
We present two distributed node coloring algorithms operating in the Signal-to-interference-and-noise-ratio (SINR) model. The first algorithm is very simple and achieves a (4 Delta)-coloring in O(Delta log n) time slots. The results of our experimental evaluation show that the algorithm is extremely fast. Combined with a new color reduction scheme, the algorithm computes a (Delta+1)-coloring in O(Delta log n) time. This improves on current distributed coloring algorithms for the SINR model either in terms of the number of colors or runtime, and matches the asymptotical runtime of one round of local broadcasting, which can be seen as a lower bound.
The history of distributedcomputing is full of trade-offs between safety and liveness. For instance, one of the most celebrated results in the field, namely the impossibility of consensus in an asynchronous system ba...
详细信息
ISBN:
(纸本)9781450336178
The history of distributedcomputing is full of trade-offs between safety and liveness. For instance, one of the most celebrated results in the field, namely the impossibility of consensus in an asynchronous system basically says that we cannot devise an algorithm that deterministically ensures consensus agreement and validity (i.e., safety) on the one hand, and consensus wait-freedom (i.e., liveness) on the other hand. The motivation of this work is to study the extent to which safety and liveness properties inherently exclude each other. More specifically, we ask, given any safety property S, whether we can determine the strongest (resp. weakest) liveness property that can (resp. cannot) be achieved with S. We show that, maybe surprisingly, the answers to these safety-liveness exclusion questions are in general negative. This has several ramifications in various distributedcomputing contexts. In the context of consensus for example, this means that it is impossible to determine the strongest (resp. the weakest) liveness property that can (resp. cannot) be ensured with linearizability. However, we present a way to circumvent these impossibilities and answer positively the safety-liveness question by considering a restricted form of liveness. We consider a definition that gathers generalized forms of obstruction-freedom and lock-freedom while enabling to determine the strongest (resp. weakest) liveness property that can (resp. cannot) be implemented in the context of consensus and transactional memory.
We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects&#...
详细信息
ISBN:
(纸本)9781450336178
We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects' transfer in the network affects the completion time of all transactions and the total communication cost. We show that there are problem instances for which there is no scheduling algorithm that can simultaneously minimize the completion time and communication cost. These instances reveal a trade-off, minimizing execution time implies high communication cost and vice versa. On the positive side, we provide scheduling algorithms which are independently communication cost nearoptimal or execution time efficient.
We introduce the study of the ant colony house-hunting problem from a distributedcomputing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a ne...
详细信息
ISBN:
(纸本)9781450336178
We introduce the study of the ant colony house-hunting problem from a distributedcomputing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributedcomputing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest.
computing students often have difficulty understanding the relevance of the math we teach, though educators appreciate the significance. This BoF will discuss ways to connect this math with what computing students thi...
详细信息
ISBN:
(纸本)9781450336857
computing students often have difficulty understanding the relevance of the math we teach, though educators appreciate the significance. This BoF will discuss ways to connect this math with what computing students think they should be doing: programming. This BoF will focus on the benefits (and perils) of connecting math to the development of correct programs with the goal of motivating the relevance of the math-related portion of the acm/IEEE Computer Society CS2013 curriculum. The discussion will continue the spirit and essence held by the math-thinking working group, a distributed working group of approximately 170 people who have been promoting and clarifying the importance of mathematics in computer science education.
暂无评论