mpm + coordination   13

Efficient, Consistent Distributed Computation with Predictive Treaties
To achieve good performance, modern applications often par-tition their state across multiple geographically distributednodes. While this approach reduces latency in the commoncase, it can be challenging for programmers to use correctly,especially in applications that require strong consistency. Weintroducepredictive treaties, a mechanism that can signifi-cantly reduce distributed coordination without losing strongconsistency. The central insight behind our approach is thatmany computations can be expressed in terms of predicatesover distributed state that can be partitioned and enforcedlocally. Predictive treaties improve on previous work by al-lowing the locally enforced predicates to depend on time.Intuitively, by predicting the evolution of system state, coor-dination can be significantly reduced compared to static ap-proaches. We implemented predictive treaties in a distributedsystem that exposes them in an intuitive programming model.We evaluate performance on several benchmarks, includingTPC-C, showing that predictive treaties can significantly in-crease performance by orders of magnitude and can evenoutperform customized algorithms.
consistency  performance  coordination 
9 weeks ago by mpm
A.M.B.R.O.S.I.A: Providing Performant Virtual Resiliency for Distributed Applications
When writing today’s distributed programs, which frequently span both devices and cloud services, programmers are faced with complex decisions and coding tasks around coping with failure, especially when these distributed components are stateful. If their application can be cast as pure data processing, they benefit from the past 40-50 years of work from the database community, which has shown how declarative database systems can completely isolate the developer from the possibility of failure in a performant manner. Unfortunately, while there have been some attempts at bringing similar functionality into the more general distributed programming space, frequently called “exactly once execution”, a compelling general-purpose system must be performant, support a variety of machine types with varying resiliency goals, and be language agnostic, allowing distributed components written in different languages to communicate. This paper introduces the first system, Ambrosia, to satisfy all these requirements. We coin the term “virtual resiliency”, analogous to virtual memory, for the fundamental mechanisms (already present in data processing systems for decades) that allow programmers to write their applications in a failure oblivious way. Of interest to our community is the effective reapplication of much database performance optimization technology to make Ambrosia more performant than many of today’s non-resilient cloud solutions.
december 2018 by mpm
DottedDB: Anti-Entorpy without Merkle Trees, Deletes without Tombstones
To achieve high availability in the face of network partitions, many distributed databases adopt eventual consistency, allow temporary conflicts due to concurrent writes, and use some form of per-key logical clock to detect and resolve such conflicts. Furthermore, nodes synchronize periodically to ensure replica convergence in a process called anti-entropy, normally using Merkle Trees. We present the design of DottedDB, a Dynamo-like key-value store, which uses a novel nodewide logical clock framework, overcoming three fundamental limitations of the state of the art: (1) minimize the metadata per key necessary to track causality, avoiding its growth even in the face of node churn; (2) correctly and durably delete keys, with no need for tombstones; (3) offer a lightweight antientropy mechanism to converge replicated data, avoiding the need for Merkle Trees. We evaluate DottedDB against MerkleDB, an otherwise identical database, but using per-key logical clocks and Merkle Trees for anti-entropy, to precisely measure the impact of the novel approach. Results show that: causality metadata per object always converges rapidly to only one id-counter pair; distributed deletes are correctly achieved without global coordination and with constant metadata; divergent nodes are synchronized faster, with less memory-footprint and with less communication overhead than using Merkle Trees.
database  coordination  consistency 
august 2017 by mpm
An Autonomous and Dynamic Coordination and Discovery Service for Wide-Area Peer-to-peer Publish/Subscribe
Industrial Internet of Things (IIoT) applications are mission-critical, which require a scalable data sharing and dissemination platform that supports quality of service (QoS) properties such as timeliness, resilience, and security. Although the Object Management Group (OMG)'s Data Distribution Service (DDS), which is a data-centric, peer-to-peer publish/subscribe standard supporting multiple QoS properties, is well-suited to meet the requirements of IIoT applications, its design and current technology limitations constrains its use to local area networks only. Moreover, although broker-based bridging services exist to inter-connect isolated DDS networks, these solutions lack autonomous and dynamic coordination and discovery capabilities that are needed to bridge multiple, isolated networks on demand. To address these limitations, and enable a practical and readily deployable solution for IIoT, this paper presents and empirically validates PubSubCoord, which is an autonomous, coordination and discovery service for DDS endpoints operating over wide area networks.
discovery  pubsub  coordination 
july 2017 by mpm
Efficient Distributed Coordination at WAN-Scale
Traditional coordination services for distributed applications do not scale well over wide-area networks (WAN): centralized coordination fails to scale with respect to the increasing distances in the WAN, and distributed coordination fails to scale with respect to the number of nodes involved. We argue that it is possible to achieve scalability over WAN using a hierarchical coordination architecture and a smart token migration mechanism, and lay down the foundation of a novel design for a flexible-consistent coordination framework, called WanKeeper. We implemented WanKeeper based on the ZooKeeper API and deployed it over WAN as a proof of concept. Our experimental results based on the Yahoo! Cloud Serving Benchmark (YCSB), Apache BookKeeper replicated log service, and the Shared Cloud-backed File System (SCFS) show that WanKeeper provides multiple folds improvement in write/update performance in WAN compared to ZooKeeper, while keeping the same read performance.
coordination  scalability 
july 2017 by mpm
DepSpace (Dependable Tuple Space) is fault and intrusion-tolerant secure tuple space implementation
tuplespace  coordination 
may 2015 by mpm
Estensible Distributed Coordination
Most services inside a data center are distributed systems requiring coordination and synchronization in the form of primitives like distributed locks and message queues. We argue that extensibility is a crucial feature of the coordination infrastructures used in these systems. Without the ability to extend the functionality of coordination services, applications might end up using sub-optimal coordination algorithms, possibly leading to low performance. Adding extensibility, however, requires mechanisms that constrain extensions to be able to make reasonable security and performance guarantees. We propose a scheme that enables extensions to be introduced and removed dynamically in a secure way. To avoid performance overheads due to poorly designed extensions, it constrains the access of extensions to resources. Evaluation results for extensible versions of ZooKeeper and DepSpace show that it is possible to increase the throughput of a distributed queue by more than an order of magnitude (17x for ZooKeeper, 24x for DepSpace) while keeping the underlying coordination kernel small
consensus  coordination 
may 2015 by mpm
A Practical Distributed Universal Construction with Unknown Participants
Modern distributed systems employ atomic read-modify-write primitives to coordinate concurrent operations. Such primitives are typically built on top of a central server, or rely on an agreement protocol. Both approaches provide a universal construction, that is, a general mechanism to construct atomic and responsive objects. These two techniques are however known to be inherently costly. As a consequence, they may result in bottlenecks in applications using them for coordination. In this paper, we investigate another direction to implement a universal construction. Our idea is to delegate the implementation of the universal construction to the clients, and solely implement a distributed shared atomic memory at the servers side. The construction we propose is obstruction-free. It can be implemented in a purely asynchronous manner, and it does not assume the knowledge of the participants. It is built on top of grafarius and racing objects, two novel shared abstractions that we introduce in detail. To assess the benefits of our approach, we present a prototype implementation on top of the Cassandra data store, and compare it empirically to the Zookeeper coordination service.
june 2014 by mpm
ZooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services. All of these kinds of services are used in some form or another by distributed applications. Essentially Noah, is a port of those concepts into a stateless RESTful application.
zookeeper  distributed  coordination 
may 2011 by mpm
Doozer is a highly-available, completely consistent store for small amounts of extremely important data. When the data changes, it can notify connected clients immediately (no polling), making it ideal for infrequently-updated data for which clients want real-time updates. Doozer is good for name service, database master elections, and configuration data shared between several machines
distributed  coordination  consistency  consensus  availability  go 
april 2011 by mpm
riak_zab is an extension for riak_core that provides totally ordered atomic broadcast capabilities. This is accomplished through a pure Erlang implementation of Zab, the Zookeeper Atomic Broadcast protocol invented by Yahoo! Research
erlang  coordination  consistency  consensus  leader-election 
april 2011 by mpm
Understanding and Applying Operational Transformation
The key to Wave is the mechanism by which we interact with these documents: operational transformation. Wave actually doesn’t allow you to get access to a document as raw XML or anything even approaching it. Instead, it demands that all of your access to the document be performed in terms of operations. This has two consequences: first, it allows for some really incredible collaborative tools like the Wave client; second, it makes it really tricky to implement any sort of Wave-compatible service
algorithm  coordination 
may 2010 by mpm
Reo Coordination Language
Reo presents a paradigm for composition of distributed software components and services based on the notion of mobile channels. Reo enforces an exogenous channel-based coordination model that defines how designers can build complex coordinators, called connectors, out of simpler ones. Application designers can use Reo as a "glue code" language for compositional construction of connectors that orchestrate the cooperative behavior of instances of components or services in a component-based system or a service-oriented application.
distributed  coordination 
september 2009 by mpm

Copy this bookmark: