Metadata

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

This paper (by Ramalingam and Vaswani) proposes a generic/automatic way to use idempotence---which requires the system to tolerate duplicate requests--- for handling communication and process failures in a software system efficiently. Using idempotence for dealing with process and communication failures has been investigated also in the " Idempotence is not a medical condition ", but there no (generic) solution for achieving idempotence was provided. Automating idempotence For automatically ensuring idempotence for a system, the paper makes use of the monad idea , and designs & implements the idempotence monad. The idea underlying the idempotence monad is simple: "Given a unique identifier associated with a computation, the monad adds logging and checking to each effectful step in the workflow to ensure idempotance". Armed with this idempotence monad, the paper shows that idempotence, when coupled with a simple retry mechanism, provides a solution to t...

Our department moved into a brand-new beautiful building last year. My new office at this building has a nice side-view of the lake, and also a bird-view of the pedestrian crosswalk on the road in front of the building. I spend a good fraction of my time in the office on my makeshift standing desk in front of the window. So I get to watch (from my peripheral vision) the pedestrians crossing the crosswalk. This makes for a surprisingly suspenseful and distracting pastime. It turns out that crossing the crosswalk is not a trivial task, but rather a complex process. Below I talk about the crosswalk scenarios I observed, and how these relate to some fundamental impossibility results in distributed systems. The crosswalk This crosswalk does not have any traffic lights as it is on a low-traffic/in-campus road. According to the crosswalk protocol, the pedestrian has the right-of-way on the crosswalk: the car needs to stop if the pedestrian shows "intent to cross" (which is un...

This is a master's thesis from the CRDT group , presenting the design and implementation of a key-value CRDT store, named SwiftCloud. SwiftCloud extends the Riak Key-Value store in to a Key-CRDT store by incorporating CRDTs in the system's data-model, namely in the value of the key-value tuple. (By the way, Riak---by Basho inc.--- is a NoSQL database implementing the principles from Amazon's Dynamo paper. Enjoy the brief singing of Riak description here!) SwiftCloud achieves automatic conflict resolution relying on properties of CRDTs, and provides strong eventual consistency. (This post will make more sense if you read this first ) SwiftCloud uses state based replication. Strong eventual consistency between replicas is achieved by merging the states of the replicas. SwiftCloud employs versioned CRDTs to support transactions. Transactions never abort due to write/write conflicts, as the system leverages CRDT properties to merge concurrent transactions. The Key-Value...

Below are my notes summarizing the paper "Conflict-free Replicated Data Types" by Marc Shapiro, Nuno Preguica, Carlos Baquero, and Marek Zawirski. The paper is available here. Replicated state machines (RSMs) are a basic and important tool for distributed systems. The idea in RSMs is if the replicas start from the same initial state and perform the same updates with the same order, then their end states are the same. The "strong consistency" approach provides this guarantee by serializing updates to the replicas in a global total order. However, the down side to strong consistency approach is that it is a performance & scalability bottleneck, and it also conflicts with availability and partition-tolerance ( due to the CAP theorem ). Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronization. However, published EC approaches are ad-hoc and error-prone (they come without a formal proof of corrrectness...

In the afternoon of day 2, there were breakout sessions. Below are summaries from the ones that I found useful. There was also an expo on day 2, and my notes on the expo are towards the end of this post. Building web-scale applications with AWS This presentation opened with a customer anectode. As you may know, Reddit runs on AWS. When President Obama did an "Ask Me Anything" on Reddit recently, Reddit called AWS a day in advanced to give heads up. There were 3 million pageviews on Reddit that day, 500K of which was for the President's AMA. Reddit has added 60 dedicated instances and handled the extra traffic smoothly. The presenter gave the takehome message in advance for his talk: While you scale, architect for failure, and architect with security. The rest of the presentation talked about these (mostly the first point) in more detail. Architecting for failure.  AWS has 9 regions around the world, and supports within each region different availability zones (AZ...

In the morning of day 2, we were led into the very large room for the keynote. There were probably 1000-1500 people in the hall, sitting in tight packed formation. Amazon VP & CTO Werner Vogels entered the stage with fanfare (the hall darkened, upbeat music blasting from the speakers). Werner gave a superb, clear, and engaging talk. You can read my notes of it below, or watch the keynote here (around 2 hours long). The AWS summit series kickstarted in NYC, because there is a good tech crowd here, and more importantly many AWS customers are in NYC. AWS summit series this year will be in 13 cities, for which a total of 20K people registered. It is hard to believe that AWS S3 launched only in 2006. There has been amazing progress in 7 years in AWS. Now there are a total of 33 services running, which span compute, storage, database and application management. 100,000 businesses are using AWS This list includes even an extraterrestrial client: NASA JPL is a good customer, ...

I attended AWS summit NYC on Wednesday and Thursday. As an academician, this was a little unconventional conference for me to attend. I regularly attend ACM, IEEE research conferences on focused areas (wireless networks, distributed systems, self-stabilization), but I wanted to go out of my comfort zone to learn about the problems AWS and the AWS ecosystem are working on. Today AWS is leading the cloud computing market, and the AWS infrastructure and platform is an amazing feat of engineering, to say the least. Jeff Bezos, Amazon CEO, has not received a fraction of the genius CEO status alloted to Steve Jobs, but by all accounts Jeff Bezos is not any less deserving. (Read Steve Yegge's platforms rants to see how in 2002 Amazon started an enormous concerted effort for building up its platforms to become what they are today.) I arrived at 2pm on Wednesday to attend the " cloud kata for start-ups ". The name sounds exciting, right? And, they promised powerpoint free pre...

I am offering a seminar/reading class this semester. Below is the list of papers I plan to discuss. If you have some suggestions on other good/recent papers to cover, please let me know in the comments. CRDT related papers: 1. Conflict-free replicated data types 2. Key-CRDT Stores 3. Abstract unordered and ordered trees CRDT 4. CAP 12 years later 5. A Stabilizing Search Tree with Availability Properties 6. Stabilizing Replicated Search Trees WAN replication related papers: 7. Paxos made moderately complex 8. MDCC Multi-Data Center Consistency 9. Mencius: building efficient replicated state machines for Wide-Area-Networks (WANs) 10. Egalitarian Paxos 11. Transactional storage for geo-replicated systems 12. Surviving congestion in geo-distributed storage systems Filesystem papers: 13. Distributed file systems survey 14. File system on CRDT 15. GlusterFS Distributed graph processing papers: 16. Distributed GraphLab: A Framework for Machine Learning and Data Mini...

Ok, our brains are not actually radios, sorry for the provocative title. But as I will explain shortly, there are some interesting parallels. When I teach about wireless radios in my networking classes, I talk about this connection, and this always perks my students up. The connection stems from the fact that both radios and brains are signal processing systems. The concepts behind how radio receivers work explain some of the mysterious phenomena in our brains, particularly the hearing of phantom tunes. This is how radios work Most people have an incorrect model of how radios and wireless radio communication work. The layman thinks radios are simple. The transmitter does all the heavy lifting, and puts the signal on the air. Before the signal fades away completely, if the receiver device is in communication range, it will pick up the signal by listening. This naive understanding suggests that the receiver is a passive dev...