Metadata

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 paper I like to physically touch the paper and handwrite and doodle on the paper. I have highlighter and different color pens read...

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 t...

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 l...

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 a...

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, a...

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 ...

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 envir...

Last week I was in Boston to attend International conference on Parallel and Distributed Processing Systems (IPDPS) , and I will post some of my notes from this conference here. Coincidentally, Distributed Computing in Sensor Systems (DCOSS) was also being held at Boston at the same dates with IPDPS, and I could only reserve my room at the DCOSS hotel instead of the IPDPS hotel. Since the DCOSS keynote on mobile sensing by Hari Balakrishnan sounded more interesting to me than the IPDPS first day keynote, I decided to sneak in to the DCOSS room and attend that keynote instead. Hari's talk had two parts. He spent most of his time on the first part, and had to rush through the second part. How can sensors improve networks? The crossover happened this year: smartphone & tablets accessing the Internet overtook PCs & laptops accessing the Internet. Smartphone adoption rate is 7 times the rate of growth of world population, and there are more people using smartphones than pe...

This paper, which appeared in NSDI 2013 , describes the evolution of Facebook’s memcached-based architecture. Memcached is an open-source implementation of a distributed in-memory hash table over a cluster of computers, and it is used for providing low latency access to a shared storage pool at low cost. Memcached was first developed by Brad Fitzpatrick in 2003. Memcached at Facebook targets a workload dominated by reads (which are two orders of magnitude more frequent than writes). Facebook needs to support a very heavy read load, over 1 billion reads/second, and needs to insulate backend services from high read rates with very high fan-out . To this end, Facebook uses memcache as a "demand-filled look-aside cache". When a web server needs data, it first requests the value from memcache by providing a string key. If it is a cache hit, great, the read operation is served. If the item addressed by that key is not cached, the web server retrieves the data from the backend da...

I have been using the pomodoro technique for a couple years  to improve my productivity. Pomodoro is a timer (of 20 minutes) during which you commit to do a task. After this task timer there is a short break, after which the next task timer starts again. The pomodoro technique is described here in detail . I like pomodoro as it helps me to concentrate and get things done.  It also helps me to get started on something I detest doing: Surely I can endure doing that thing for 20 minutes, right? This helps trick myself to break my inertia and usually I find that I can keep going for multiple pomodoros on that task. I use the Pomodoro Desktop app (by Ugo Landini) for Mac OS X, and configure it to use 20 minutes as the task timer and 10 minutes as the break timer. I modified it to disable my laptop wifi at the start of the task timer and enable it back at the end of the task timer. For this I added  do shell script "networksetup -setairportpower en0 off"  to the pomod...

I had mentioned about Fatih Bulut, one of my PhD students, when writing about his crowdsourced line wait-time forecasting project . Fatih has recently been working on an energy-efficient proximity alert service for Android, and published his preliminary work in  M. F. Bulut, M. Demirbas. Energy Efficient Proximity Alert on Android. IEEE Workshop on Pervasive Collaboration and Social Networking, 2013 . The abstract from that paper reads: The proximity alert service on Android is important as an enabler of ubiquitous location-based services, however, it is also limited in this role due to its excessive energy expenditure. In this paper, we present the design and implementation of an energy-efficient proximity alert service for Android. Our method utilizes the distance to the point of interest and the user’s transportation mode in order to dynamically determine the location-sensing interval and the location providers (GPS, GSM, or Wi-Fi) to be used . We implement our method as a...

My advice to you has 4 parts: Publish or perish, Work hard, Understand the philosophy of research, and Manage your time well. (A nice complement to this post is my advice to my undergraduate students .) PUBLISH OR PERISH Be goal-oriented Always know the criteria needed for the next step, and focus on addressing these criteria. Your next step after PhD is, ideally, to get a faculty job. And this requires you to have both good quality and quantity of publications. Aim to have 10 publications, half of them at top conferences. So publish or perish. 4.0 GPA is not your goal. Taking a lot of classes is not your goal. Get your first paper out very fast This will give you the confidence to write other papers. This will teach you that research is not an exotic thing that only professors do. This will shave off couple of years from your PhD. Your first paper does not need to be very good. Get it out fast. Write well, write a lot, revise a lot Writing clearly and communica...