Excecise 109
XinQiao Wang
i am scratching my head very hard trying to work out a counterexample
(i.e. a non-linearizable trace) for the OptimisticList algorithm (in
Chapter 9) under the condition that the `contain()' method uses no
locks.
i believe there should be one since the later LazyList algorithm is
proposed as an improvement over OptimisticList by offering a wait-free
`contain()'.
However, i fails to find any despite some hard time. Did i miss
something obvious or it is true that the OptimisticList algorithm with
a `lock-less' `contain()' method is still linearizable?
Anyone (esp. Maurice) can help?
Best wishes,
Wang
Maurice Herlihy
contains returns false. Analyze each.
Maurice
Maurice Herlihy
Professor
Computer Science
Brown University
Doug Lea
First Workshop on Curricula in Concurrency and Parallelism (OOPSLA 2009)
http://concurrencypedagogy.ning.com/
Important Dates:
* Submission deadline for position papers: August 30, 2009
* Notification of decision: September 14, 2009
* Workshop Date: Monday, October 26
* Submit by mail to vijay at saraswat.org
The concurrency era has exploded on us. Multicore systems are now everywhere --
in our laptops, desktops, graphic cards, video game consoles. Symmetric
multi-processors and clusters dominate the server and high performance computing
market and are the foundation for cloud computing.
There is an urgent need to ensure that newly trained Computer Science graduates
are well versed in the principles and practice of concurrent and parallel
programming. Following a previous successful workshop on Multicore Programming
Education at ASPLOS 2009, this workshop will address several fundamental questions:
* What are the ``fundamental ideas'' of concurrency and parallelism that
every Computer Science graduate should know? That every college graduate should
know?
* Should concurrency and parallelism be taught ``top-down'' (via high-level
abstractions such as operations on collections) or bottom up (with low-level
tools such as threads and locks)?
* Should sequential programming be taught as a ``special case'' of
concurrent and parallel programming?
* Should concurrency and parallelism issues be addressed in introductory
computer science courses?
* Should concurrency and parallelism topics be ``sprinkled'' in existing
courses (e.g. in architecture, systems, programming languages, algorithms) -- if
so which topics in those courses should be taken out to make room? Should these
topics be taught in their own separate stream?
This workshop aims to bring together practitioners and thinkers to address this
topic. In keeping with OOPSLA traditions, we seek a diverse group of
participants -- educators, researchers, practitioners, students, authors -- with
varied background, experience and approaches, for what we hope will be a
stimulating discussion. It will be organized around the presentation of position
papers selected by the PC, and a panel discussion. The results of the workshop
will be made available online at http://concurrencypedagogy.ning.com
Potential participants are invited to submit 2-page position papers addressing
these topics, for consideration by the Program Committee. Please submit by email
to vijay at saraswat.org
The paper should address the authors' experience and thoughts on this topic, and
raise questions that they would like to see discussed at the workshop. In the
case of educators we are particularly interested in understanding how your
academic department is organizing as a whole to address these pedagogical issues.
Program Committee
* Guy Blelloch, Carnegie-Mellon University
* Kim Bruce, Pomona College
* Shriram Krishnamurthi, Brown University
* Tim Mattson, Intel Corporation
* Vijay Saraswat, IBM Corporation (co-chair)
* Michael L. Scott, University of Rochester
* Guy L. Steele, Jr Sun Microsystems (co-chair)
* Kathy Yelick, UC Berkeley and NERSC
