Srikanth Sastry A Techie in Boston

Asynchronous Failure Detectors

My latest work on a modeling framework for a special variant of failure detectors is accepted at the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. A preprint of the submission is available [here].

Update: The full version is available as a tech report [here].

Abstract: Failure detectors — oracles that provide information about process crashes — are an important abstraction for crash tolerance in distributed systems. Although current failure-detector theory provides great generality and expressiveness, it also poses significant challenges in developing a robust hierarchy of failure detectors. We address some of these challenges by proposing a variant of failure detectors called asynchronous failure detectors and an associated modeling framework. Unlike the traditional failure-detector framework, our framework eschews real time completely. We show that asynchronous failure detectors are sufficiently expressive to include several popular failure detectors. Additionally, we show that asynchronous failure detectors satisfy many desirable properties: they are self-implementable, guarantee that stronger asynchronous failure detectors solve more problems, and ensure that their outputs encode no information other than process crashes. We introduce the notion of a failure detector being representative of a problem to capture the idea that some problems encode the same information about process crashes as their weakest failure detectors do. We show that a large class of problems, called finite problems, do not have representative failure detectors.

Failure Detectors Encapsulate Fairness

The full version of my OPODIS 2010 paper “Failure Detectors Encapsulate Fairness” (preprint) has been accepted for publication with the journal Distributed Computing. You can find a preprint of the paper here [pdf].

Abstract: Failure detectors have long been viewed as abstractions for the synchronism present in distributed system models. However, investigations into the exact amount of synchronism encapsulated by a given failure detector have met with limited success. The reason for this is that traditionally, models of partial synchrony are specified with respect to real time, but failure detectors do not encapsulate real time. Instead, we argue that failure detectors encapsulate the fairness in computation and communication. Fairness is a measure of the number of steps executed by one process relative either to the number of steps taken by another process or relative to the duration for which a message is in transit. We argue that failure detectors are substitutable for the fairness properties (rather than real-time properties) of partially synchronous systems. We propose four fairness-based models of partial synchrony and demonstrate that they are, in fact, the ‘weakest system models’ to implement the canonical failure detectors from the Chandra-Toueg hierarchy. We also propose a set of fairness-based models which encapsulate the $Gc$ parametric failure detectors which eventually and permanently suspect crashed processes, and eventually and permanently trust some fixed set of c correct processes.

Tunisia, December 2010

I was in Tunisia in the second week of December in 2010. Just a week before the popular uprising ripped the political system apart and dethroned the dictator Ben Ali. I have tried to capture my visit as a photo essay of Tunisia just before the revolution. The essay is divided into multiple parts: Tunis, Carthage, Sidi Bou Said, photographs from the subsharan desert near Tozeur, the nearby mountain oases, a salt lake, and a visit to the sets of the Phantom Menace.

 

Tunis

The southern entrance to the Tunis Medina

Walking around the medina, the place reminded me so much of India

 

Including Poorly Spelt Signs :-)

 

Some public spaces and buildings were rather beautiful

 

Of course, Ben Ali saved the best for himself. This is as close as I could get to the presidential palace overlooking the Mediterranean.

 

Just so that everyone knows who the boss around is, Ben Ali's photographs were everywhere!

Next, we move to Sidi Bou Said.


Sidi Bou Said

Sidi Bou Said is a beautiful (rich) neighborhood not far from Tunis. The blue and white colors look a lot like the villages in Greece.

 

This point marks the beginning of Sidi Bou Said, and curiously, everything up through this point was relatively dusty and the eat outs where cheap. A few paces to the other side of the street and the entire picture changes.

 

All the houses that I saw there maintained the same color scheme and style.

 

The similarity of the houses is down to the window grills and the lintel over the windows too.

 

The clean streets and relatively expensive cars betrayed the wealth of the residents here.

 

All the streets were really just cobble-stoned pathways. It looked like a quiet village while I was there. Nevertheless beautiful.

 

It is hard to believe that sleepy pathways much like this witnessed a massive uprising against the dictatorship.

 

And for all you cat lovers out here, Sidi Bou Said, and Tunis, in general, is so cat friendly. I saw dozens of them walking about tame and unafraid.

 

Of course, no visit to Tunisia is complete without a visit to the famous Roman baths. So that’s where we head next.

 


The Roman baths were, no doubt, magnificent. But very little of it’s super structure remains.

The beautiful pathway to the ruins gives you an inkling of the magnificence that the people of antiquity enjoyed here.

 

Yet, it can’t prepare you to be awestruck when you actually see the ruins. Although the superstructure is completely gone, you can’t help but admire the opulence of what once was.

 

Hard as you may try, photographs simply don’t do justice to the sight.

 

The underground/basement floors were seldom seen by the patrons of these baths. All the of the basement was for operations that made the hot water, the heated walls, and the steam, possible.

 

And that basement was HUGE. Almost as large as the bath complex above the ground.

 

This is all that remains of the decadent bath complex

 

The amphitheater didn’t fare any better either.

 

The Roman villas have met the same fate, and curiously, these ruins overlook the president’s palace.

 

But overlooking these ruins, is a magnificent mosque. Obviously. It’s an Islamic country after all!

 

From Tunis, my visit took me to Tozeur, a desert village in southern Tunisia.

 


Tozeur

There isn’t much in Tozeur itself. But it is a great starting place for visiting some beautiful locations including  the salt lake Chott el-Jerid, a few mountain oases including Chebika, and of course, the set of the Star Wars movie The Phantom Menace.

 

Chott el-Jerid

We were told that the sunrise over the salt lake is beautiful, so we got there just in time before the sun rose.

 

And saw this. In fact, it was the most beautiful just before the sunrise.

 

But the sunrise was pretty too.

 

Of course, we took some time to smell the salt.

 

And yes, there was some salt there… In fact, lots of it!

 

But life is tenacious, and manages to find a way to survive even in such harsh, saline conditions. Mind you, the lake dries up to become a salt bed in the summer.

 

And then I saw this! Who in their right mind thought it smart to place a bus in the middle of a salt lake?!?

Anyway, moving on… next, we come to the mountain oasis Chebika.

 


 

Chebika

We had to drive 30 minutes or so into the Saharan desert to get to Chebika.

 

What we found was that a stream of this size….

 

…feeds an Oasis this large!

A tribe owns the whole oasis and divides it among its people. And this, I assume is their mascot or some sort of identity symbol. Though I could be completely wrong.

 

There is evidence of some massive tectonic activity in this region, which could well have thrown up…

 

Lots of fossils, quartz, and curious looking crystals (such as the desert rose) that the villagers collect, and they make a living off of selling them to tourists like us.

 

From Chebika, we wanted to make it to another oasis, Medis, but it was getting pretty late.

But we did manage to get some breathtaking views in our futile attempt to get to Medis before sundown.

 

It was getting pretty late, but higher up in the mountains, the sun sets later than down there.

 

We almost made it there, but not quite. We were just a couple of miles away. This road leads straight to Algeria, and Medis was just before the international border. But then, we ran out of time.

 

After an unsuccessful drive to Medis, we headed out to the dunes and the nerd in me could not  miss out on what was coming next.

 


The set of Phantom Menace

The set of the movie The Phantom Menace

 

The set was in a remarkably good condition. This place must have a steady stream of tourists. The local people here make their living selling any kind of trinkets that they can. Only they can survive in this harsh landscape.

 

This is the kind of dwelling they live in, in the middle of high desert!

Of course, the desert held other charms as well.

Like this magnificent landscape.

 

And an alien sense of desolation.

 

But alas, like eveything else. This visit too had to come to an end. And thank god it did in the nick of time. I flew out of Tunis on December 19th. The self immolation that triggered the revolution was on December 17th in Sidi Bouzid (not to be confused with Sidi Bou Said).

A successful defense

I successfully defended my dissertation titled “A Prescription For Partial Synchrony” on January 21st, 2011. The dissertation was approved and accepted by the Thesis Office on February 2nd, 2011.

Abstract:

Algorithms in message-passing distributed systems often require partial synchrony to tolerate crash failures. Informally, partial synchrony refers to systems where timing bounds on communication and computation may exist, but the knowledge of such bounds is limited. Traditionally, the foundation for the theory of partial synchrony has been real time: a time base measured by counting events external to the system, like the vibrations of Cesium atoms or piezoelectric crystals.

Unfortunately, algorithms that are correct relative to many real-time based models of partial synchrony may not behave correctly in empirical distributed systems. For example, a set of popular theoretical models, which we call M, assume (eventual) upper bounds on message delay and relative process speeds, regardless of message size and absolute process speeds. Empirical systems with bounded channel capacity and bandwidth cannot realize such assumptions either natively, or through algorithmic constructions. Consequently, empirical deployment of the many M-based algorithms risks anomalous behavior.

As a result, we argue that real time is the wrong basis for such a theory. Instead, the appropriate foundation for partial synchrony is {\em fairness}: a time base measured by counting events internal to the system, like the steps executed by the processes. By way of example, we redefine M* models with fairness-based bounds and provide algorithmic techniques to implement fairness-based M* models on a significant subset of the empirical systems. The proposed techniques use failure detectors — system services that provide hints about process crashes — as intermediaries that preserve the fairness constraints native to empirical systems. In effect, algorithms that are correct in M* models are now proved correct in such empirical systems as well.

Demonstrating our results requires solving three open problems. (1) We propose the first unified mathematical framework based on Timed I/O Automata to specify empirical systems, partially synchronous systems, and algorithms that execute within the aforementioned systems. (2) We show that crash tolerance capabilities of popular distributed systems can be denominated exclusively through fairness constraints. (3) We specify exemplar system models that identify the set of weakest system models to implement popular failure detectors.

I thank my advisors Scott Pike and Jennifer Welch for all their help, support, and guidance.

A copy of my dissertation (in PDF format) can be accessed here.

Proposing a new radio show

I am proposing a new music show on KEOS 89.1FM Community Radio. Below is the proposal I will be submitting to the KEOS mangement team.


  KEOS Show Proposal

Name: Srikanth Sastry Date: August 27, 2008 Show Description: I propose a music show focusing exclusively on Trance music. The show will showcase various sub genres of trance including Progressive Trance, Acid Trance, Psychedelic Trance, Vocal Trance, Ambient Trance, and such. The show will feature artists like ATB, Paul Oakenfold, Paul Van Dyke, Tiesto, Robert Miles, Astral Projection, Buddha Bar, and such. The nature of trance music and the associated culture is such that it favors long sessions of continuous music, so the show will have very few breaks. All the mandated PSAs, promos, and station ID will either be played together so as to provide a longer continuous music session, or will be played over the music (the music will be potted down, of course). Since this makes it difficult to communicate the play-list to the listeners I propose serve the play-list online.


Show Format: It will be a 2 hr. show consisting of ~30-minute sessions of continuous music. Audience: Anyone interested in trance music, or is curious about it. There is a significant minority counter/alternative culture in the B/CS area who listen to trance, house, and ambient music. Unfortunately the airways carry very little music in those genres. I expect this program to fill that void, at least partially. Longevity: Trance is an extremely active music genre. Having developed in the 1990s, it is a relatively new form of music. Despite its nascence Trance DJs are extremely prolific in their creations and several artists release albums every year, not to mention recordings from various trance festivals and jam sessions. Although trance is not very well known in the US, it is extremely popular in Europe and shows no signs of waning down. Fidelity to KEOS Mission: This show will play music from a genre that is chronically and acutely underplayed on all radio stations. Its audience includes a demographic which is severely under-served on the Bryan-College Station airwaves. The show has the potential to attract new listener-ship to KEOS, thus diversifying both the music played on the station, and the people who listen to KEOS. Resources: I have legal copies of all the music that I’d like to play on the air. I need only the resources already available in the On-Air studio for my show. Wireless Internet would be a desirable, but not necessary, resource. Suggested Titles: Trance Texas Corridor; Trance Nocturna; Alchemical Hours; Android Dreams; One Nation Under Trance Possible Time Slots: Monday 11PM-1AM; Tuesday 9-11PM. 11PM-1AM Co-Hosting: Currently, I do not have a co-host, but am open to the idea of having one. My backup, in case I cannot host during some weeks, is Martin Codrington. Start Date: First week of October