The other day a non-CS friend remarked to me that since computer science is a quantitative, technical discipline, most issues probably have an obvious objective truth. Of course this is not at all the case, and it is not uncommon to find major disagreements even when all parties are apparently reasonable and acting in good faith. Sometimes these disagreements spill over into the public space.
The purpose of this post is to list a collection of public debates in academic computer science where there is genuine and heartfelt disagreement among intelligent and accomplished researchers. I sometimes assign these as reading in class: they are a valuable resource for a couple of reasons. First, they show an important part of science that often gets swept under the rug. Second, they put discussions out into the open where they are widely accessible. In contrast, I’ve heard of papers that are known to be worthless by all of the experts in the area, but only privately — and this private knowledge is of no help to outsiders who might be led astray by the bad research. For whatever reasons (see this tweet by Brendan Dolan-Gavitt) the culture in CS does not seem to encourage retracting papers.
- N-version programming is a software development method where several implementations of a specification are run in parallel and voting is used to determine the correct result. Knight and Leveson wrote a paper showing that the assumption of independent faults in independent implementations may not be a good one. This finding did not sit well with the proponents of n-version programming and while I cannot find online copies of their rebuttals, Knight and Leveson’s reply to the criticisms includes plenty of quotes. This is great reading, a classic of the genre.
- Starting in the late 1980s, Ken Birman’s group was advocating causal and totally ordered multicast. Cheriton and Skeen were less than impressed and wrote 15 pages to that effect. Then we have Birman’s 32-page response to the criticisms. Also see Neha Narula’s take on the debate.
- This 1991 paper introduced log-based filesystems. In 1993 Seltzer et al. published this paper describing and evaluating an implementation of a log-based filesystem, and this followup in 1995. John Ousterhout, one of the authors of the original paper, disagreed with the evaluation. Seltzer and her coauthors rebutted his critique, and Ousterhout had, as far as I know, the last word.
- Linus v Tanenbaum on the merits of microkernels is another classic. Also see some (one-sided) comments on a reincarnation of the debate here. Related, Hand et al. published a paper Are Virtual Machine Monitors Microkernels Done Right?; in response, Heiser et al. wrote a paper with the same title but coming to the other conclusion.
- Social Processes and Proofs of Theorems and Programs is a provocative opinion piece about the role of formal methods in software development. Dijkstra called it “a very obnoxious paper” (see page 14 of this transcript) and wrote a response called “On a Political Pamphlet from the Middle Ages.” DeMillo et al. replied: “We must begin by refusing to concede that our confidence in a piece of real software has ever been increased by a proof of its correctness…” See the letters to the editor of CACM responding to this article, Victor Yodaiken’s take on this debate, and also three more shots fired in 2010, two by Moshe Vardi and one by the original paper’s authors.
- Sticking with Dijkstra, he and John Backus had a (only partially public) spat, nicely written up here.
I’d like to fill any holes in this list, please leave a comment if you know of a debate that I’ve left out!
Here are some more debates pointed out by readers:
- Software-based attestation offers a protocol for checking that a remote system contains the memory image that we expect it to have. On the Difficulty of Software-Based Attestation of Embedded Devices presents concrete attacks on SWATT. Perrig and van Doorn did not agree that the attacks were valid and, finally, Francillon et al. responded to the refutation.
- See the debate about code pointer integrity, links in comment #1
- See the debate about automated program repair, links in comment #2
- See the debate about the Java memory model, links in comment #4
- Go-to Statement Considered Harmful,
Goto Considered Harmful Considered Harmful, and
Goto Considered Harmful Considered Harmful Considered Harmful (several different letters in this PDF, and sorry about the paywall)
26 responses to “Vigorous Public Debates in Academic Computer Science”
A recent one from the security world: “Code Pointer Integrity” (OSDI ’14) [1] was attacked by “Missing the Point(er)” (Oakland ’15) [2]; the authors of the former thought the latter was a bit of a cheap shot*, and published “Getting The Point(er)” as a poster [3].
Secretly, I assume they did it all so they could make those pointer jokes in the titles.
* Note: I’m putting words in their mouths here for dramatic effect.
[1] http://dslab.epfl.ch/pubs/cpi.pdf
[2] https://people.csail.mit.edu/rinard/paper/oakland15.pdf
[3] http://dslab.epfl.ch/pubs/cpi-getting-the-pointer.pdf
“Program repair,” introduced with GenProg, takes off in 2011: https://qosbox.cs.virginia.edu/~weimer/p/weimer-tse2011-genprog-preprint.pdf
In 2015, Rinard’s lab lists (somewhat shocking) methodological deficiencies in the whole area GenProg begat: http://people.csail.mit.edu/rinard/paper/issta15.pdf
Another contemporaneous claim that the whole thing may have been broken all along: https://people.cs.umass.edu/~brun/pubs/pubs/Smith15fse.pdf
I haven’t seen a rebuttal from Forrest, Weimer, et al., but I’d love to read one!
About the “Social Processes and Proofs of Theorems and Programs”, see also Moshe Vardi’s opinion: http://cacm.acm.org/magazines/2010/1/55739-more-debate-please/fulltext where he concludes that “with hindsight of 30 years, it seems that [the Social Processes paper] has proven to be rather misguided”. In the same page the reply by the authors of the original paper who “completely disagree with Vardi’s assessment”.
ARITH23 “Special Session: The Great Debate: John Gustafson and William Kahan” (about IEEE floating point vs Unum arithmetic). I think it is interesting that a conference has hosted a debate like this with both sides exposing their arguments.
Slides: http://arith23.gforge.inria.fr/slides/Gustafson.pdf http://arith23.gforge.inria.fr/slides/Kahan.pdf
Video of debate: https://youtu.be/LZAeZBVAzVw
Work on the Java Memory Model amounted to a decade-long ongoing public… discussion. Unlike many of the other debates on this page, the root cause wasn’t so much philosophical differences, but rather the sheer (and often subtle) complexity of the problem being tackled.
Steele et al published the original JMM spec in ’96 as part of the Java Language Specification.
Pugh notes, in 2000, that “The Java memory model described in Chapter 17 of
the Java Language Specification […] is hard to interpret and poorly understood; […] Guy Steele (one of the authors of [GJS96]) was unaware that the memory model prohibited common compiler optimizations, but after several days of discussion at OOPSLA98 agrees that it does.”
http://www.cs.tufts.edu/comp/150IPL/papers/pugh00java.pdf
Manson, Pugh, and Adve published a revised JMM spec at POPL 2005. They write “the new model […] clearly defines the boundaries of legal transformations.”
http://rsim.cs.uiuc.edu/Pubs/popl05.pdf
In 2007, Cenciarelli et al publish a paper with a counterexample to Theorem 1 from the POPL 2005 paper, demonstrating that reordering of independent statements is not permissible:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.6162&rep=rep1&type=pdf
Aspinall and Å evÄÃk published a paper in 2007 with example programs highlighting “good, bad and ugly” behavior properties of the JMM and follow up in 2008 with another paper: “we find that commonly used optimisations, such as common subexpression elimination, can introduce new behaviours and so are invalid for Java.”
http://groups.inf.ed.ac.uk/request/jmmexamples.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf
I’m also a fan of the whole line of “stack vs. heap for continuations” arguments:
e.g., the citation graph around https://www.cs.princeton.edu/~appel/papers/stack2.pdf
I think there’s still a bunch more to say here, especially around CPU prediction hardware that sort of assumes your behavior has things that look like stack frames.
This might be too broad/vague for your list here, but I find it intriguing that in programming languages the dynamic versus typed debate has continued for decades. To me, the fact that such a disagreement has gone on for so long with smart people on both sides almost certainly means that neither Pareto dominates the other. But there are smart people willing to argue that such dominance is in fact the case. Bob Harper’s blog has some interesting discussion threads on the topic.
Not exactly the same thing but; there are a number of intersections of CS and public policy (particularly around security) that seem to have a lot of active debate. However that tends towards the opinions being aligned with if the speaker is coming at it from CS or public policy.
Awesome links, folks, thanks!
Also the debate between John Ousterhout and Margo Seltzer about latter’s log-structured file system. https://www.eecs.harvard.edu/margo/papers/usenix95-lfs/supplement/ouster_critique2.html
While not exactly a debate — more of a fundamental difference in outlook — these are interesting, completely opposite claims:
Bob Harper[1]:
> There is an alternative… without… reference to an underlying machine… [W]e adopt a linguistic model of computation, rather than a machine model, and life gets better! There is a wider range of options for expressing algorithms, and we simplify the story of how algorithms are to be analyzed.
Leslie Lamport[2]:
> Thinking is not the ability to manipulate language; it’s the ability to manipulate concepts. Computer science should be about concepts, not languages. … State machines… provide a uniform way to describe computation with simple mathematics. The obsession with language is a strong obstacle to any attempt at unifying different parts of computer science.
[1]: https://existentialtype.wordpress.com/2011/03/16/languages-and-machines/
[2]: http://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf
Some long running debates (CTL vs LTL for model checking logics) do not really have a great paper trail that I recall.
Re: linear vs. branching temporal logics (LTL vs. CTL), Vardi (who is not one to shy away from vigorous debates 🙂 has written a great summary http://www.cs.rice.edu/~vardi/papers/etaps01-ver13.pdf
The relational vs network model debate in the late 70s was a turning point in data management.
http://diaswww.epfl.ch/courses/adms07/papers/roots.pdf
https://mitpress.mit.edu/sites/default/files/titles/content/9780262693141_sch_0001.pdf
I think Moshe would not mind if I said that he was one to run, as quickly as is possible while maintaining dignity and decorum, to vigorous debate!
Despite coming from the CMU Ed Clarke camp, I have no dog in this fight: the model checkers I’ve implemented have mostly supported LTL, but in practice I’ve almost always model checked systems for safety properties — in fact, just assertion violations.
Re: GenProg/automatic program repair: speaking only for myself (not having consulted with my coauthors before posting), I go back and forth between thinking a specific response to the ISSTA ’15 paper in particular might be warranted, and thinking (as I do right now as I type) that the ongoing, vigorous, peer-reviewed, academic conversation between multiple groups and authors (not just Rinard and the original GenProg team) allows the science of patch generation to advance as all good science does: via replication, further investigation, and the advancement/proposal of both new techniques and methods to evaluate them (as in, for example, FSE ’15).
(All hallmarks of a good and interesting scientific debate, in my opinion!)
(Bah can’t edit. I meant to say: “Rinard et al.”, not just Rinard.)
The debate around whether or not causally and totally ordered communication support (CATOCS) violates the end-to-end principle was a very public debate. This timeless argument about the role of the network in distributed system design is continuously re-evaluated by the community.
Understanding the limitations of causally and totally ordered communication
http://dl.acm.org/citation.cfm?id=168623
A response to Cheriton and Skeen’s criticism of causal and totally ordered communication
http://dl.acm.org/citation.cfm?id=164858
End-to-end arguments in system design
http://dl.acm.org/citation.cfm?id=357402
“The other day a non-CS friend remarked to me that since computer science is a quantitative, technical discipline, most issues probably have an obvious objective truth.”
This suddenly struck me as a somewhat bizarre statement in that a considerable chunk of even the academic CS literature is basically flamewars over which programming languages are good/bad/the-spawn-of-the-dark-one.
(Not bizarre for a non-CS person to make, just rather funny in that the feeling other people are horribly wrong, without a great way to prove it, has been a key part of CS since early days).
You forgot the Random Oracle controversy –see Sec. 3 in:
http://web.cs.ucdavis.edu/~rogaway/papers/cc.pdf
(Edit: I meant Sec. 5, not 3)
You forgot the Random Oracle controversy –see Sec. 5 in:
http://web.cs.ucdavis.edu/~rogaway/papers/cc.pdf
In the goto debate, there was also Knuth’s “Structured Programming with goto Statements”: http://web.archive.org/web/20130731202547/http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
Personally, I thought it was the most nuanced treatment of the issue.
SQL vs noSQL?
There was a fairly fierce debate in DB about MapReduce vs traditional DBMS that started with a fireball thrown by DeWitt and Stonebraker back in 2008. This paper from 2011 recounts some of the discussion.
https://www.cs.arizona.edu/~bkmoon/papers/sigmodrec11.pdf
In the HCI community there was a debate on usability evaluation.
Usability Evaluation Considered Harmful (Some of the Time), Greenberg and Buxton, CHI 2008.
http://dl.acm.org/citation.cfm?id=1357074
http://www.billbuxton.com/usabilityHarmful.pdf
http://slideplayer.com/slide/4800439/