letters to the editor
DOI: 10.1145/1941487.1941489

Preserve Privacy in statistical Correlations

Many thanks for Cyn- thia Dwork’s article “A Firm Foundation for Private Data Analysis” (Jan. 2011), explaining
why, in trying to formalize what is per-
fect privacy, we cannot use the late Uni-
versity of Stockholm economist Tore
E. Dalenius’s criterion that asking al-
lowed queries of a statistical database,
we should not be able to learn new (pri-
vate) information about a particular
individual. When preparing to discuss
Dwork’s article at a recent colloquium
in our computer science department,
we came up with an even simpler expla-
nation of such an impossibility:
One important purpose of collect-
ing statistical data is to help identify
correlations between, say, weight and
blood pressure. Suppose, for exam-
ple, it turns out that blood pressure
is equal to weight, and we know that
person A (not in this database) weighs
180 pounds. Without the database, A’s
blood pressure might be private, but
once we learn the perfect correlation
from it, we can conclude that A’s blood
pressure is 180.

In real life, we never see such perfect correlation, but, by analyzing the database and discovering some correlation, we know more about the probability of different values of blood pressure than we would otherwise know.

Vladik Kreinovich and Luc Longpre,
el Paso, TX
Recall the Lost frontiers
of Virtual Worlds

The Future Tense essay “Rebirth of
Worlds” (Dec. 2010) lamented the de-
mise of historic, online interactive 3D
destinations. Since 1997 when they first
appeared on the Web, virtual worlds
have inspired artists, engineers, and
scientists alike to explore and build the
emerging frontiers of cyberspace. As
Rumilisoun (a.k.a William Sims Bain-
bridge) wrote, despite the wonderful
destinations across entertainment,
education, and community, we are left
to ask, “How can I still get there?”
What came through clearly in “Re-
birth of Worlds” is the author’s nostal-
gia for the experience of those worlds—
their realities and possibilities. Such
compelling emotional, perceptual, ex-
istential content may indeed be gone
for good. Loss of an appealing game
world is lamentable, but it is even more
disheartening with engineering and
scientific content, where we require the
durability and reproducibility of our in-
teractive 3D digital content—models,
behaviors, worlds, and scenarios—for
decades to come.

Let Implementation semantics unlock the Pop The lock-free pop operation Nir Shavit described in his article “Data Structures in the Multicore Age” (Mar. 2011) depends on the semantics of the Java implementation in an important way. The push operation allocates a new node object during the call, and it is this object that is placed on the stack.

In addition, the assignment of old Top at line 13 creates a reference to the top node, keeping it alive until the return from the function.

This is of interest because if any of these constraints is not true, the pop operation would not work. In particular, if one would naively implement a push-and-pop mechanism along these lines in a language like C++, and let the clients provide the object to be pushed, and returned that object to the clients when the pop occurred, the program would be wrong. This is because after fetching oldTop (line 13) and newTop (line 17) other threads could remove the top node, remove or push other nodes, then push the top node again. The compareAnd-Set would then succeed, even though new Top was no longer the correct new value. Similarly, if the implementation allocated a node in push, and freed it in pop, the program would be wrong because the freed-node storage might be reused in a subsequent push, leading to the same error.

The Java implementation also involves hidden costs, including allocation and garbage collection of the node objects and concurrency control required in the memory-allocation system to make it work. These costs must be considered, as they are essential to the correctness of the program. Be warned about not using apparently identical algorithms that do not satisfy the hidden constraints.

marc auslander, yorktown heights, ny

Protect software Consumers
Like everyone else

I regret that Joel F. Brenner responded to my letter to the editor “Hold Manufacturers Liable” (Feb. 2011) concerning his Viewpoint “Why Isn’t Cyberspace More Secure?” (Nov. 2010) with two strawman arguments and one outright misstatement.