Conventional distributed systems wisdom is to treat slow nodes the same as failed nodes, through the use of leases and timeouts, handling merely slow nodes by effectively rebooting or restarting them.

While this wisdom has led to simpler systems that can effectively handle high churn while also continuing to function in the face of high network delays, it is ill suited to more modern managed environments, where many processes are co-located in a small geographic region such as a campus or data center. In these environments, delays are commonly just that—delays. Moreover, a failed process is likely to be restarted quite quickly, so that if state is effectively maintained, it need not be erased as it would by conventional wisdom.

In our paper, we propose that conventional wisdom be rebooted for managed distributed systems: that we should instead treat failed nodes as slow nodes, allowing the system to more gracefully handle common scenarios such as power failures.

We present Ken protocol, a lightweight distributed reliability model that is well suited to developing highly-survivable applications for these environments and allows the developer to focus on the crash-free behavior of applications.

We also demonstrate how this model can be effortlessly integrated with Mace toolkits for building large-scale distributed systems, yielding MaceKen, to support survivable application development. Moreover, this model allows multiple, independently developed application components to be seamlessly composed, preserving the reliability benefits across systems.

Our work will be released as an open source in soon. Stay tuned.

Sunghwan Yoo, Charles Killian, Terence Kelly, Hyoun Kyu Cho, and Steven Plite.  Composable Reliability for Asynchronous Systems: Treating Failures as Slow Processes, In proceedings of 2012 USENIX Annual Technical Conference (USENIX ATC ’12). Boston, MA. (to appear) 13-15 June, 2012.  

Most distributed systems are designed to meet application-prescribed metrics that ensure availability and high-performance for practical usage. However compromised participants can manipulate protocol semantics through attacks that target the messages exchanged with honest nodes and degrade performance significantly. To date, finding attacks against performance has been primarily a manual task due to both the difficulty of expressing performance as an invariant in the system and the state-space explosion that occurs as attackers are more realistically modeled. Our design goal is to find performance attacks automatically requiring the least amount of user effort.

In our paper, we propose Gatling, a framework that automatically finds performance attacks caused by insider attackers in large-scale message-passing distributed systems. We define performance attacks as following; malicious nodes deviate from the protocol when sending or creating messages, with the goal of degrading system performance. Gatling is a framework that combines a model checker and simulator environment with a fault injector to find performance attacks in event-based message passing distributed systems. Continue reading →

The event-driven model is a popular framework for those who want to build a complex distributed application while keeping the simple event-driven system features where the lower details can be hidden.

However, introducing parallelism in the event-driven system has not been an easy task since it has to solve the concurrency problem between various events sharing state variables.

Assume that we have two events, event_a() and event_b() as follows.

state_variable v; event_a() { read(v); write(v, 1); } event_b() { read(v); // do something read(v); }

What happens when we run those two events in parallel? write(v,1) statement in event_a() can occur between the two read(v) statements in event_b(). This concurrent access will violate programmer expectations.

The simplest way to overcome this issue is not allowing parallelism at all. This is called the atomic event model, which Mace has used since its creation due to its simplicity.

However, what if we have a service that has a recurring event to be handled in timely manner? One good example is a heartbeat(ping) message to check the liveness of each node. If we have a event that takes a long time to complete, the heartbeat message may not be processed in time while the long-running event is handled.

The ideal solution (as suggested in InContext model) is allowing parallelism in a service so that each event can be handled separately in different threads. This will increase the responsiveness of the system that has a background service like ping messages to check liveness.

The problem is to how to deal with concurrent access to shared variables. How can we safely run the multiple events in parallel without breaking concurrency? Of course we can take another approach like SEDA by calling other methods by queuing events to be processed. However, one cannot simply parallelize their events with SEDA and it may require a lot of restructuring work on existing system. Is there a simpler algorithm?

InContext provides a solution for those who seek parallelism in event driven system while keeping simplicity. Continue reading →

Performance is one of the later but important component in building efficient Distributed systems. Precise performance guarantees are essential for high throughput and time sensitive distributed applications, and hence developers have to chase performance. Most of the time, performance problems are uncovered in non-ideal conditions (such as delayed or dropped packets, node failures, network partitions, etc.) making it hard to identify problems especially in complex interleaved distributed executions. Moreover, common development approaches adopt periodic recovery mechanisms that eventually bring protocol correctness and node consistency. But this strategy is detrimental to performance debugging as it conceals the inability (of the protocol) to attain consistency in their absence. We refer to such problems as latent performance anomalies, which have serious design and implementation problems with big implications to responsiveness, availability and end-to-end behavior of the system.

In our FSE paper, we present MacePC – that automates the discovery of latent performance problems in distributed systems through a systematic analysis of the system. Broadly, MacePC first identifies representative execution performance of the distributed system, following which it sets out to explore the state space to identify executions that lead to anomalous run times. Any sequence of events that leads to a very large (or small) run time is flagged for developer inspection, along with a point in the execution that led to the bad performance. We implemented MacePC over Mace and evaluated it across 5 mature implementations of popular distributed protocols. In this exercise, we identified (previously unknown) bugs in the protocol/implementation that cause poor performance. Continue reading →