Wyłowione z czytnika

This is how I feel about buying apps

2010-08-30T13:19:03Z

Lessons from Google Wave and REST vs. SOAP: Fighting Complexity of our own Choosing

2010-08-27T14:30:17Z

Software companies love hiring people that like solving hard technical problems. On the surface this seems like a good idea, unfortunately it can lead to situations where you have people building a product where they focus more on the interesting technical challenges they can solve as opposed to whether their product is actually solving problems for their customers.

I started being reminded of this after reading an answer to a question on Quora about the difference between working at Google versus Facebook where ~~Edmond Lau~~ David Braginsky wrote

Culture:
Google is like grad-school. People value working on hard problems, and doing them right. Things are pretty polished, the code is usually solid, and the systems are designed for scale from the very beginning. There are many experts around and review processes set up for systems designs.

Facebook is more like undergrad. Something needs to be done, and people do it. Most of the time they don't read the literature on the subject, or consult experts about the "right way" to do it, they just sit down, write the code, and make things work. Sometimes the way they do it is naive, and a lot of time it may cause bugs or break as it goes into production. And when that happens, they fix their problems, replace bottlenecks with scalable components, and (in most cases) move on to the next thing.

Google tends to value technology. Things are often done because they are technically hard or impressive. On most projects, the engineers make the calls.

Facebook values products and user experience, and designers tend to have a much larger impact. Zuck spends a lot of time looking at product mocks, and is involved pretty deeply with the site's look and feel.

It should be noted that Google deserves credit for succeeding where other large software have mostly failed in putting a bunch of throwing a bunch of Ph.Ds at a problem at actually having them create products that impacts hundreds of millions people as opposed to research papers that impress hundreds of their colleagues. That said, it is easy to see the impact of complexophiles (props to Addy Santo) in recent products like Google Wave.

If you go back and read the Google Wave announcement blog post it is interesting to note the focus on combining features from disparate use cases and the diversity of all of the technical challenges involved at once including

“Google Wave is just as well suited for quick messages as for persistent content — it allows for both collaboration and communication”
“It's an HTML 5 app, built on Google Web Toolkit. It includes a rich text editor and other functions like desktop drag-and-drop”
“The Google Wave protocol is the underlying format for storing and the means of sharing waves, and includes the ‘live’ concurrency control, which allows edits to be reflected instantly across users and services”
“The protocol is designed for open federation, such that anyone's Wave services can interoperate with each other and with the Google Wave service”
“Google Wave can also be considered a platform with a rich set of open APIs that allow developers to embed waves in other web services”

The product announcement read more like a technology showcase than an announcement for a product that is actually meant to help people communicate, collaborate or make their lives better in any way. This is an example of a product where smart people spent a lot of time working on hard problems but at the end of the day they didn't see the adoption they would have liked because they they spent more time focusing on technical challenges than ensuring they were building the right product.

It is interesting to think about all the internal discussions and time spent implementing features like character-by-character typing without anyone bothering to ask whether that feature actually makes sense for a product that is billed as a replacement to email. I often write emails where I write a snarky comment then edit it out when I reconsider the wisdom of sending that out to a broad audience. It’s not a feature that anyone wants for people to actually see that authoring process.

Some of you may remember that there was a time when I was literally the face of XML at Microsoft (i.e. going to http://www.microsoft.com/xml took you to a page with my face on it ). In those days I spent a lot of time using phrases like the XML<-> objects impedance mismatch to describe the fact that the dominate type system for the dominant protocol for web services at the time (aka SOAP) actually had lots of constructs that you don’t map well to a traditional object oriented programming language like C# or Java. This was caused by the fact that XML had grown to serve conflicting masters. There were people who used it as a basis for document formats such as DocBook and XHTML. Then there were the people who saw it as a replacement to for the binary protocols used in interoperable remote procedure call technologies such as CORBA and Java RMI. The W3C decided to solve this problem by getting a bunch of really smart people in a room and asking them to create some amalgam type system that would solve both sets of completely different requirements. The output of this activity was XML Schema which became the type system for SOAP, WSDL and the WS-* family of technologies. This meant that people who simply wanted a way to define how to serialize a C# object in a way that it could be consumed by a Java method call ended up with a type system that was also meant to be able to describe the structural rules of the HTML in this blog post.

Thousands of man years of effort was spent across companies like Sun Microsystems, Oracle, Microsoft, IBM and BEA to develop toolkits on top of a protocol stack that had this fundamental technical challenge baked into it. Of course, everyone had a different way of trying to address this “XML<-> object impedance mismatch which led to interoperability issues in what was meant to be a protocol stack that guaranteed interoperability. Eventually customers started telling their horror stories in actually using these technologies to interoperate such as Nelson Minar’s ETech 2005 Talk - Building a New Web Service at Google and movement around the usage of building web services using Representational State Transfer (REST) was born. In tandem, web developers realized that if your problem is moving programming language objects around, then perhaps a data format that was designed for that is the preferred choice. Today, it is hard to find any recently broadly deployed web service that doesn’t utilize on Javascript Object Notation (JSON) as opposed to SOAP.

The moral of both of these stories is that a lot of the time in software it is easy to get lost in the weeds solving hard technical problems that are due to complexity we’ve imposed on ourselves due to some well meaning design decision instead of actually solving customer problems. The trick is being able to detect when you’re in that situation and seeing if altering some of your base assumptions doesn’t lead to a lot of simplification of your problem space then frees you up to actually spend time solving real customer problems and delighting your users. More people need to ask themselves questions like do I really need to use the same type system and data format for business documents AND serialized objects from programming languages?

Now Playing: Travie McCoy - Billionaire (featuring Bruno Mars)

5 sekretów, których nie zdradzam nieznajomym

2010-08-22T09:54:00Z

Nawet jeśli nie masz paranoi na punkcie prywatności, musisz poznać mało znane funkcje serwisów społecznościowych, które zdradzają twoje dane. I najważniejszą zasadę Internetu. Na wstępie zaznaczę, że ONI mnie nie śledzą. Amerykańskie satelity nie zaglądają mi przez okno, żeby zobaczyć jaką gazetę czytam. Nie zmieniam co miesiąc numeru telefonu. Uważam, że karty kredytowe to jeden z [...]

Lepiej kształci się akwizytorów niż nauczycieli

2010-08-11T16:51:15Z

Przyszli nauczyciele nie są przygotowywani do pracy w szkole. Już o wiele lepiej kształci się akwizytorów. Porównania tego użył Dariusz Kulma, Nauczyciel Roku 2008, w rozmowie z “Głosem Nauczycielskim” (zob. tekst). Nie chodzi o braki w zakresie wiedzy merytorycznej, lecz o nieznajomość technik uczenia, motywowania uczniów, podstaw psychologii, zasad komunikowania się z ludźmi itp.

Kto miałby tego nauczyć studentów, skoro pracownicy uczelni traktują szkoły jak skupiska trędowatych? Zwyczajnie boją się uczniów. Najprawdopodobniej sami nie potrafią motywować do nauki. Mam nadzieję, że sytuacja się zmieniła, ale mój rocznik był motywowany słowami: “Połowa studentów nie zaliczy pierwszego roku” (uwagi do mężczyzn) albo “Mówią, że studiujecie, aby łatwiej znaleźć męża” (uwagi do kobiet). Gdy zaś poinformowałem jednego z profesorów, do którego czułem sympatię, że idę pracować w szkole, życzył mi, aby to nie trwało długo i żebym szybko znalazł coś lepszego. Pracownicy uczelni nie ukrywali, że dla nich szkoła to syf. Czy to się zmieniło?

Na uczelni nauczyłem się podstaw historii metodyki, historii pedagogiki i historii psychologii. Praktyki zaś było tyle, co kot napłakał, mimo że już na pierwszym roku studiów do indeksu wbito mi pieczątkę “specjalizacja pedagogiczna”. Całe szczęście, że pracowałem w handlu. Sztuki komunikowania uczyłem się, sprzedając kasety magnetofonowe i płyty CD. Wzbudzanie motywacji praktykowałem, wciskając ludziom materiały pirotechniczne. A praktyki metodyczne odrabiałem, prowadząc zajęcia dla pielęgniarek z konstrukcji kapci (zajmowałem się marketingiem w firmie produkującej kapcie, sprzedawaliśmy je głównie w szpitalach). Parę lat pracy w handlu uczyniły ze mnie profesjonalnego belfra. Niestety, jeżeli ktoś podczas studiów nie popracuje w handlu, to nie ma szans nauczyć się, jak być sprawnym nauczycielem. Musi uczyć się na własnych błędach z uczniami, a te bywają bolesne

Dremel: Interactive Analysis of Web-Scale Datasets - Data as a Programming Paradigm

2010-08-04T14:04:55Z

If Google was a boxer then MapReduce would be a probing right hand that sets up the massive left hook that is Dremel, Google's—scalable (thousands of CPUs, petabytes of data, trillions of rows), SQL based, columnar, interactive (results returned in seconds), ad-hoc—analytics system. If Google was a magician then MapReduce would be the shiny thing that distracts the mind while the trick goes unnoticed. I say that because even though Dremel has been around internally at Google since 2006, we have not heard a whisper about it. All we've heard about is MapReduce, clones of which have inspired entire new industries. Tricky.

Dremel, according to Brian Bershad, Director of Engineering at Google, is targeted at solving BigData class problems:

While we all know that systems are huge and will get even huger, the implications of this size on programmability, manageability, power, etc. is hard to comprehend. Alfred noted that the Internet is predicted to be carrying a zetta-byte (1021 bytes) per year in just a few years. And growth in the number of processing elements per chip may give rise to warehouse computers of having 1010 or more processing elements. To use systems at this scale, we need new solutions for storage and computation.

Fatal Flaws in Deolalikar’s Proof?

2010-08-13T04:15:21Z

Possible fatal flaws in the finite model part of Deolalikar’s proof

Neil Immerman is one of the world’s experts on Finite Model Theory. He used insights from this area to co-discover the great result that is closed under complement.

Today I had planned not to discuss the proof, but I just received a note from Neil on Vinay Deolalikar “proof” that PNP. Neil points out two flaws in the finite model part that sound extremely damaging to me. He has already shared them with Vinay, and suggested that I highlight them here. The comments from Neil are in the next section—I have only edited it slightly to make it “compile.”

Two Flaws?

Dear Vinay Deolalikar,

Thank you very much for sharing your paper with me. I find your approach and your ideas fascinating, but I am afraid that there is currently a serious hole in your paper as I now describe. For page numbers, I refer to the 102 page, 12 pt. version of your paper.

Your main idea for the lower bound is to show that FO(LFP) is not powerful enough to express SAT, by using Hanf-Gaifman locality to limit the connectivity of the graphs you consider at successive stages of the fixed point computation. As you point out, if a total ordering is given as part of the input structure, then the Gaifman graph has diameter one, so locality is meaningless. Thus you restrict to a successor relation and as you point out, it is still true that FO(LFP) is equal to P in the presence of a successor relation. However, you make two assertions that are not true.

You use the relation as your successor relation. On page 67 you write, “The reason for the relation that creates the chain is that on such structures, polynomial time queries are captured by FO(LFP) [EF06, S11.2].” This is a technicality. Recall that an order on the structure enables the LFP computation (or the Turing machine the runs this computation) to represent tuples in a lexicographical ordering. In our problem -SAT, it plays no further role. Specifically, the assignments to the variables that are computed by the LFP have nothing to do with their order. They depend only on the relation which encodes the clauses and the relation that holds the initial partial assignment that we are going to ask the LFP to extend. In other words, each stage of the LFP is order invariant. It is known that the class of order invariant queries is also Gaifman local [GS00].

Unfortunately, it is not true that each stage of the fixed point must be order invariant. In particular, consider the definition of ordering from successor, easily defined by a least fixed point and thus the reason that successor suffices to capture P. The ordering is defined by taking the transitive closure of the successor relation. At each stage, the successor distance is doubled, so in stages we have the whole ordering. Note that all these stages contain the order dependent information that is part of the original successor relation. It is true that the final aim of your computation is the SAT property which is order independent. But that definitely does not imply that each stage of the induction is order independent.

The other problem is that you restrict your attention to monadic fixed points. You write,

“Remark 7.4. The relation being constructed is monadic, and so it does not introduce new edges into the Gaifman graph at each stage of the LFP computation. When we compute a -ary LFP, we can encode it into a monadic LFP over a polynomially () larger product space, as is done in the canonical structure, for instance, but with the linear order replaced by a weaker successor type relation. Therefore, we can always chose to deal with monadic LFP. This is really a restatement of the transitivity principle for inductive definitions that says that if one can write an inductive definition in terms of other inductively defined relations over a structure, then one can write it directly in terms of the original relations that existed in the structure [Mos74, p. 16].”

It is not the case that you can freely assume that your fixed points are monadic. If you actually work on the canonical structure, then you require the multiple arity relations that can take us from a tuple to its individual elements and back again. These would again make the diameter of the whole graph bounded. However, in your proof you do not include these relations. Thus, your restriction to only have successor and to restrict to monadic fixed points is fundamental. In this domain—only monadic fixed points and successor—FO(LFP) does not express all of P!

Currently, as I see it, the strongest tool we have in descriptive complexity — rather than the locality theorems — is the Håstad Switching Lemma. Paul Beame and Johan Håstad used this to shown that Mike Sipser’s hierarchy theorem extends all the way to FO[]. As you know, FO(LFP) is the same thing as FO[]—properties expressible by the polynomial iteration of a fixed block of restricted quantifiers. We know that is contained in FO[] and this is tight. Furthermore, L and NL are contained in , and it remains open whether is equal to NP. A state of the art paper that I very much recommend is Ben Rossman’s result that expressing the existence of a clique requires variables in FO, and even in FO[] for appropriate . (In Rossman’s result, as in all results that use the switching lemma, the lower bound is true in the presence not just of order, but of any numeric relations including addition and multiplication.)

—Neil

Open Problems

Is Neil right? It seems that the most damaging statement of Neil is:

Thus, your restriction to only have successor and to restrict to monadic fixed points is fundamental. In this domain—only monadic fixed points and successor—FO(LFP) does not express all of P!

Most of us have focused on the issues of 2-SAT and XOR-SAT compared to -SAT, but Neil’s comment points out serious flaws in the finite model part. It was the connection of this work with the random structure of -SAT that excited many of us in the first place. Unless Neil is wrong, it seems that his points are very serious.

Deolalikar Responds To Issues About His P≠NP Proof

2010-08-12T02:14:13Z

A principle for checking proofs with an application to the proof

Vinay Deolalikar is standing by his claim and proof. He and I have been exchanging e-mails, and as noted in the several comments, he has updated his paper several times. The updates are trying to answer some of the questions raised here and elsewhere. However, the consensus seems to be best summarized by a recent comment here by Terence Tao:

I think there are several levels to the basic question “Is the proof correct?”:

Does Deolalikar’s proof, after only minor changes, give a proof that P NP?
Does Deolalikar’s proof, after major changes, give a proof that P NP?
Does the general proof strategy of Deolalikar (exploiting independence properties in random -SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added.” But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days.)

Today I wish to talk about something other than the PNP proof. But it is hard to get back to other issues right now. I do agree with Tao that we need to move on to other topics, and let the proof checking continue at a more relaxed pace.

I would like to share a proof searching trick that I have always used; it must be well known, but I do not know a name for it. The method is quite relevant to the emerging biggest issue in the correctness of Vinay’s proof.

The Principle

Suppose that Alice is trying to prove , some statement that Bob is interested in seeing proved. Alice is working hard trying to understand the problem: she reads the known literature, she talks to experts, she tries some examples, and she thinks hard about the problem.

Finally, after months of hard work, Alice has an outline of a proof. She has not checked all the details, but she is quite excited about the potential. She thinks she has her proof. Imagine that she is about to go to explain the proof to Bob.

Just before she does this, Alice notices the following. Let’s call her proof of the statement . She notices that the same proof—perhaps slightly changed—will also prove . In a sense she sees that

where is a slight variation of her proof .

Here is the principle: this is bad, very bad, if is known to be false. Even if is an open problem, then this could be an issue. The reason is Alice felt she had a nice proof , but did not think her method was powerful enough to solve the hard open problem .

I use this principle—unfortunately all too often—to shoot down my own proof attempts. More than I care to admit, I find a clever “proof” of something, but then realize by the principle it will prove too much. It will either prove something dead-wrong or something that is way too hard for my weak method.

Here are two simple examples of this principle: one imaginary and one real.

Suppose Alice is working on the Riemann Hypothesis. This famous problem says that all the non-trivial zeroes of the zeta function must lie on the line . The zeta function has so called trivial zeroes at

She proves that all the non-trivial zeroes of the zeta function must have a left-to-right symmetry about the line . She then uses this cool lemma to solve the Riemann Hypothesis. She is overjoyed. But after checking her argument she discovers that her cool lemma never used the fact that the zeroes were non-trivial. Clearly, this is a problem, since it would imply that the zeta function has zeroes with real part greater than . This is false and so her lemma has to be re-thought

I have worked on a much less important problem, but one where the principle played a role. I had an idea for proving a certain complexity theorem—nothing like PNP—but still an open problem. I had discovered a partial result based on a “trick” that I had discovered. I was pretty excited and quickly thought I could generalize my trick to solve the full problem. Alas, I saw that the principle applied here: if I could do what I planned, then my proof would yield a result that would violate a known complexity theorem. The problem I worked on is still open. Oh well.

The Proof and The Principle

A number of researchers—including Avi Wigderson and Ryan Williams—have pointed out that Vinay’s proof could fall to the above principle. They do not state their concern in this way, but it is essentially a potential violation of the principle.

In particular their concern is how does the proof tell -SAT from -SAT? If Vinay’s “proof” would work as well on both these types of SAT problems, then there is a fundamental difficulty. Of course, -SAT is long known to be in polynomial time, so if his proof does not have a critical step, lemma, or place where is used in an essential way, then it has problems.

I still do not know for sure what to conclude about this. But this issue is definitely one of the biggest ones that we have seen raised. It is not sufficient to rely on some results having been proved for or —the proof must show how this restriction is used in an essential manner. This may require ensuring that the proof strategy can’t be adapted to properties expressible in the same terms, which would prove an known to be false.

There is a longer discussion of this and related issues with his proof at the wiki page.

Deolalikar’s Answer

Vinay has just responded directly to a number of us in an attempt to explain how his work does use . It is still a bit early to see if his explanation is sufficient, but he does state some technical differences between -SAT and -SAT that he claims to exploit. I have communicated directly with him to ask that he would allow his comments to be made available to the community. He has agreed. (I made slight edits to make the formulas compile into LaTeX.)

Let me try to answer the question, which is “Why does my proof fail for 2-SAT, known to be in P.” The proof requires that the solution space of the CSP be “sufficiently hard to describe.” By that we mean, not possible to describe with fewer than independent parameters. XORSAT does not violate this since its linearity allows simple specification. 2-SAT does not violate this since it does not enter the d1RSB phase. In contrast, 9-SAT onwards do enter the d1RSB phase, and in the absence of properties such as linearity, it is not possible to specify the joint distribution of the covariates in this phase with independent parameters. However, both range and value limited interaction models that underlie LFP algorithms can only furnish such independent parameters to describe their solution spaces. Hence the contradiction. I think this is really the major point. There are many details in the various chapters. I wrote Chapter 3 yesterday to discuss some of this. I discuss the significance of the poly quantity etc.

Open Problems

Of course the key questions remain: Is the proof correct? Or can it be fixed?

Perhaps the last question is what did we learn from the last few hectic days. I think I learned three things: First, that the community is extremely interested in our basic question, P=NP? I find this very positive. I was shocked at the tremendous interest that was generated.

Second, I like that the community reacted in a mostly positive and supportive manner. I think we owe Vinay a thanks, no matter what the final outcome is. He has raised some interesting connections that, as Tao says, may be useful in the future. He also showed how people can ask hard questions, and how the community can be helpful. Yes, there were some tough comments here and elsewhere, but for the most part I think the experience has been positive.

Finally, I realized that it is not possible to keep up the hectic pace of the last few days for much longer. I hope we helped, I hope we were always positive, and I hope the work here in trying to resolve this exciting event has been a positive contribution. I thank you all for your kind interest.

Of Mainframes And Clouds

2010-08-02T20:07:20Z

When I speak in front of audiences, I usually try and push the boundaries a bit by being intentionally controversial.

Today was no exception. I spoke at a partner event (GreenPages) in front of about 100 people about the journey to the private cloud. Some of my comments even made it to CRN in real-time -- scary thought.

At one point, I asked if anyone in the room had done "hard time on mainframes". And, as usual, a few hands went up.

For these people, the current move to cloud architectures is going to give many of them a strange sense of deja-vu ...

To Begin With

In Chuck's Oversimplified Technology Dictionary, a "cloud" is any IT environment that's (a) built differently (dynamic pools of shared resources) (b) operated differently (end-to-end service delivery vs. individual silos) and (c) consumed differently.

Going a bit farther, a "private cloud" is a cloud that IT controls -- regardless of whether the resources run internally or externally.

However, this sort of definition doesn't prescribe things like processor technologies (even though there's a strong case to be made for x86) or hypervisor technology (ditto strong case for VMware) and so on.

Simply put, any set of technologies that can get you there ought to qualify as "cloud", right?

Indeed, I wrote a post a while back ("Back To The Future") where I compared many aspects of our idealized cloud world with the legacy established by mainframes. I drew some predictable fire for that one, but I still stand by my core assertions.

Much of the cloud discussion rests on the choice of processor architecture -- as no one has been overly successful in combining multiple incompatible processor architectures into a single, homogeneous pool of virtualized resources.

Processors are one of the key areas that people are going to have to standardize on when they consider their next-gen environments. And right now, all signs point to two clear architectural winners going forward: the x86 processor, and z/OS.

The Narrowing Of The Processor World

During the course of my career, I've been exposed to a dozen or so of processor technologies -- Motorola, MIPS, Alpha -- the list goes on and on.

No one talks seriously about Itanium any more, SPARC's role in Oracle's grand plans is decidedly unclear at present, and -- yes -- IBM keeps swinging away at Power -- but you've got to wonder how long they're going to keep that up -- especially with a wholesale migration of the IT ecosystem to x86 binaries.

Some people just assume that all clouds will be built on x86 architectures, and that's that. But I would beg to differ ...

So, What About Mainframes?

Anyone who blithely proclaims "mainframes are dead" probably hasn't spent much time in larger IT shops. The people who make those claims are more likely to be gone before the mainframes are ... :-)

As far as I can see, people continue to use mainframes for three primary reasons: (1) they're locked in by legacy applications, (2) they handle really scary workloads very well, and (3) run properly, they can be an incredibly efficient way of delivering IT services at scale.

#1 is unfortunate, but we can't do much about that. However, #2 and #3 deserve a bit more discussion.

So much of cloud is about scale-out -- relatively uniform workloads that are easily divisible into more manageable tasks. Mainframes also provide scale-up -- the ability to run enormous single-threaded tasks -- at blinding performance.

Yes, many of those workloads could be re-architected to be more amenable to scale-out architectures, but that's an expensive proposition in itself. And, of course, x86 and associated technologies keep pushing the boundaries with every tick and tock.

Where I think the mainframe approach clearly shines is in the maturity of the integration and associated operational processes. And there are a lot of great lessons to be learned by newer cloud practitioners from their mainframe elders.

Thinking About Those Processes ...

Imagine a very modern mainframe, perhaps running thousands of Linux VMs.

Self-service provisioning for end users? Integrated automation? Monitoring end-to-end service delivery across multiple elements? Been around for years, thank you -- nothing new here.

Sweating hardware and software assets to the n-th degree? Extremely efficient cost-to-serve? Old hat, thank you.

Chargeback? Oversubscription? Aggregate capacity planning? Integrated security and GRC? Advanced backup and replication? Plenty of real-world examples to choose from -- mainframe shops have been doing this for years.

I clearly remember getting my first chargeback bill from a mainframe service provider way back in 1980. One big number, followed by reams of overly precise usage detail on CPU/minutes, IOs, storage, memory, etc.

Of course, it came to me on green-bar paper :-)

Implementing a private cloud with a combination of internal and external resources? Moving workloads around? Mainframe shops have been doing this for many years, albeit with comparatively expensive technology.

The New Economics

In many ways, the current private cloud discussion might be construed as a re-framing of mainframe concepts, only this time with a healthy helping of the new tech economics: commercial hardware, plentiful bandwidth and open source application software.

Maybe the supporting technology is rather new, but the underlying cloud operational processes that deliver all the magic really aren't all that new -- especially if you've been around in some the larger mainframe shops.

So, Where Am I Going With All Of This?

Glad you asked ...

A rather innocuous press release from EMC announced several important capabilities we've added to our historical mainframe support.

Things like full storage API access from Linux VMs under z/OS. A spiffy new non-disruptive migration capability. Dedupe for mainframe backup. FICON enhancements. And a bunch more.

Much of the press release discusses the relationship between mainframes and private clouds. You might be tempted to dismiss the prose as so much marketing fluff, but it's not -- some of the most advanced private cloud implementations today are mainframes -- and this is likely to continue into the future.

Indeed, EMC's mainframe DNA impacts how we interpret terms like "non-disruptive" and "mission critical" and "high availability" and a lot else as well. I think that one of the reasons so many shops depend on EMC for their most important apps is that we understand serious IT -- regardless of whether it's z/OS, UNIX or an uber-large VMware farm on the floor.

There's another important message here as well: the cool things we continue to do for x86/hypervisor stacks, we also intend to do in the z/OS world.

Because mainframes aren't going away any time soon ...

Beyond Locks and Messages: The Future of Concurrent Programming

2010-08-02T19:02:43Z

Concurrent programming has been around for quite some time (almost half a century), but it was mostly accessible to the highest ranks of the programming priesthood. This changed when, in the 2000s, concurrency entered prime time, prodded by the ubiquity of multicore processors. The industry can no longer afford to pay for hand-crafted hand-debugged concurrent solutions. The search is on for programming paradigms that lead to high productivity and reliability.

Recently DARPA created its HPCS, High Productivity Computing Systems, program (notice the stress on productivity), and is funding research that lead to, among other things, the development of new programming languages that support concurrency. I had a peek at those languages and saw some very interesting developments which I’d like to share with you. But first let me give you some perspective on the current state of concurrency.

Latency vs. Parallel Performance

We are living in the world of multicores and our biggest challenge is to make use of parallelism to speed up the execution of programs. As Herb Sutter famously observed, we can no longer count on the speed of processors increasing exponentially. If we want our programs to run faster we have to find ways to take advantage of the exponential increase in the number of available processors.

Even before multicores, concurrency had been widely used to reduce latencies and to take advantage of the parallelism of some peripherals (e.g., disks). Low latency is particularly important in server architectures, where you can’t wait for the completion of one request before you pick up the next one.

Initially, the same approach that was used to reduce latency–creating threads and using message-passing to communicate between them–has been used to improve parallel performance. It worked, but it turned out to be extremely tedious as a programming paradigm.

There will always be a niche for client/server architectures, which are traditionally based on direct use of threads and message passing. But in this post I will limit myself to strategies for maximizing program performance using parallelism. These strategies are becoming exponentially more important with time.

Threads? Who Needs Threads?

There are two extremes in multithreading. One is to make each thread execute different code–they all have different thread functions (MPMD–Multiple Programs Multiple Data, or even MPSD–Multiple Programs Single Data). This approach doesn’t scale very well with the number of cores–after all there is a fixed number of thread functions in one program no matter how many cores it’s running on.

The other extreme is to spawn many threads that essentially do the same thing (SPMD, Single Program Multiple Data). On the very extreme we have SIMD (Single Instruction Multiple Data), the approach taken, e.g., graphics accelerators. There, multiple cores execute the same instructions in lockstep. The trick is to start them with slightly different initial states and data sets (the MD part), so they all do independently useful work. With SPMD, you don’t have to write lots of different thread functions and you have a better chance at scaling with the number of cores.

There are two kinds of SPMD. When you start with a large data set and split it into smaller chunks and create separate threads to process each chunk, it’s called data-driven parallelism. If, on the other hand, you have a loop whose iterations don’t depend on each other (no data dependencies), and you create multiple threads to process individual iterations (or groups thereof), it’s called control-driven parallelism.

These types of parallelism become more and more important because they allow programs to be written independent of the number of available cores. And, more importantly, they can be partially automated (see my blog on semi-implicit parallelism).

In the past, to explore parallelism, you had to create your own thread pools, assign tasks to them, balance the loads, etc., by hand. Having this capacity built into the language (or a library) takes your mind off the gory details. You gain productivity not by manipulating threads but by identifying the potential for parallelism and letting the compiler and the runtime take care of the details.

In task-driven parallelism, the programmer is free to pick arbitrary granularity for potential parallelizability, rather than being forced into the large-grain of system threads. As always, one more degree of indirection solves the problem. The runtime may chose to multiplex tasks between threads and implement work stealing queues, like it’s done in Haskell, TPL, or TBB. Programming with tasks rather than threads is also less obtrusive, especially if it has direct support in the language.

Shared Memory or Message Passing?

Threads share memory, so it’s natural to use shared memory for communication between threads. It’s fast but, unfortunately, plagued with data races. To avoid races, access to shared (mutable) memory must be synchronized. Synchronization is usually done using locks (critical sections, semaphores, etc.). It’s up to the programmer to come up with locking protocols that eliminate races and don’t lead to deadlocks. This, unfortunately, is hard, very hard. It’s definitely not a high-productivity paradigm.

One way to improve the situation is to hide the locking protocols inside message queues and switch to message passing (MP). The programmer no longer worries about data races or deadlocks. As a bonus, MP scales naturally to distributed, multi-computer, programming. Erlang is the prime example of a programming language that uses MP exclusively as its concurrency paradigm. So why isn’t everybody happy with just passing messages?

Unfortunately not all problems lend themselves easily to MP solutions–in particular, data driven parallelism is notoriously hard to express using message passing. And then there is the elephant in the room–inversion of control.

We think linearly and we write (and read) programs linearly–line by line. The more non-linear the program gets, the harder it is to design, code, and maintain it (gotos are notorious for delinearizing programs). We can pretty easily deal with some of the simpler MP protocols–like the synchronous one. You send a message and wait for the response. In fact object oriented programming is based on such a protocol–in the Smalltalk parlance you don’t “call” a method, you “send a message” to an object. Things get a little harder when you send an asynchronous message, then do some other work, and finally “force” the answer (that’s how futures work); although that’s still manageable. But if you send a message to one thread and set up a handler for the result in another, or have one big receive or select statement at the top to process heterogeneous messages from different sources, you are heading towards the land of spaghetti. If you’re not careful, your program turns into a collection of handlers that keep firing at random times. You are no longer controlling the flow of execution; it’s the flow of messages that’s controlling you. Again, programmer productivity suffers. (Some research shows that the total effort to write an MPI application is significantly higher than that required to write a shared-memory version of it.)

Back to shared memory, this time without locks, but with transactional support. STM, or Software Transactional Memory, is a relatively new paradigm that’s been successfully implemented in Haskell, where the type system makes it virtually fool-proof. So far, implementations of STM in other languages haven’t been as successful, mostly because of problems with performance, isolation, and I/O. But that might change in the future–at least that’s the hope.

What is great about STM is the ease of use and reliability. You access shared memory, either for reading of writing, within atomic blocks. All code inside an atomic block executes as if there were no other threads, so there’s no need for locking. And, unlike lock-based programming, STM scales well.

There is a classic STM example in which, within a single atomic block, money is transferred between two bank accounts that are concurrently accessed by other threads. This is very hard to do with traditional locks, since you must lock both accounts before you do the transfer. That forces you not only to expose those locks but also puts you in risk of deadlocks.

As far as programmer productivity goes, STM is a keeper.

Three HPCS Languages

Yesterday’s supercomputers are today’s desktops and tomorrow’s phones. So it makes sense to look at the leading edge in supercomputer research for hints about the future. As I mentioned in the introduction, there is a well-funded DARPA program, HPCS, to develop concurrent systems. There were three companies in stage 2 of this program, and each of them decided to develop a new language:

Cray: Chapel
IBM: X10
Sun: Fortress

(Sun didn’t get to the third stage, but Fortress is still under development.)

I looked at all three languages and was surprised at how similar they were. Three independent teams came up with very similar solutions–that can’t be a coincidence. For instance, all three adopted the shared address space abstraction. Mind you, those languages are supposed to cover a large area: from single-computer multicore programming (in some cases even on an SIMD graphics processor) to distributed programming over huge server farms. You’d think they’d be using message passing, which scales reasonably well between the two extremes. And indeed they do, but without exposing it to the programmer. Message passing is a hidden implementation detail. It’s considered too low-level to bother the programmer with.

Running on PGAS

All three HPCS languages support the shared address space abstraction through some form of PGAS, Partitioned Global Address Space. PGAS provides a unified way of addressing memory across machines in a cluster of computers. The global address space is partitioned into various locales (places in X10 and regions in Fortress) corresponding to local address spaces of processes and computers. If a thread tries to access a memory location within its own locale, the access is direct and shared between threads of the same locale. If, on the other hand, it tries to access a location in a different locale, messages are exchanged behind the scenes. Those could be inter-process messages on the same machine, or network messages between computers. Obviously, there are big differences in performance between local and remote accesses. Still, they may look the same from the programmer’s perspective. It’s just one happy address space.

By now you must be thinking: “What? I have no control over performance?” That would be a bad idea indeed. Don’t worry, the control is there, either explicit (locales are addressable) or in the form of locality awareness (affinity of code and data) or through distributing your data in data-driven parallelism.

Let’s talk about data parallelism. Suppose you have to process a big 2-D array and have 8 machines in your cluster. You would probably split the array into 8 chunks and spread them between the 8 locales. Each locale would take care of its chunk (and possibly some marginal areas of overlap with other chunks). If you’re expecting your program to also run in other cluster configurations, you’d need more intelligent partitioning logic. In Chapel, there is a whole embedded language for partitioning domains (index sets) and specifying their distribution among locales.

To make things more concrete, let’s say you want to distribute a (not so big) 4×8 matrix among currently available locales by splitting it into blocks and mapping each block to a locale. First you want to define a distribution–the prescription of how to distribute a block of data between locales. Here’s the relevant code in Chapel:

const Dist = new dmap(new Block(boundingBox=[1..4, 1..8]));

A Block distribution is created with a bounding rectangle of dimension 4×8. This block is passed as an argument to the constructor of a domain map. If, for instance, the program is run on 8 locales, the block will be mapped into 8 2×2 regions, each assigned to a different locale. Libraries are supposed to provide many different distributions–block distribution being the simplest and the most useful of them.

When you apply the above map to a domain, you get a mapped domain:

var Dom: domain(2) dmapped Dist = [1..4, 1..8];

Here the variable Dom is a 2-D domain (a set of indices) mapped using the distribution Dist that was defined above. Compare this with a regular local domain–a set of indices (i, j), where i is between 1 and 4 (inclusive) and j is between 1 and 8.

var Dom: domain(2) = [1..4, 1..8];

Domains are used, for instance, for iteration. When you iterate over an unmapped domain, all calculations are done within the current locale (possibly in parallel, depending on the type of iteration). But if you do the same over a mapped domain, the calculations will automatically migrate to different locales.

This model of programming is characterized by a very important property: separation of algorithm from implementation. You separately describe implementation details, such as the distribution of your data structure between threads and machines; but the actual calculation is coded as if it were local and performed over monolithic data structures. That’s a tremendous simplification and a clear productivity gain.

Task-Driven Parallelism

The processing of very large (potentially multi-dimensional) arrays is very useful, especially in scientific modeling and graphics. But there are also many opportunities for parallelism in control-driven programs. All three HPCS languages chose fine-grained tasks (activities in X10, implicit threads in Fortress), not threads, as their unit of parallel execution. A task may be mapped to a thread by the runtime system but, in general, this is not a strict requirement. Bunches of small tasks may be bundled for execution within a single system thread. Fortress went the furthest in making parallelism implicit–even the for loop is by default parallel.

From the programmer’s perspective, task-driven parallelism doesn’t expose threads (there is no need for a fork statement or other ways of spawning threads). You simply start a potentially parallel computation. In Fortress you use a for loop or put separate computations in a tuple (tuples are evaluated in parallel, by default). In Chapel, you use the forall statement for loops or begin to start a task. In X10 you use async to mark parallelizable code.

What that means is that you don’t have to worry about how many threads to spawn, how to manage a thread pool, or how to balance the load. The system will spawn the threads for you, depending on the number of available cores, and it will distribute tasks between them and take care of load balancing, etc. In many cases it will do better than a hand-crafted thread-based solution. And in all cases the code will be simpler and easier to maintain.

Global View vs. Fragmented View

If you were to implemented parallel computation using traditional methods, for instance MPI (Message Passing Interface), instead of allocating a single array you’d allocate multiple chunks. Instead of writing an algorithm to operate on this array you’d write an algorithm that operates on chunks, with a lot of code managing boundary cases and communication. Similarly, to parallelize a loop you’d have to partially unroll it and, again, take care of such details as the uneven tail, etc. These approaches results in fragmented view of the problem.

What HPCS languages offer is global view programming. You write your program in terms of data structures and control flows that are not chopped up into pieces according to where they will be executed. Global view approach results in clearer programs that are easier to write and maintain.

Synchronization

No Synchronization?

A lot of data-driven algorithms don’t require much synchronization. Many scientific simulations use read-only arrays for input, and make only localized writes to output arrays.

Consider for instance how you’d implement the famous Game of Life. You’d probably use a read-only array for the previous snapshot and a writable array for the currently evaluated state. Both arrays would be partitioned in the same way between locales. The main loop would go over all array elements and concurrently calculate each one’s new state based on the previous state of its nearest neighbors. Notice that while the neighbors are sometimes read concurrently by multiple threads, the output is always stored once. The only synchronization needed is a thread barrier at the end of each cycle.

The current approach to synchronization in HPCS languages is the biggest disappointment to me. Data races are still possible and, since parallelism is often implicit, harder to spot.

The biggest positive surprise was that all three endorsed transactional memory, at least syntactically, through the use of atomic statements. They didn’t solve the subtleties of isolation, so safety is not guaranteed (if you promise not to access the same data outside of atomic transactions, the transactions are isolated from each other, but that’s all).

The combination of STM and PGAS in Chapel necessitates the use of distributed STM, an area of active research (see, for instance, Software Transactional Memory for Large Scale Clusters).

In Chapel, you not only have access to atomic statements (which are still in the implementation phase) and barriers, but also to low level synchronization primitives such as sync and single variables–somewhat similar to locks and condition variables. The reasoning is that Chapel wants to provide multi-resolution concurrency support. The low level primitives let you implement concurrency in the traditional style, which might come in handy, for instance, in MPMD situations. The high level primitives enable global view programming that boosts programmer productivity.

However, no matter what synchronization mechanism are used (including STM), if the language doesn’t enforce their use, programmers end up with data races–the bane of concurrent programming. The time spent debugging racy programs may significantly cut into, or even nullify, potential productivity gains. Fortress is the only language that attempted to keep track of which data is shared (and, therefore, requires synchronization), and which is local. None of the HPCS languages tried to tie sharing and synchronization to the type system in the way it is done, for instance, in the D programming language (see also my posts about race-free multithreading).

Conclusions

Here’s the tongue-in-cheek summary of the trends which, if you believe that the HPCS effort provides a glimpse of the future, will soon be entering the mainstream:

Threads are out (demoted to latency controlling status), tasks (and semi-implicit parallelism) are in.
Message passing is out (demoted to implementation detail), shared address space is in.
Locks are out (demoted to low-level status), transactional memory is in.

I think we’ve been seeing the twilight of thread-based parallelism for some time (see my previous post on Parallel Programming with Hints. It’s just not the way to fully explore hardware concurrency. Traditionally, if you wanted to increase the performance of your program on multicore machines, you had to go into the low-level business of managing thread pools, splitting your work between processors, etc. This is now officially considered the assembly language of concurrency and has no place in high level programming languages.

Message passing’s major flaw is the inversion of control–it is a moral equivalent of gotos in un-structured programming (it’s about time somebody said that message passing is considered harmful). MP still has its applications and, used in moderation, can be quite handy; but PGAS offers a much more straightforward programming model–its essence being the separation of implementation from algorithm. The Platonic ideal would be for the language to figure out the best parallel implementation for a particular algorithm. Since this is still a dream, the next best thing is getting rid of the interleaving of the two in the same piece of code.

Software transactional memory has been around for more than a decade now and, despite some negative experiences, is still alive and kicking. It’s by far the best paradigm for synchronizing shared memory access. It’s unobtrusive, deadlock-free, and scalable. If we could only get better performance out of it, it would be ideal. The hope though is in moving some of the burden of TM to hardware.

Sadly, the ease of writing parallel programs using those new paradigms does not go hand in hand with improving program correctness. My worry is that chasing concurrency bugs will eat into productivity gains.

What are the chances that we’ll be writing programs for desktops in Chapel, X10, or Fortress? Probably slim. Good chances are though that the paradigms used in those languages will continue showing up in existing and future languages. You may have already seen task driven libraries sneaking into the mainstream (e.g., the .NET TPL). There is a PGAS extension of C called UPC (Unified Parallel C) and there are dialects of several languages like Java, C, C#, Scala, etc., that experiment with STM. Expect more in the future.

Acknowledgments

Special thanks go to Brad Chamberlain of the Cray Chapel team for his help and comments. As usual, a heated exchange with the Seattle Gang, especially Andrei Alexandrescu, lead to numerous improvements in this post.

Bibliography

DARPA’s High Productivity Computing Systems
Cray Chapel
IBM X10
Sun Fortress
Message Passing Interface specification
Unified Parallel C, PGAS in C
Microsoft Task Parallel Library
Intel Thread Building Blocks
HPC Programmer Productivity:
A Case Study of Novice HPC Programmers
Software Transactional Memory for Large Scale Clusters
Scalable Software Transactional Memory for Global Address Space Architectures
A Brief Retrospective on Transactional Memory
Designing an Effective
Hybrid Transactional Memeory System
Concurrency in the D Programming Language

Python optimization note: function calls are slow

2010-07-26T15:01:03Z

In Mercurial, we do a lot of gathering and filtering of long lists of things – filenames, revision numbers, etc. A typical pattern is something like this:

l = []
for f in files:
    if f.startswith(foo):
        l.append(f)

Usually it’s more involved than that – there’s often multiple lists to track and several tests, so a simple comprehension won’t help. And usually performance of these loops is pretty critical. If we can shave 10% off a call to status when there are 50,000 files, we’ll do it. So one of the first things we do is:

l = []
la = l.append
for f in files:
    if f.startswith(foo):
        la(f)

This saves a lookup in the inner loop, and that’s often a very measurable win. Another pattern is that sometimes one or more of the lists isn’t going to be needed, so we’ll avoid appending to it at all. So is it better to call a dummy function or stick an if statement in the inner loop? Let’s consider variations on this simple test:

a = []
f = False
aa = a.append
for x in xrange(1000000):
    if f:
        aa(x)

Let’s explore some possibilities and time them with timeit (Python 2.6.5):

append function	flag	test	time
None	True	if f: a.append	216 msec
None	True	a.append	197 msec
a.append	True	if f: la(x)	133 msec
a.append	False	if f: la(x)	63 msec
a.append	True	f and la(x)	133 msec
a.append	False	f and la(x)	65 msec
a.append	True	la(x)	113 msec
lambda x: None	False	la(x)	239 msec
id	False	la(x)	110 msec

The fastest way to add to a list (flag is True) is with a pre-looked-up list append function and no test. But the fastest way to not add to our list is with the if test. And both of these are significantly faster than the naive ‘if f: a.append(x)’ approach.

Thus, if we expect to usually be adding to a given list, we should set la to a handy dummy function like the ‘id’ built-in when our flag tells us not to gather to a list. This is much faster than the obvious lambda function by virtue of being a trivial built-in, and gives us a ‘balanced’ 113/110 msec split between keep and discard. But if we usually don’t want a list (for instance, Mercurial usually doesn’t report ‘clean’ files), then an if statement is best, with a 133/63 keep/discard split.

Boli mnie w krzyżu

2010-08-09T19:39:36Z

W sprawie krzyża spod pałacu dostałem ostatnio kilka listeli z pytaniami "a co ja właściwie o tym myślę?" W zasadzie to nie rozumiem: nie czuję się jeszcze aż takim autorytetem moral

When Not Responding Online Is The Right Response

2010-08-09T11:54:20Z

The common online rhetoric is to respond to everything that is being said about your brand. That could be a mistake.

With new Social Media monitoring tools - or just some careful snooping around - it has never been easier to figure out who are the people with a legitimate concern and who are the quacks just trying to feed their own need for attention. And yes, there are even those whose only goal is to push their own agenda forward by drawing attention to themselves. There's a known saying amongst the Digerati: "don't feed the Trolls." The Wikipedia definition of "troll" is "someone who posts inflammatory, extraneous, or off-topic messages in an online community, such as an online discussion forum, chat room, or blog, with the primary intent of provoking other users into a desired emotional response or of otherwise disrupting normal on-topic discussion." The point being, you're never going to make someone like this happy or get any level of customer service rectified. Even when/if you respond to their needs with an equitable resolution, you'll soon be trapped in a, "give them an inch and they'll take you a mile," scenario where nothing you do will ever be enough (because their intent was never to get any form of resolution in the first place).

Simply don't respond.

That's going to sound very radical in a day and age where most new media pundits will tell you the opposite. This past week, someone commented in their Twitter feed about a brand and situation they were not happy with (translation: their personal cause/agenda was not highlighted and they felt like the company should pay more attention to their plight). When the company didn't respond, the known troll went after people who were mentioning the same brand in their tweets and asked for their opinion on the company's choice to not highlight their personal issue. Many of the people that this individual reached out to didn't engage or responded in a very succinct and finite way (the Social Media equivalent of crickets in the night). With nowhere to go, and no wind left in their sails, the troll continued to rally for their cause in their own Facebook and Twitter stream, but there was little-to-no traction. With that, the grandstanding became nothing more than the online version of someone wandering the downtown streets blurting absurdities at the top of their lungs until the cops come by and politely ask them to, "move on."

People know when you have a genuine complaint. People know when you're simply pushing your own agenda.

A smart company is one that can respond with professionalism and resolution. A smart company is one that doesn't spend hours of time and resources trying to please the unappeasable. It's an important distinction, and now that we can see a semblance of maturity online when it comes to individual's and their digital legacies, it's easier to figure out the raisins from the nuts. At first, the ability to make this distinction will not be obvious, and brands (as we have seen) have been sucked into major back-and-forths that have never ended well. Ultimately, the troll is never satisfied and all the brand did was give that individual's actions a platform and some real credibility where none existed before.

It's a delicate balance.

Zappos is brilliantly kind to everyone. Others believe that "your call is important to us" means that you will soon be treated like garbage. Not everyone online is a troll. Not everyone online is out to get a brand in a "gotcha!" kind of way. In fact, the opposite is (mostly) true: Assume two percent of the population is evil. Assume a slightly larger percentage are trolls and take some level of pride in getting a brand to react to their irrational opinions. Beyond that, know why and how you're going to engage online, and when cornered by someone who will never be happy, change the venue: ask if you can give them a call on the phone to discuss or offer to bring them into your office for a meeting or a tour. More often than not they will scurry back to the comfort of their keyboard and the warm glow of their monitor.

A great question to ask yourself...

When thinking about these online shift disturbers, ask yourself: Who is this person? What do they do? Who works with them? Who are they connected to? What are the types of conversations that they have recently had? A bit of research goes a long way, and can easily highlight whether or not there is a semi-legitimate concern that needs to be addressed or if you're dealing with someone who is just looking for a one-sided fight.

Do you think it's acceptable not to respond to certain individuals online? Or are all gripes created equal? What's your take?

Tags: attention blog brand complaint credibility customer service digerati digital legacy facebook new media online community online grandstanding social media social media monitoring troll twitter wikipedia your call is important to us zappos

A Proof That P Is Not Equal To NP?

2010-08-09T01:11:24Z

A serious proof that claims to have resolved the P=NP question.

Vinay Deolalikar is a Principal Research Scientist at HP Labs who has done important research in various areas of networks. He also has worked on complexity theory, including previous work on infinite versions of the P=NP question. He has just claimed that he has a proof that P is not equal to NP. That’s right: . No infinite version. The real deal.

Today I will talk about his paper. So far I have only had a chance to glance at the paper; I will look at it more carefully in the future. I do not know what to think right now, but I am certainly hopeful.

The Paper

Deolalikar’s draft paper is here—he was kind enough to give me the pointer to his paper. For now please understand that this is a “preliminary version.” See the discussion by Greg Baker, who first posted on his paper.

At first glance it is a long, well written paper, by a serious researcher. He clearly knows a great deal of complexity theory and mathematics. His Ph.D. thesis at USC is titled:

On splitting places of degree one in extensions of algebraic function fields, towers of function fields meeting asymptotic bounds, and basis constructions for algebraic-geometric codes.

My first thought is who knows—perhaps this is the solution we have all have been waiting for. If it is correct, the Clay list will drop down to five. I assume he would take the prize.

But first there is the small issue of correctness. Is his paper correct?

I suggest you look at his paper to see his own summary of his approach, and of course the details of his proof. At the highest level he is using the characterization of polynomial time via finite model theory. His proof uses the beautiful result of Moshe Vardi (1982) and Neil Immerman (1986):

Theorem: On ordered structures, a relation is defined by a first order formula plus the Least Fixed Point (LFP) operator if and only if it is computable in polynomial time.

Then, he attacks SAT directly. He creates an ordered structure that encodes SAT. He then argues if P=NP, then by the above theorem it must follow that SAT has certain structural properties. These properties have to do with the structure of random SAT. This connection between finite model theory and random SAT models seems new to me.

The one thing that strikes me immediately is his use of finite model theory. This is one area of logic that has already led to at least one breakthrough before in complexity theory. I believe that Neil used insights from this area to discover his famous proof that is closed under complement. It is interesting that the “final” proof does not directly use the machinery of finite model theory. Deolalikar’s connection between model theory and the structure of random SAT is interesting. I hope it works, or at least sheds new light on SAT.

An obvious worry about his proof, just from a quick look, is the issue of relativization. I believe that the LFP characterization, and similar first order arguments do relativize in general. However, it is possible that his use of concretely encoded structures prevents his entire argument from relativizing. We will need to check carefully that his proof strategy evades this limitation. I am on record as not being a fan of oracle results, so if this is the problem for his proof, I will have to re-think my position. Oh well.

Deolalikar does cite both Baker-Gill-Solovay for relativization and Razborov-Rudich for the “Natural Proofs” obstacle. His proof strategy ostensibly evades the latter because it exploits a uniform characterization of P that may not extend to give lower bounds against circuits. In fact the paper does not state a concrete time lower bound for SAT, as the proof is by contradiction. Since the gap in the contradiction is between “” and “,” it is possible that a time lower bound of “ for some ” is implied. More will have to wait until there is time to examine all the threads of this long and complex paper closely. However, the author certainly shows awareness of the relevant obstacles and command of literature supporting his arguments—this is a serious effort.

Open Problems

Is his paper correct? How does he avoid all the “barriers” that have been claimed to surround the P=NP question? Let’s hope it all checks out.

Emacs-fu: some handy key bindings

2010-07-30T19:49:00Z

Emacs offers many handy key bindings; every now and then I come across a new one, which has been hiding there somewhere for a decade or more… Here are some of my favorites – I'm listing those that are (a) often useful, (b) might not be known by everyone already (c) don't require any external packages or setup.

M-27 x gives you xxxxxxxxxxxxxxxxxxxxxxxxxxx; and, believe it or not, works also with different characters and numbers;
M-m jumps to the first non-whitespace character on the current line;
M-^ joins two lines into one – like vi(m)'s :join, except that point must be on the second line, not the first;
M-/ auto-completes based on words in all your buffers; there are more powerful alternatives, but this one does not require any setup;
C-h k followed by some key or key combination tells you what it does, C-h m describes the currently active modes, with their key bindings;
C-h f documents the current function, C-h v does the same for variables. C-h a gives you information about commands - for example to get date-related commands, press C-h a date. This will, however, also get you commands related to update; instead, you can use C-h a \bdate (because C-h a accepts regular expressions);
C-x C-o will delete all the empty lines around your current cursor position, except for one;
M-q re-aligns the current paragraph; I use it all the time when writing e-mails etc. (you might want to check out filladapt for a version that gives you a bit more smartness with indentations, lists etc.);
C-x 8 RET in a recent emacs version gives you an auto-completable list of special characters to insert. So if I need, say, the Yen-character, I type C-x 8 RET ye TAB and I get YEN SIGN, which RET will then insert: ¥. Note that the completion only works on the start of the character name, so if you'd want to include the α-character, you'd need to know that its UCS-name is GREEK SMALL LETTER ALPHA… (you can try *alpha or TAB the empty string, and search in the results buffer, but that's rather slow);
C-h l shows your last 300 key presses ('lossage'). Interesting to see, and it might be useful when defining keyboard macros.

What are your favorites? Please share them in the comments.

07/30/10 PHD comic: 'Too due list'

2010-08-02T07:08:46Z

Piled Higher & Deeper by Jorge Cham		www.phdcomics.com

title: "Too due list" - originally published 7/30/2010

Is floating point math deterministic? - Shawn Hargreaves Blog - Site Home - MSDN Blogs

2010-08-01T20:53:51Z

Tribalism is the enemy within

2010-07-30T12:32:34Z

Tribalism is when one group of people start to think people from another group are “wrong by default”. It’s the great-granddaddy of racism and sexism. And the most dangerous kind of tribalism is completely invisible: it has nothing to do with someone’s “birth tribe” and everything to do with their affiliations: where they work, which sports team they support, which linux distribution they love.

There are a couple of hallmarks of tribal argument:

1. “The other guys have never done anything useful”. Well, let’s think about that. All of us wake up every day, with very similar ambitions and goals. I’ve travelled the world and I’ve never met a single company, or country, or church, where *everybody* there did *nothing* useful. So if you see someone saying “Microsoft is totally evil”, that’s a big red flag for tribal thinking. It’s just like someone saying “All black people are [name your prejudice]“. It’s offensive nonsense, and you would be advised to distance yourself from it, even if it feels like it would be fun to wave that pitchfork for a while.

2. “Evidence contrary to my views doesn’t count.” So, for example, when a woman makes it to the top of her game, “it’s because she slept her way there”. Offensive nonsense. And similarly, when you see someone saying “Canonical didn’t actually sponsor that work by that Canonical employee, that was done in their spare time”, you should realize that’s likely to be offensive nonsense too.

Let’s be clear: tribalism makes you stupid. Just like it would be stupid not to hire someone super-smart and qualified because they’re purple, or because they are female, it would be stupid to refuse to hear and credit someone with great work just because they happen to be associated with another tribe.

The very uncool thing about being a fanboy (or fangirl) of a project is that you’re openly declaring both a tribal affiliation and a willingness to reject the work of others just because they belong to a different tribe.

One of the key values we hold in the Ubuntu project is that we expect everyone associated with Ubuntu to treat people with respect. It’s part of our code of conduct – it’s probably the reason we *pioneered* the use of codes of conduct in open source. I and others who founded Ubuntu have seen how easily open source projects descend into nasty, horrible and unproductive flamewars when you don’t exercise strong leadership away from tribal thinking.

Now, bad things happen everywhere. They happen in Ubuntu – and because we have a huge community, they are perhaps more likely to happen there than anywhere else. If we want to avoid human nature’s worst consequences, we have to work actively against them. That’s why we have strong leadership structures, which hopefully put people who are proven NOT to be tribal in nature into positions of responsibility. It takes hard work and commitment, but I’m grateful for the incredible efforts of all the moderators and council members and leaders in LoCo teams across this huge and wonderful project, for the leadership they exercise in keeping us focused on doing really good work.

It’s hard, but sometimes we have to critique people who are associated with Ubuntu, because they have been tribal. Hell, sometimes I and others have to critique ME for small-minded and tribal thinking. When someone who calls herself “an Ubuntu fan” stands up and slates the work of another distro we quietly reach out to that person and point out that it’s not the Ubuntu way of doing things. We don’t spot them all, but it’s a consistent practice within the Ubuntu leadership team: our values are more important than winning or losing any given debate.

Do not be drawn into a tribal argument on Ubuntu’s behalf

Right now, for a number of reasons, there is a fever pitch of tribalism in plain sight in the free software world. It’s sad. It’s not constructive. It’s ultimately going to be embarrassing for the people involved, because the Internet doesn’t forget. It’s certainly not helping us lift free software to the forefront of public expectations of what software can be.

I would like to say this to everyone who feels associated with Ubuntu: hold fast to what you know to be true. You know your values. You know how hard you work. You know what an incredible difference your work has made. You know that you do it for a complex mix of love and money, some more the former, others the more latter, but fundamentally you are all part of Ubuntu because you think it’s the most profound and best way to spend your time. Be proud of that.

There is no need to get into a playground squabble about your values, your ethics, your capabilities or your contribution. If you can do better, figure out how to do that, but do it because you are inspired by what makes Ubuntu wonderful: free software, delivered freely, in a way that demonstrates real care for the end user. Don’t do it because you feel intimidated or threatened or belittled.

The Gregs are entitled to their opinions, and folks like Jono and Dylan have set an excellent example in how to rebut and move beyond them.

I’ve been lucky to be part of many amazing things in life. Ubuntu is, far and away, the best of them. We can be proud of the way we are providing leadership: on how communities can be a central part of open source companies, on how communities can be organised and conduct themselves, on how the economics of free software can benefit more than just the winning distribution, on how a properly designed user experience combined with free software can beat the best proprietary interfaces any day. But remember: we do all of those things because we believe in them, not because we want to prove anybody else wrong.

University Website

2010-07-30T04:00:00Z

Thoughts and rambling on the X protocol

2010-07-30T13:41:46Z

Two years ago, while working on awesome, I joined the Freedesktop initiative to work on XCB. I had to learn the arcane of the X11 protocol and all the mysterious and old world that goes with it.

Now that I've swum all this months in this mud, I just feel like I need to share my thoughts about what become a mess over the decades.

When I was unborn…

…the Toto band were releasing their song "Africa" and some smart guys were working on a windowing system: the X Window System (this is its full name) which therefore has a (too) long history. The latest version of its protocol, the 11th one, has been designed in the 80's. You can learn more about the history in the Wikipedia article about X.

In 2010, we still listen disco music and we still use various protocols designed in the 80's and even before X. Music have evolved, protocols have evolved, and so did X11.

The problem is that X11 did not evolve that well. The guys at MIT-and-some other-places-with-very-smart-people-in-it created X version 1 in 1984, and updated it until X version 11 (the one we're still using) in 1987. Eleven version in 3 years, that was following the "release early, release often" model. But I don't know why, it just stopped to happen for the last 23 years¹.

I don't know what changes have been made in the first 11 major versions of the X protocol, but I'm rather sure we should have deserve a couple of major version updates this last 2 decades.

In my humble opinion, X11 was not designed to live 23 years. But hey, I'm not blaming anyone here: I was 4 years old and playing Lego ® when they released this latest version of the X protocol, so there is little chance I'd have done something better.

1. That's not totally true: they added (and then deprecated) many extensions.

We won't fix. We'll work-around.

That is probably one of the guideline of the X protocol for the last years. And don't misread me: I'm not bashing anyone thereafter.

Since the X11 protocol was aging, the X guys started to add extensions. They added tons of them over the years. This, in application of one of the early principles of X:

It is as important to decide what a system is not as to decide what it is. Do not serve all the world's needs; rather, make the system extensible so that additional needs can be met in an upwardly compatible fashion.

All of them with no exception were added because, bad luck, the X11 protocol did not anticipated the things that happened in the last 23 years, like video, OpenGL, multiple monitors, or the pleasure to draw oval windows. Some of this extensions are still in use, while some of them have been dropped.

While this is not a bad thing to extends the protocol, it seems like a bad thing to try to fix the protocol with for example the XFixes extension, even with all the good intentions Keith Packard might have in his greatness.

Actually it's even worst than you think

The X11 protocol (without extensions) defines about 120 types of requests: create a window, move a window, etc.

Nowadays, there's at least 25 % of them which are useless: usage of server-side font, or the drawing of squares and polygon, are unused by any modern application or toolkit. All of this is superseded by requests from extensions, like the XRender one.

The handling of multiple monitors displays has totally been screwed up. X11 has been designed to work in Zaphod mode (independent monitors). But Xinerama, and nowadays XRandR have replaced it up: recent X servers (released after ~2007) does not support Zaphod mode anymore, even if it's a core piece of the X11 protocol.

Worst: on many requests, there's limitation or design flaws, like described in this document: Why X Is Not Our Ideal Window System by DEC researchers.

We'll add more broken standard on top of that

Following its early principle, X does not define policies but only mechanisms, which seems like a good thing,

Consequently, people started writing specifications to determine a number of stuff and dogmas: ICCCM. That was 22 years ago in 1988. It's useless to add that many things in this specification are now obsolete, useless, or that it misses many modern stuff.

I was not the only one to think that. The people from what will be the major desktop environments, KDE and GNOME, saw that too in the 90's while I was learning to count. So they wrote EWMH, another standard that comes on top of ICCCM and extends it with nifty features like maximization, full screen mode, etc.

The problem is that this standard has also been written by narrow-minded people who at that time, were working on GNOME or KDE (and maybe others). This desktop environments were having and still have some strong concepts of how should work a desktop: "it should have work-spaces", "a window is only on one workspace", "we only see a workspace at a time", "you do not have multiple screens", etc.

Dude, we don't care: we have toolkits!

This vision of how the desktop should work have now been written in marble in all applications and libraries implementing EWMH, like GTK+ or Qt.

Nowadays, everybody forgot about all of this standards. Toolkits have implemented this, circumvented the X11 protocol limitation and flaws, and nobody wants to look back.

Like all standards, obviously some people implemented them badly. This had some side effects, like OpenOffice acting like a pager.

We don't look back? Worst, we forgot where we came from!

With all these layers of bad designed standards, the desktop continued to evolve for more than a decade. They continued to add more standard, the more recent ones being based on D-Bus like the Desktop Notification Specification or the latest Status Notifier Specification developed by KDE.

The Status Notifier is a new implementation of the good old system tray based on XEmbed, using D-Bus instead of the X11 mechanisms, and adding the possibility to show the system tray with something else than icons.

This specification draft saw an important issue and design flaw raised by Wolfgang Draxinger in this thread on the XDG mailing-list. What Wolfgang points out, is that X is network-oriented, and D-Bus is not. Therefore, making the Status Notifier specification to use D-Bus to pass system tray messages around is a bad idea, since running a X application from host A on host B will draw the system tray on the wrong host!

Apparently, reading the thread, this does not fear some of the KDE people:

of course this is a bizarre corner case not worth much thought. at least that's what you'll think until you actually run into it yourself (be it because you are testing something or because you are setting up some weird kiosk environment).

What Oswald describes as a corner case is an actual common use case for many of us. Of course, YMMV.

From my point of view, this is a step back in the wrong direction. But we can conclude that the network part of X is now worthless, to at least KDE.

I used to believe in XCB

When I joined Freedesktop, it was to work on XCB, the X C Binding. XCB is a nice, clean, 21st century technology based API to play with the X11 protocol. Its code is auto generated based on XML file describing the protocol.

In comparison, Xlib is 80's obfuscated code with almost no comments and hard-coded things. Only a few people can understand some of its corner like its i18n or XKB implementations. And all its code is synchronous.

For people not knowing it yet, X is a network protocol where you send request (like a GET in HTTP) and then get a response. Xlib forces the application to wait for the reply to its request, so the application is blocked until the X server sends the reply to the request. XCB on the other hand does not block and allows the application to send a batch of requests, do some other stuff in the mean time, and then gets the replies.

It's like your Web browser would send one request at a time to a Web server, and would wait until you downloaded all the images one by one to display the page.

In cases where X and all its clients are on the same host, the latency is small and not really visible, therefore the gain for XCB to be asynchronous is small. On slow network however, the gain can be huge, as proved in the rewrite of xlsclients with XCB by Peter Harris.

One of the long standing goal of the XCB folks is to kick-out Xlib, to increase speed and hides latency in X11 applications. That requires to port many libraries, because almost none of them (Cairo being an exception) supports XCB.

From where I stand, I don't really see if the work is worth it now. The desktop world is trusted by GNOME and KDE, meaning GTK+ and Qt. It seems none of this toolkits are interested to work on XCB, neither on the X protocol. They probably put hard effort in bypassing X limitation and flaws, and they now sit on top of crap of workarounds and broken-by-design-standard implementation. It seems to me they don't want to go back in the layers and improves things.

They're too high to go back down and they don't see what the gain would be.

Enlightenment with its EFL was the first toolkit to have an XCB back-end with the work of Vincent Torri. Unfortunately, the back-end is not maintained and nobody cares about it. Last time I tried it, it did not compile at all.

X12 ?

There's a page called X12 on the Freedesktop wiki, listing all the things that should be fixed some days. Unfortunately, the list continues to grow up an no one talks about working on X12.

On the other hand, there's a handset of people trying to work when they will have time on XKB2, the second version of the "let's-try-to-fix-up-the keyboard-part-of-the-protocol-we-wrote-23-years-ago-a-second-time" extension.

To me, it does not seem X12 will happen in the next decade neither.

Alternative ?

Do we got alternative to X ? There's Wayland, but it's far from being usable. There's DirectFB, but that's not very portable. None seems candidate to replace X some days to me.

Anyhow, none of the main toolkits around support this alternative. GTK+ once supported DirectFB, but as far as I know, it is not supported nor works nowadays, as stated by Josselin Mouette. This is why recent versions of the Debian installer have migrated to X for the graphic part, thanks to Cyril Brulebois work.

Conclusion

XCB has been around for more than half-a-decade, and very few people showed interested in it. As far as I can see, nobody is interested to use the X protocol and everybody tries to encapsulate it in some higher-level API as soon as possible to stop seeing it. This leads to poorly written application and toolkits, with a lot of ugly hack.

All of that also means that starting to write applications and graphical toolkits based on XCB would be a very interesting project, but that would lead to spend too much time learning to circumvent the X protocol flaws, things that have been done in years by predecessors like Qt and GTK+.

Major toolkits implementations have almost nothing to win in going back in the dark water of X. I guess most of their folks prefer to work on shiny 3D effects based on your GPS location, rather than redefining better basis for everyone.

The manpower available in the X world is very small. Debian lacking of X maintainers is just the summit of that. There is very smart and very competent and skilled guys in the X world, as you can see by simply reading blog posts on Planet Freedesktop for example (me excluded). Unfortunately, there's not enough of them to cover all the things involved in X: input devices, graphics devices, new protocol extension specification and so on. The X server is really late, and it seems most of the developers prefers to work on the server itself than on the protocol behalf. Which is understandable.

I'm curious to see where all of that will lead in the upcoming years. I've been walking in the X world hallways for about 3 years now, and I feel desktop alternatives to KDE and GNOME will all die sooner or later. The time were you could choose between a dozen "modern" window managers has passed away.

After all, maybe that is simply Darwinism applied to computer software.

Announcing rainbow-mode

2010-07-30T13:41:31Z

While customizing Emacs this last weeks, I had the need to customize also the color theme.

Color themes are always a pain in the ass to edit, because you're supposed to read color strings like #aabbcc and guess what colors they represent.

This is why I wrote rainbow-mode, a minor mode for Emacs that will highlight strings that represents color, using the color they represent.

This support hexadecimal syntax, HTML color name, X color names and rgb() CSS syntax.