| 1. |
- Bailis, P., et al.
(författare)
-
Bolt-on causal consistency
- 2013
-
Ingår i: SIGMOD '13 Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450320375 ; , s. 761-772
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of separating consistency-related safety properties from availability and durability in distributed data stores via the application of a "bolt-on" shim layer that upgrades the safety of an underlying general-purpose data store. This shim provides the same consistency guarantees atop a wide range of widely deployed but often inflexible stores. As causal consistency is one of the strongest consistency models that remain available during system partitions, we develop a shim layer that upgrades eventually consistent stores to provide convergent causal consistency. Accordingly, we leverage widely deployed eventually consistent infrastructure as a common substrate for providing causal guarantees. We describe algorithms and shim implementations that are suitable for a large class of application-level causality relationships and evaluate our techniques using an existing, production-ready data store and with real-world explicit causality relationships.
|
|
| 2. |
- Bailis, P., et al.
(författare)
-
HAT, not CAP : Towards highly available transactions
- 2013
-
Ingår i: 14th Workshop on Hot Topics in Operating Systems, HotOS 2013. - : USENIX Association.
-
Konferensbidrag (refereegranskat)abstract
- While the CAP Theorem is often interpreted to preclude the availability of transactions in a partition-prone environment, we show that highly available systems can provide useful transactional semantics, often matching those of today's ACID databases. We propose Highly Available Transactions (HATs) that are available in the presence of partitions. HATs support many desirable ACID guarantees for arbitrary transactional sequences of read and write operations and permit low-latency operation.
|
|
| 3. |
- Bailis, P., et al.
(författare)
-
The potential dangers of causal consistency and an explicit solution
- 2012
-
Ingår i: Proceedings of the 3rd ACM Symposium on Cloud Computing, SoCC 2012. - New York, NY, USA : ACM. - 9781450317610
-
Konferensbidrag (refereegranskat)abstract
- Causal consistency is the strongest consistency model that is available in the presence of partitions and provides useful semantics for human-facing distributed services. Here, we expose its serious and inherent scalability limitations due to write propagation requirements and traditional dependency tracking mechanisms. As an alternative to classic potential causality, we advocate the use of explicit causality, or application-defined happens-before relations. Explicit causality, a subset of potential causality, tracks only relevant dependencies and reduces several of the potential dangers of causal consistency.
|
|
| 4. |
- Ghodsi, Ali, et al.
(författare)
-
Multi-resource fair queueing for packet processing
- 2012
-
Ingår i: SIGCOMM'12 - Proceedings of the ACM SIGCOMM 2012 Conference Applications, Technologies, Architectures, and Protocols for Computer Communication. - New York, NY, USA : ACM. - 9781450314190 ; , s. 1-12
-
Konferensbidrag (refereegranskat)abstract
- Middleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (e.g., CPU cycles and memory bandwidth). Thus, depending on the functions they go through, different flows can consume different amounts of a middlebox's resources. While there is much literature on weighted fair sharing of link bandwidth to isolate flows, it is unclear how to schedule multiple resources in a middlebox to achieve similar guarantees. In this paper, we analyze several natural packet scheduling algorithms for multiple resources and show that they have undesirable properties. We propose a new algorithm, Dominant Resource Fair Queuing (DRFQ), that retains the attractive properties that fair sharing provides for one resource. In doing so, we generalize the concept of virtual time in classical fair queuing to multi-resource settings. The resulting algorithm is also applicable in other contexts where several resources need to be multiplexed in the time domain.
|
|
| 5. |
- Shafaat, Tallat M., et al.
(författare)
-
A Practical Approach to Network Size Estimation for Structured Overlays
- 2008
-
Ingår i: SELF-ORGANIZING SYSTEMS, PROCEEDINGS. - Berlin : SPRINGER-VERLAG. - 9783540921561 ; , s. 71-83
-
Konferensbidrag (refereegranskat)abstract
- Structured overlay networks have recently received much attention due to their self-* properties under dynamic and decentralized settings. The number of nodes in all overlay fluctuates all the time due to churn. Since knowledge of the size of the. overlay is a core requirement for many systems, estimating the size in a decentralized manner is a challenge taken up by recent research activities. Gossip-based Aggregation has been shown to give accurate estimates for the network size, but previous work done is highly sensitive to node failures. In this paper, we present a gossip-based aggregation-style network size estimation algorithm. We discuss shortcomings of existing aggregation-based size estimation algorithms, and give a solution that is highly robust to node failures and is adaptive to network delays. We examine our solution in various scenarios to demonstrate. its effectiveness.
|
|
| 6. |
- Shafaat, Tallat M., et al.
(författare)
-
Handling network partitions and mergers in structured overlay networks
- 2007
-
Ingår i: P2P. - 9780769529868 ; , s. 132-139
-
Konferensbidrag (refereegranskat)abstract
- Structured overlay networks form a major class of peer-to-peer systems, which are touted for their abilities to scale, tolerate failures, and self-manage. Any long-lived Internet-scale. distributed system is destined to face network partitions. Although the problem of network partitions and mergers is highly related to fault-tolerance and self-management in large-scale systems, it has hardly been studied in the context of structured peer-to-peer systems. These systems have mainly been studied under chum (frequent joins/failures), which as a side effect solves the problem of network partitions, as it is similar to massive node failures. Yet, the crucial aspect of network mergers has been ignored. In fact, it has been claimed that ring-based structured overlay networks, which constitute the majority of the structured overlays, are intrinsically ill-suited for merging rings. In this paper we present an algorithm for merging multiple similar ring-based overlays when the underlying network merges. We examine the solution in dynamic conditions, showing how our solution is resilient to churn during the merger something widely believed to be difficult or impossible. We evaluate the algorithm for various scenarios and show that even when falsely detecting a merger the algorithm quickly terminates and does not clutter the network with many messages. The algorithm is flexible as the tradeoff between message complexity and time complexity can be adjusted by a parameter.
|
|
| 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.
|
|
