| 1. |
- Ghodsi, Ali, 1978-
(författare)
-
Distributed k-ary System: Algorithms for Distributed Hash Tables
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described.
|
|
| 2. |
- Haridi, Seif, et al.
(författare)
-
Enhanced Paxos Commit for Transactions on DHTs
- 2010
-
Ingår i: 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, CCGrid 2010. - 9781424469871 ; , s. 448-454
-
Konferensbidrag (refereegranskat)abstract
- Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.
|
|
| 3. |
- Högqvist, Mikael, et al.
(författare)
-
Using Global Information for Load Balancing in DHTs
- 2008
-
Ingår i: SASOW 2008. - 9780769535531 - 9781424434688 ; , s. 236-241
-
Konferensbidrag (refereegranskat)abstract
- Distributed Hash Tables (DHT) with order-preserving hash functions require load balancing to ensure an even item-load over all nodes. While previous item-balancing algorithms only improve the load imbalance, we argue that due to the cost of moving items, the competing goal of minimizing the used network traffic must be addressed as well. We aim to improve on existing algorithms by augmenting them with approximations of global knowledge, which can be distributed in a DHT with low cost using gossip mechanisms. In this paper we present initial simulation-based results from a decentralized balancing scheme extended with knowledge about the average node load. In addition, we discuss future work including a centralized auction-based algorithm that will be used as a benchmark.
|
|
| 4. |
- Paul, Ruma, 1985-
(författare)
-
Building Distributed Systems for High-Stress Environments using Reversibility and Phase-Awareness
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Large-scale applications for mobile devices and Internet of Things live in stressful real-world environments: they have both continuous faults and bursts of high faults. Typical faults are node crashes, network partitions, and communication delays. In this thesis, we propose a principled approach to build applications that survive in such environments by using the concepts of Reversibility and Phase. A system is Reversible if the set of operations it provides depends on its current stress, and not on the history of the stress. By stress we imply all the potential perturbing effects of the environment on the system, which includes both faults and other nonfunctional properties such as communication delay and bandwidth. Reversibility generalizes standard fault tolerance with nested fault models. When the stress causes the fault rate to go outside one model then it is still inside the scope of the next model. As stress is a global condition that cannot easily be measured by individual nodes, we propose the concept of Phase in order to approximate the set of available operations of the system at each node. Phase is a per-node property, and can be determined with no additional distributed computation. We present two case studies. First, we present a transactional key-value store built on a structured overlay network and we explain how to make it Reversible. Second, we present a distributed collaborative graphic editor built on top of the key-value store, and we explain how to make it Phase-Aware, i.e., it optimizes its behavior according to a real-time observation of phase at each node using a Phase API. This shows the usefulness of Reversibility and Phase-Awareness for building large-scale Internet applications.
|
|
| 5. |
- Reinefeld, Alexander, et al.
(författare)
-
A Scalable, Transactional Data Store for Future Internet Services
- 2009
-
Ingår i: Towards the Future Internet. - 9781607500070 ; , s. 148-159
-
Konferensbidrag (refereegranskat)abstract
- Future Internet services require access to large volumes of dynamically changing data records that are spread across different locations. With thousands or millions of distributed nodes storing the data, node crashes or temporary network failures are normal rather than exceptions and it is therefore important to hide failures from the application. We suggest to use peer-to-peer (P2P) protocols to provide self-management among peers. However, today's P2P protocols are mostly limited to write-once/read-many data sharing. To extend them beyond the typical file sharing, the support of consistent replication and fast transactions is an important yet missing feature. We present Scalaris, a scalable, distributed key-value store. Scalaris is built on a structured overlay network and uses a distributed transaction protocol. As a proof of concept, we implemented a simple Wikipedia clone with Scalaris which outperforms the public Wikipedia with just a few servers.
|
|
| 6. |
- Schwiegelshohn, Uwe, et al.
(författare)
-
Perspectives on grid computing
- 2010
-
Ingår i: Future Generation Computer Systems. - : Elsevier BV. - 0167-739X .- 1872-7115. ; 26:8, s. 1104-1115
-
Tidskriftsartikel (refereegranskat)abstract
- Grid computing has been the subject of many large national and international IT projects. However, not all goals of these projects have been achieved. In particular. the number of users lags behind the initial forecasts laid out by proponents of grid technologies. This underachievement may have led to claims that the grid concept as a whole is on its way to being replaced by Cloud computing and various X-as-a-Service approaches. In this paper, we try to analyze the current situation and to identify promising directions for future grid development. Although there are shortcomings in current grid systems, we are convinced that the concept as a whole remains valid and can benefit from new developments, including Cloud computing. Furthermore, we strongly believe that some future applications will require the grid approach and that, as a result, further research is required in order to turn this concept into reliable, efficient and user-friendly computing platforms. (c) 2010 Elsevier B.V. All rights reserved.
|
|
| 7. |
- Shafaat, Tallat M., et al.
(författare)
-
Key-based consistency and availability in structured Overlay Networks
- 2008
-
Ingår i: Proceedings of the 17th International Symposium on High Performance Distributed Computing 2008, HPDC'08. - New York, NY, USA : ACM. - 9781595939975 ; , s. 235-236
-
Konferensbidrag (refereegranskat)abstract
- Structured Overlay Networks (SONs) provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. SONs provide lookup services that map keys to nodes that can be used as processing or storage resources. In SONs, lookups for a key may return inconsistent results. Consequently, it is difficult to provide consistent data services on top of SONs that build on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the affect of lookup inconsistencies can be reduced by using node responsibilities. We present our results as a trade-off between consistency and availability of keys.
|
|
| 8. |
- Shafaat, Tallat M., et al.
(författare)
-
On consistency of data in structured overlay networks
- 2008
-
Ingår i: GRID COMPUTING. - NEW YORK : SPRINGER. - 9780387094564 ; , s. 249-260
-
Konferensbidrag (refereegranskat)abstract
- Data consistency can be violated in Distributed Hash Tables (DHTs) due to inconsistent lookups. In this paper, we identify the events leading to inconsistent lookups and inconsistent responsibilities for a key. We find the inaccuracy of failure detectors as the main reason for inconsistencies. By simulations with inaccurate failure detectors, we study the probability of reaching a system configuration which may lead to inconsistent data. We analyze majority-based algorithms for operations on replicated data. To ensure that concurrent operations do not violate consistency, they have to use non-disjoint sets of replicas. We analytically derive the probability of concurrent operations including disjoint replica sets. By combining the simulation and analytical results, we show that the probability for a violation of data consistency is negligibly low for majority-based algorithms in DHTs.
|
|
| 9. |
- van Roy, Peter, et al.
(författare)
-
Self Management of Large-Scale Distributed Systems by Combining Structured Overlay Networks and Components
- 2005. - 1
-
Konferensbidrag (refereegranskat)abstract
- This position paper envisions making large-scale distributed applications self managing by combining component models and structured overlay networks. A key obstacle to deploying large-scale applications running on Internet is the amount of management they require. Often these applications demand specialized personnel for their maintenance. Making applications self-managing will help removing this obstacle. Basing the system on a structured overlay network will allow extending the abilities of existing component models to large-scale distributed systems. Structured overlay networks provide guarantees for efficient communication, e±cient load-balancing, and self-manage in case of joins, leaves, and failures. Component models, on the other hand, support dynamic configuration, the ability of part of the system to reconfigure other parts at run-time. By combining overlay networks with component models we achieve both low-level as well as high-level self-management. We will target multi-tier applications, and specifically we will consider three-tier applications using a self-managing storage service.
|
|
