Nearly All Binary Searches and Mergesorts are Broken

A paper from POPL that we are reading in John's Research group refers to this blog post: Official Google Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Scary and funny at the same time.

The problem occurs with int mid =(low + high) / 2; and statements like it. If low and high are integers, then there is not a problem. Since they are int typed instead, there is a possibility for overflow. An easy solution is to add in a subtraction or do some fancy shifting (see the original Google blog).

John mentions this type of thing a lot. It seems that a lot of formal methods people make assumptions about an int acting like an integer. Software engineers, on the other hand, are painfully aware that the problems normally come because int types do NOT act like integers. This is why there are some many complicated transfer functions in cXprop. The paper we are reading is Types, Bytes and Separation Logic by Harvey Tuch, Gerwin Klein, and Michael Norrish.

Distributed Cognition

I recommended we read a paper on distributed cognition as part of the seminar on ultra-large scale systems. The paper I chose was Distributed Cognition: Toward a New Foundation for Human-Computer Interaction Research by James Hollan, Edwin Hutchins, and David Kirsh (all at UCSD). The paper led to some interesting discussion about human computer interaction (HCI). Eric was particularly excited about it, as it directly relates to the FLUX workbench project, which he is in charge of.

I found the paper to be an interesting and informative read, but I would prefer to read the follow-up paper. The ethnographic studies they highlight emphasize the importance of considering the environment as part of the cognitive process, but they do not actually include multiple people in that environment. They explain how such a study does not exist yet, but that does not make me feel any better. Unfortunately, I have not been able to find a paper which does do this study.

RTSS PhD Student Forum

Yesterday I submitted my proposal to the RTSS PhD Student Forum. I am fairly happy with how my submission turned out.

Apple's mistake?

On the way to work today I listened to the This Week in Tech podcast from last week. A new episode came out yesterday, but I did not plug in my iPod last night. Since I had not listened to any of my podcasts (I rarely do), this one was still available. Anyway, I listened to it and the discussion revolved mostly around Apple and their "announcements" of two weeks ago.

The main debate centered around the $200 price cut in the iPhone. The host tried to see the best in Apple, while the rest seemed to think Apple made a huge mistake. They also talked about why this was a mistake (bad publicity, overshadow new releases, etc). Even though they were disagreeing, I think everybody was making strong and reasonable arguments. I have to say I am in the "apple made a mistake" category, but I agree with the host that the true shame is the overshadowing of their new releases.

In particular, the new iPod nano. Sure, the iPod touch is what is REALLY cool, but the iPod nano puts video in such a small scale and for so cheap! That commercial for it is also strangely addicting and too catchy. The biggest problem I have with the nano is all the choices! Not only do we have to decide which iPod to get, we also have to decide which color. And if we want to surprise someone with a gift, that makes things difficult.

Open-source in ULS systems

In the Ultra-Large-Scale Systems (ULS) seminar we are reading the Carnegie Mellon report which makes a case for ULS systems as a new and legitimate area of research. This seems to be somewhat of a hot topic right now, including a special discussion session at OOPSLA last year and a workshop earlier this year. The fundamental problem with this research is that it involves considering things that most systems computer scientists do not consider (such as the social and economic aspects).

One particularly prevalent consideration is how the open-source movement fits into the models (See the Cathedral and the Bazaar). The semi-altruistic behavior of open-source software development has proven its staying power. However, these ULS systems will be developed by and for the government (at least initially), and will therefore not be open-source in the conventional sense. However, open-source-development-like behavior may be exhibited by competing government contractors.

Also the longevity of ULS systems may necessitate open-source models in order to remain relevant. These systems will take a long time to build, and will take even longer to be replaced. "Many eyes makes all bugs shallow," so open source may be the way to go. However, how does one put automatic driving, a hospital, or the military in the hands of open-source and feel good about it?