Why Concurrent Objects Are Recurrently Complicated

Nir Shavit’s article "Data Structures in the Multicore Age" (Mar. 2011) was a thrill to read; so, too, was the timely Viewpoint "Managing Time" by Peter J. Denning, the article "Understanding Scam Victims: Seven Principles for Systems Security" by Frank Stajano and Paul Wilson, the Technical Perspective "VL2" by Jennifer Rexford, and the article "VL2: A Scalable and Flexible Data Center Network" by Albert Greenberg et al.

I was especially intrigued by Shavit’s exposition on concurrent objects. I first encountered lock-free and wait-free protocols in a 1993 article by Maurice Herlihy,¹ using load-linked and store-conditional instructions. Thanks now to Shavit for explaining additional techniques, including exchangers and balancers.

Also important is to point out that Shavit’s pseudocode for the lock-free stack included an unstated restriction—that a node, once popped, never goes back on the stack—the ABA problem; see the related Communications blog page http://cacm.acm.org/magazines/2011/3/105308-data-structures-in-the-multicore-age/comments, as well as Herlihy’s and Shavit’s 2008 book.²

The key point is that concurrent data structures are more difficult than they might first seem, as I discussed in my own 1995 article³ and that it is easy to introduce subtle bugs, especially when all important assumptions are not stated or enforced; in this case, that a node, once popped, never goes back on the stack.

Joseph P. Skudlarek, Lake Oswego, OR

Back to Top

Origin of SQL

I would like to clarify Erik Meijer’s and Gavin Bierman’s statement concerning the origin of SQL in their article "A Co-Relational Model of Data for Large Shared Data Banks" (Apr. 2011) that said, "The landscape changed radically when Ted Codd proposed a new data model and a structured query language (SQL) based on the mathematical concepts of relations and foreign/primary key relationships." There were actually additional steps and additional people involved getting from Codd’s influential 1970 Communications article "A Relational Model of Data for Large Shared Data Banks" (cited by Meijer and Bierman) to the SQL language. In it and in subsequent articles and papers, Codd discussed query languages based on both relational calculus and relational algebra. But it was Raymond Boyce and Donald Chamberlin who, after studying Codd’s work, defined the SEQUEL language, later renamed SQL, as first documented by Chamberlin and Boyce.⁴ For more on how Codd’s ideas influenced Boyce and Chamberlin and the rest of the System R team, see Chamberlin.⁵

Paul McJones, Mountain View, CA

Back to Top

Back to Top