vote for next paper (Nov 4 meeting)
Constantin Berzan
It's time to vote for our next paper! I've added two papers to the
list ("Flapjax: A Programming Language for Ajax Applications" and
"Detecting and Escaping Infinite Loops with Jolt"), and if you have
more suggestions, I'd be happy to add them!
Please vote: http://www.doodle.com/m6aubpmuq3aiyqwh
Our next meeting is tentatively scheduled for November 4.
Have a great week!
-Constantin
==============================================================================
Proof of a Program: Find [17p]
Hoare; 1989
Abstract:
A proof is given of the correctness of the algorithm Find. First, an
informal description is given of the purpose of the program and the
method used. A systematic technique is described for constructing the
program proof during the process of coding it, in such a way as to
prevent the intrusion of logical errors. The proof of termination is
treated as a separate exercise. Finally, some conclusions relating to
general programming methodology are drawn.
http://portal.acm.org/citation.cfm?id=63445 (website of the book in
which the essay is contained)
==============================================================================
Dynamo: Amazon’s Highly Available Key-value Store [16p]
DeCandia and other folks from Amazon; 2007
Abstract:
Reliability at massive scale is one of the biggest challenges we face
at Amazon.com, one of the largest e-commerce operations in the world;
even the slightest outage has significant financial consequences and
impacts customer trust. The Amazon.com platform, which provides
services for many web sites worldwide, is implemented on top of an
infrastructure of tens of thousands of servers and network components
located in many datacenters around the world. At this scale, small and
large components fail continuously and the way persistent state is
managed in the face of these failures drives the reliability and
scalability of the software systems.
This paper presents the design and implementation of Dynamo, a highly
available key-value storage system that some of Amazon's core services
use to provide an "always-on" experience. To achieve this level of
availability, Dynamo sacrifices consistency under certain failure
scenarios. It makes extensive use of object versioning and
application-assisted conflict resolution in a manner that provides a
novel interface for developers to use.
http://portal.acm.org/citation.cfm?id=1294281
==============================================================================
Convex partitions with 2-edge connected dual graphs [16p]
Al-Jubeh, Hoffmann, Ishaque, Souvaine, Tóth (Tufts folks!); 2009
Abstract:
It is shown that for every finite set of disjoint convex polygonal
obstacles in the plane, with a total of <em>n</em> vertices, the free
space around the obstacles can be partitioned into open convex cells
whose dual graph (defined below) is 2-edge connected. Intuitively,
every edge of the dual graph corresponds to a pair of adjacent cells
that are both incident to the same vertex.
Aichholzer et al. recently conjectured that given an even number of
line-segment obstacles, one can construct a convex partition by
successively extending the segments along their supporting lines such
that the dual graph is the union of two edge-disjoint spanning trees.
Here we present a counterexamples to this conjecture, with n disjoint
line segments for any n >= 15, such that the dual graph of any convex
partition constructed by this method has a <em>bridge</em> edge, and
thus the dual graph cannot be partitioned into two spanning trees.
http://www.eecs.tufts.edu/~mishaq01/JOCO-2010.pdf
==============================================================================
Plan 9 from Bell Labs [9p]
Pike, Presotto, Thompson, Trickey; 1995
Abstract:
Plan 9 is a distributed computing environment. It is assembled from
separate machines acting as CPU servers, file servers, and terminals.
The pieces are connected by a single file-oriented protocol and local
name space operations. By building the system from distinct,
specialised components rather than from similar general-purpose
components, Plan 9 achieves levels of efficiency, security,
simplicity, and reliability seldom realised in other distributed
systems. This paper discusses the building blocks, interconnections,
and conventions of Plan 9.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.8671&rep=rep1&type=pdf
==============================================================================
Induction of Decision Trees [26p]
Quinlan; 1986
Abstract:
The technology for building knowledge-based systems by inductive
inference from examples has been demonstrated successfully in several
practical applications. This paper summarizes an approach to
synthesizing decision trees that has been used in a variety of
systems, and it describes one such system, ID3, in detail. Results
from recent studies show ways in which the methodology can be modified
to deal with information that is noisy and/or incomplete. A reported
shortcoming of the basic algorithm is discussed and two means of
overcoming it are compared. The paper concludes with illustrations of
current research directions.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.167.3624&rep=rep1&type=pdf
==============================================================================
The Hardness of Cache-Conscious Data Placement [11p]
Petrank, Rawitz, 2002
Abstract:
The growing gap between the speed of memory access and cache access
has made cache misses an in uential factor in program eciency. Much
eort has been spent recently on reducing the number of cache misses
during program run. This eort includes wise rearranging of program
code, cache-conscious data placement, and algorithmic modications that
improve the program cache behavior. In this work we investigate the
complexity of nding the optimal placement of objects (or code) in the
memory, in the sense that this placement reduces the cache misses to
the minimum. We show that this problem is one of the toughest amongst
the interesting algorithmic problems in computer science. In
particular, suppose one is given a sequence of memory accesses and one
has to place the data in the memory so as to minimize the number of
cache misses for this sequence. We show that if P != NP, then one
cannot eciently approximate the optimal solution even up to a very
liberal approximation ratio. Thus, this problem joins the small family
of extremely inapproximable optimization problems. The other two
famous members in this family are minimum coloring and maximum clique.
http://www.cs.tufts.edu/~sguyer/classes/comp150-2006/papers/petrank02hardness.pdf
==============================================================================
On the translation of languages from left to right [33p]
Knuth, 1965
Abstract:
There has been much recent interest in languages whose grammar is
sufficiently simple that an efficient left-to-right parsing algorithm
can be mechanically produced from the grammar. In this paper, we
define LR(k) grammars, which are perhaps the most general ones of this
type, and they provide the basis for understanding all of the special
tricks which have been used in the construction of parsing algorithms
for languages with simple structure, e.g. algebraic languages. We give
algorithms for deciding if a given grammar satisfies the LR (k)
condition, for given k, and also give methods for generating
recognizers for LR(k) grammars. It is shown that the problem of
whether or not a grammar is LR(k) for some k is undecidable, and the
paper concludes by establishing various connections between LR(k)
grammars and deterministic languages. In particular, the LR(]c)
condition is a natural analogue, for grammars, of the deterministic
condition, for languages.
http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf
==============================================================================
Program development by stepwise refinement [13p]
Wirth, 1971
Abstract:
The creative activity of programming - to be distinguished from coding
- is usually taught by examples serving to exhibit certain techniques.
It is here considered as a sequence of design decisions concerning the
decomposition of tasks into subtasks and of data into data structures.
The process of successive refinement of specifications is illustrated
by a short but nontrivial example, from which a number of conclusions
are drawn regarding the art and the instruction of programming.
http://www.ehu.es/~ljrf/AED/2010/practicas/lenguaje_C/StepwiseRefinement_Wirth.pdf
==============================================================================
Garbage Collection in an Uncooperative Environment [17p]
Boehm, Weiser, 1988
Abstract:
We describe a technique for storage allocation and garbage collection
in the absence of significant cooperation from the code using the
allocator. This limits garbage collection overhead to the time
actually required for garbage collection. In particular, application
programs that rarely or never make use of the collector no longer
encounter a substantial performance penalty. This approach greatly
simplifies the implementation of languages supporting garbage
collection. It further allows conventional compilers to be used with a
garbage collector, either as the primary means of storage reclamation,
or as a debugging tool.
Our approach has two potential disadvantages. First, some garbage may
fail to be reclaimed. Second, we use a ‘‘stop and collect’’ approach,
thus making the strategy unsuitable for applications with severe
real-time constraints. We argue that the first problem is, to some
extent, inherent in any garbage collection system. Furthermore, based
on our experience, it is usually not significant in practice. In spite
of the second problem, we have had favorable experiences with
interactive applications, including some that use a heap of several
megabytes.
http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
==============================================================================
Automated re-invention of six patented optimal lens systems using
genetic programming [8p]
Koza, 2005
Abstract:
This paper describes how genetic programming was used as an invention
machine to automatically synthesize complete designs for six optical
lens systems that duplicated the functionality of previously patented
lens systems. The automatic synthesis was done "from scratch"-that is,
without starting from a pre-existing good design and without
pre-specifying the number of lenses, the physical layout of the
lenses, the numerical parameters of the lenses, or the non-numerical
parameters of the lenses. One of the six genetically evolved lens
systems infringed a previously issued patent; three contained many of
the essential features of the patents, without infringing; and the
others were non-infringing novel designs that duplicated (or improved
upon) the performance specifications contained in the patents. One of
the six patents was issued in the 21st-century. The six designs were
created in a substantially similar and routine way, suggesting that
the approach used may have widespread utility. The genetically evolved
designs are instances of human-competitive results produced by genetic
programming in the field of optical design.
http://portal.acm.org/citation.cfm?id=1068337
==============================================================================
Demonstrating the Evolution of Complex Genetic Representations: An
Evolution of Artificial Plants [12p]
Toussaint, 2003
Abstract:
A common idea is that complex evolutionary adaptation is enabled by
complex genetic representations of phenotypic traits. This paper
demonstrates how, according to a recently developed theory, genetic
representations can self-adapt in favor of evolvability, i.e., the
chance of adaptive mutations. The key for the adaptability of genetic
representations is neutrality inherent in non-trivial
genotype-phenotype mappings and neutral mutations that allow for
transitions between genetic representations of the same phenotype. We
model an evolution of artificial plants, encoded by grammar-like
genotypes, to demonstrate this theory.
http://www.springerlink.com/content/ad524w1bvpvbjyh7/fulltext.pdf
==============================================================================
You and Your Research
Hamming (transcribed), 1986
Abstract:
At a seminar in the Bell Communications Research Colloquia Series, Dr.
Richard W. Hamming, a Professor at the Naval Postgraduate School in
Monterey, California and a retired Bell Labs scientist, gave a very
interesting and stimulating talk, You and Your Research to an overflow
audience of some 200 Bellcore staff members and visitors at the Morris
Research and Engineering Center on March 7, 1986. This talk centered
on Hamming's observations and research on the question ``Why do so few
scientists make significant contributions and so many are forgotten in
the long run?'' From his more than forty years of experience, thirty
of which were at Bell Laboratories, he has made a number of direct
observations, asked very pointed questions of scientists about what,
how, and why they did things, studied the lives of great scientists
and great contributions, and has done introspection and studied
theories of creativity. The talk is about what he has learned in terms
of the properties of the individual scientists, their abilities,
traits, working habits, attitudes, and philosophy.
http://www.cs.virginia.edu/~robins/YouAndYourResearch.pdf
==============================================================================
Flapjax: A Programming Language for Ajax Applications
Meyerovich, Guha, Baskin, Cooper, Greenberg, Bromfield, Krishnamurthi, 2009
Abstract:
This paper presents Flapjax, a language designed for contemporary Web
applications. These applications communicate with servers and have
rich, interactive interfaces. Flapjax provides two key features that
simplify writing these applications. First, it provides event streams,
a uniform abstraction for communication within a program as well as
with external Web services. Second, the language itself is reactive:
it automatically tracks data dependencies and propagates updates along
those dataflows. This allows developers to write reactive interfaces in
a declarative and compositional style.
Flapjax is built on top of JavaScript. It runs on unmodified browsers
and readily interoperates with existing JavaScript code. It is usable
as either a programming language (that is compiled to JavaScript) or
as a JavaScript library, and is designed for both uses. This paper
presents the language, its design decisions, and illustrative examples
drawn from several working Flapjax applications.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.5404&rep=rep1&type=pdf
==============================================================================
Detecting and Escaping Infinite Loops with Jolt
Carbin, Misailovic, Kling, Rinard, 2011
Abstract:
Infinite loops can make applications unresponsive. Potential problems
include lost work or output, denied access to application
functionality, and a lack of responses to urgent events. We present
Jolt, a novel system for dynamically detecting and escaping infinite
loops. At the user’s request, Jolt attaches to an application to
monitor its progress. Specifically, Jolt records the program state at
the start of each loop iteration. If two consecutive loop iterations
produce the same state, Jolt reports to the user that the application
is in an infinite loop. At the user’s option, Jolt can then transfer
control to a statement following the loop, thereby allowing the
application to escape the infinite loop and ideally continue its
productive execution. The immediate goal is to enable the application
to execute long enough to save any pending work, finish any in-progress
computations, or respond to any urgent events.
We evaluated Jolt by applying it to detect and escape eight infinite
loops in five benchmark applications. Jolt was able to detect seven of
the eight infinite loops (the eighth changes the state on every
iteration). We also evaluated the effect of escaping an infinite loop as
an alternative to terminating the application. In all of our benchmark
applications, escaping an infinite loop produced a more useful output
than terminating the application. Finally, we evaluated how well
escaping from an infinite loop approximated the correction that the
developers later made to the application. For two out of our eight
loops, escaping the infinite loop produced the same output as the
corrected version of the application.
http://people.csail.mit.edu/rinard/paper/ecoop11.pdf
==============================================================================