## Posts

Showing posts from 2013

### Research is a capricious mistress

Research is a capricious mistress. You should be totally devoted to it, and you should be thinking about it all the time. Otherwise, it won't divulge its secrets to you.

Research has this nonlinear return on investment (ROI) function. It awards persistence and dedication by folds and punishes apathy and laziness severely.

If you give research your 100%, you will get at least 200% ROI back. Eventually, that is. It will first test you to see if you are worthy, if you really mean it, if you really have it in you. You will get several setbacks, false alarms. Yet, if you persist and overcome the failures, it will start giving back to you by folds.

If you give research your 50% you will get 20% back. You won't make the cut, and you will be operating a business with deficiency. Usually someone else (the university that employs you) pays the tab.

So what does giving 100% mean? It doesn't mean working overtime (sometimes that will be needed, and you will be doing it though). The pr…

### My notes from SOSP13 welcome and awards

The ACM Symposium on Operating Systems Principles (SOSP) is arguably the top conference in the computer systems area. The SOSP conference took a start with a welcome talk from the General Chair, Michael Kaminsky (Intel Labs), and PC Chair, Mike Dahlin (Google and UT Austin).

The chairs started by thanking to the many sponsors (platinum, gold, silver, bronze level) for the conference.

This year SOSP had 628 registrations, which made it the biggest SOSP as of yet, with a 16% increase over 2011 SOSP (which was yet biggest till then). Attendance distribution to SOSP is 76% from North America, 15% Europe, and 11% Asia. Among those attending 42% is faculty, 42% students, and 15% industry. There were 7 workshops on the weekend preceding the SOSP (LADIS was one of them), and 40% of attendants also attended workshops.

This year, for the first time, SOSP had full open access conference proceedings (the cost, $1100 per paper has been paid by SIGOPS), and this announcement got a huge applause fro… ### LADIS 2013 keynotes I attended and presented a paper at LADIS 2013, which was colocated with SOSP13. I will talk about my paper in a later post. Here I just want to share brief summaries of the LADIS keynotes. 1. LADIS keynote: Cloud-scale Operational Excellence, by Peter Vosshall, distinguished engineer What is operational excellence? It is anticipating and addressing problems. For us, operational excellence arises from a combination of culture + tools + processes. 1.1 Culture Amazon leadership principles are: Customer obsession Ownership (Amazon has a strong ownership culture, known as devops!) Insisting on the highest standards 1.2 Tools Amazon has tools for software deployment, monitoring, visualization, ticketing, risk auditing. In 1995, Amazon had a single web-server operation, and had a website-push perl script. This was managed by a small centralized team, named Houston. The team invested in a tool called Apollo for automating deployments. As a result, it was easy to do deployments. Some 2… ### Beyond TrueTime: Using AugmentedTime for Improving Google Spanner ### How I write Writing is easy. All you do is sit staring at the blank sheet of paper until the drops of blood form on your forehead. -- Red Smith Let's get this cleared first. Writing is hard. Whoever says it is easy is lying. There is a lovely book by Sophy Burnham called "For Writers Only" which includes countless quotes from writers on the exquisite pain of the writing life. I highly recommend the book. All the quotations in this post are taken from that book. I see but one rule: to be clear. -- Stendhal Of course, I am not going to talk about how to write great works of literature. For that I am unqualified. I will talk about technical/scientific writing, which is a bit easier and manageable. For technical writing you do not necessarily need to be creative, playful, and poetic. You just have to communicate your points clearly. (Unfortunately, this is easier said than done.) We do not write in order to be understood, we write in order to understand. -- C. Day-Lewis Writing is very… ### How I read a research paper I can't tell you how you should read a research paper. Probably a different and customized style would work best for you. But I can tell you how I read a research paper. And if you think some of the things below make sense, you can try them for yourself and see if they work for you as well. So, how do I read a paper? The first answer that pops to my mind is "I fight with it". I strive to completely understand and "Grok" the paper by arguing with it. I resist to believe the claims in the paper at face value, I try to poke holes at it. I believe that the paper has to earn my trust, and I only accept the parts that I am obliged to accept. My algorithm for reading a paper 0. Print the paper 1. Ask questions and argue with the paper 2. Write a review 3. Fight with the paper 4. Sleep on it and come back to it Print the paperI like to physically touch the paper and handwrite and doodle on the paper. I have highlighter and different color pens ready with me, when I am… ### Apps are selfish parasites! How can we get truly collaborative apps on smartphones? While there has been good progress and wide availability of the devices (smartphones, tablets, sensors) to fulfill the ubiquitous computing vision, the-state-of-the-art in software and integration is lagging far behind. Consider DARPA's 2009 network grand challenge on the occasion of the 40th anniversary of the Internet. The challenge was to accurately find 10 weather balloons deployed in arbitrary locations of the U.S. within a day. There was an award of$40,000 for the team that would first report the locations of the 10 balloons accurately, and this challenge was solved within 9 hours. The winning team employed social networks and a multilevel incentive structure, but had to prepare, campaign, and publicize aggressively for an entire month before the challenge day.

This points to a big gap between the potential of the smartphones and the reality of the smartphone software today. Why are the existing apps so limited and person-centric? Why can we not have an app that is able to …

### Ramblings on serializability

Here is a very raw/immature idea I have been toying with recently. I decided to write it down and share in order to get feedback about whether this is worth exploring further.

Serializability Serializability of reads and writes (sequential consistency) is an important feature in distributed systems. A significant application of serializability is in transaction processing in distributed databases (e.g., Spanner).

Paxos serialization versus serializability Paxos is a method for fault-tolerant state machine replication. In order to achieve fault-tolerant state machine replication, Paxos employs consensus to serialize operations at a leader and apply the operations at each replica in this exact serialized order (dictated by the leader).

While serialization is not an end in Paxos but rather a means, Paxos is seen nowadays as a defacto method for serialization rather than a method for fault-tolerant state machine replication. Maybe the ZooKeeper implementation of a Paxos-based lock-service…

The Spanner paper by Google (appeared in OSDI'12) is cryptic and hard to understand. When I first read it, I thought I understood the main idea, and that the benefit of TrueTime was to enable lock-free read-only transactions in Spanner. Then, I slowly realized things didn't check; it was possible to achieve lock-free read-only transactions without TrueTime as well. I did another read, and thought for some time, and had a better understanding of how TrueTime benefits Spanner, and how to improve its shortcomings.

I will first provide a summary of the Spanner work (borrowing sentences and figures from the Spanner paper), and then talk about what TrueTime is actually good for.

In a nutshell Spanner is Google's scalable, multi-version, globally-distributed, and synchronously-replicated database. Spanner supports non-blocking reads in the past, lock-free read-only transactions, and atomic schema changes. In order to support externally-consistent distributed transactions at glo…

### Antifragility from an engineering perspective

I read Nassim Taleb's "Antifragility: Things That Gain from Disorder" book a while ago, and enjoyed it a lot. I have been thinking about antifragility in engineering systems, and thought it would be good to put what I have come up with so far in writing to be able to contribute to the discussion. There are some nice reviews of the book in various places. My intention here is not to review the book, but to try to look at antifragility from an engineering perspective. Unfortunately, this came out mostly as rambling, but here it is for what it is worth.

Engineered systems:  Let's start with giving examples from the mechanical world. I will try to give examples for three increasingly-superior levels of reliability: robust-yet-fragile < resilient < antifragile.

Robust-yet-fragile. A good example here is the glass. Glass (think of automobile glasses or gorilla glass) is actually very tough/robust material. You can throw pebbles, and even bigger rocks at it, and it won…

### RAMCloud reloaded: Log-structured Memory for DRAM-based Storage

I had written a review about "the case for RAMCloud" paper in 2010.  RAMCloud advocates storing all the data in the RAM over distributed nodes in a datacenter. A RAMCloud is not a cache like memcached and data is not stored on an I/O device; DRAM is the permanent home for data.  Obviously, storing everything in RAM could yield a very high-throughput (100-1000x) and very low-latency (100-1000x) system compared to disk-based systems.

In the last 3 years, the RAMCloud group headed by John Ousterhout at Stanford has done significant work on this project, and this is a good time to write another review on RAMCloud. My review mostly uses (shortened) text form their papers, and focuses on some of the significant ideas in their work.

State of the RAMCloud
Data model. RAMCloud provides a simple key-value data model consisting of uninterpreted data blobs called objects. Objects are grouped into tables that may span one or more servers in the cluster; a subset of a table stored on a si…

### IPDPS'13 day1 graph algorithms

Here are some of my notes from the first day of IPDPS.

Optimizations & analysis of BSP graph processing models on public clouds Mapreduce/Hadoop is not very suitable for graph processing (which requires iterating over and over on the same graph), and this led to the Pregel graph processing framework by Google. Pregel is based on the Bulk Synchronous Parallelism (BSP) model. Here is a summary of Pregel if you are not familiar with it. In short, Pregel uses a vertex-centric graph processing model, where the same code is executed on all vertices concurrently. Pregel uses message passing along edges and barrier synchronization at supersteps (i.e., rounds) to iterate over the graph. This paper looks at optimizations and analysis of BSP graph processing frameworks.

This group had access to Microsoft Azure cloud computing framework, and they wanted to experiment with Pregel there, so they implemented Pregel (following the description in the Pregel paper) from scratch in .NET environment.…