Arun Ramachandran presents Linearizability: A Correctness Condition for Concurrent Objects, by Maurice P. Herlihy and Jeannette M. Wing.
How can we create the illusion that an abstract data type is modified one operation at a time, when in fact we have several concurrent processes? The answer lies in linearizability. It's a correctness condition whereby we can enforce upon the pre-conditions and post-conditions of an abstract data type as if it were operated on by a single sequential process.
Arun has studied concurrent data structures. His research is heavily based upon the work of Herlihy. Let's get his take on this paper.
Ever walk out of a movie and go "How did they do that special effect!?" Well it's not magic, just MATH! (lots and lots of math) Addition, Multiplication, Subtraction, its all in there! Come see how the math is done and how this cool algorithm work when we talk about "The Rendering Equation" by James Kajiya (coincidentally presented first, at a Dallas SIGGRAPH conference - Get the paper) You might even see some teapots, boxes, flashlights and puppets.
Michael will cover a paper that raised the eyebrows of many observers of cryptography theory.
"A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic"
What a fun title! This paper talks about a way to reduce the complexity of the Discrete Logarithm Problem (DLP) in certain situations. DLP is finding the inverse of the equation that sits at the foundation of both the Diffie Hellman and RSA crypto algorithms. These algorithms are at the heart of Internet security.
This paper is really just an excuse to geek out about asymmetric cryptography. We'll go over the Diffie Hellman and RSA algorithms in some detail, and see why a solution to the DLP would be so upsetting.
Don't use your browser until you read this paper! (Well, OK. You can use it.)
Paxos has become a standard by which other consensus systems in distributed computing are compared. Let's all get a basic shared understanding from which we can move forward.
We'll study Paxos Made Simple. Written by Leslie Lamport (of Time, Clocks, and the Ordering of Events in a Distributed System), this is an extremely approachable paper.
PDF: Get the paper
This will be a group activity, so please spend a few minutes with the paper beforehand. We would love your input!
Dal Jeanis will present Scott Downey and Jeff Sutherland's paper on Scrum Metrics. This is a practice based not on anecdotal evidence, but on hard numbers. We can actually compute the performance of a team, and use those metrics to improve efficacy.
This month we are changing things up a bit. Please join us at ThoughtWorks and at a later time in the month. Please let us know if the time and venue work better for you.
Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
Michael Perry will present a discussion on causal consistency in a distributed system. With this concept, a distributed system achieve:
• Low latency
• High availability
• Partition Tolerance
Most systems that do so sacrifice consistency (liniearizability of events) for eventual consistency. But this paper seeks a lesser compromise, which can easily detect and resolve conflicts.
As an added bonus, before the primary discussion, Dal will present a lightning talk on boosting of machine learning algorithms.
Cellular Automata apply simple rules to simulate complex systems. Stephen Wolfram has invented "A New Kind of Science" to study these machines, and determine how we can use them to understand the natural world.
Nik Clarkson will guide us through one of Wolfram's early papers on the subject. He takes a fresh approach to the problem, in which he first tries to achieve the same results as nature, and then tries to walk back to an understanding of the governing laws.
How do they put a giant robot right in the middle of an outdoor shot in a movie? How do they get the light from its environment to reflect off its surface? And how do they make it cast a shadow on nearby objects in the shot?
In many ways, an image that is purely artificial is easier to generate. But when the real world and the digital world collide, magic happens. We can put fantasy within the context of everyday life. But this is not easy. Let's explore some of the techniques for making this happen.
Adam Hill has attended several SIGGRAPH conventions in the past. He applies his knowledge and passion for digital imagery to business app and game development alike. He will guide us on this fascinating journey.
Programming languages are designed to solve real problems. C++ was designed to represent days structures and the operations that act upon them. See the thought process that went into the design of the language by exploring a common days structure, the stack.
Come explore 16 ways to solve this problem in C++, from the man who designed the language, presented by one of his students. This is a pragmatic look into data structures, language design, and problem solving.
What does it mean for one event to occur before another? In the real world, special relativity shows us that the limit for "before" and "after" is the speed of light. What is it in the digital world? And how does user perception influence the correctness of a distributed system?
Let's study Leslie Lamport's award winning paper, "Time, Clocks, and the Order of Events in a Distributed System." He lays the ground work for years of research in distributed computing.
There are several fascinating works based on this, one of the most cited papers in computer science. Come join me in forming a solid foundation for other great papers to come.
We will review the paper Extensible Records with Scoped Labels, by Daan Leiden.
Michael Perry will present the paper and lead a discussion. Please read the paper ahead of time, so we can all benefit from your viewpoint.
To read an academic paper:
• Read the abstract
• Read the conclusion
• Scan the outline
• Skim the article, skipping equations and proofs
• Dive in to the parts that interest you most
It helps to write out the outline on a separate page, and then summarize the sections as you skim them.