Important Software Engineering papers

Some of the must read in software architecture and design.

• Threads cannot be implemented as a library [link]
  Proceedings of the 2005 ACM SIGPLAN conference
  
  Or "Why Java is better than C++"... for the moment at least. Since the Java Memory Model takes care of the issues raised in the papers above. However C++ will get it's own memory model in the next version of it's standard, C++0x.
  
  
• Data abstraction and Hierarchy [link]
  Proceedings of OOPSLA 1987 Conference
  
  From this we get that famous Liskov Substitution Principle, which is in summary a statement of the below,

Let q(x) be a property provable about objects x of type T. Then q(y) should be true for objects y of type S where S is a subtype of T.

The paper also discuss why inheritance violates encapsulation in 3 possible ways.

• Multiple Dispatch in Practice [link]
  Proceedings of OOPSLA 2008 Conference
  
  A good survey/introduction to the multiple dispatch technique. This has important applications in say, network event handling code that performs callbacks based on type of message received.
  
  
• Wait-Free Synchronization [link]
  Proceedings of ACM Transactions on Programming Languages and Systems 1991.
  
  Paper lays the foundation for much of the recent developments and renewed interest in wait-free/lock-free concurrency. It proves that it is "impossible to construct a wait-free implementation of a queue, stack, priority queue, set, or list from a set of atomic readl/write registers." This is done by reduction to a consensus number. FIFO queues for example have consensus number 2 and hence it can be implemented using compare-and-swap atomic instructions, which have the same consensus number.
  
  On an interesting side-note, consensus is in itself an intriguing problem. In fact, consensus in distributed computing is undecidable. The paper "Easy impossibility proofs for distributed consensus problems" with the famous result can be found here.
  
  
  
• Software Transactional Memory [link]
  Distributed Computing. Volume 10, Number 2. February 1997.
  
  The landmark paper describing a software transactional approach to concurrent shared memory. This is an attempt to deviate from the conventional approach of using locks with the aim of overcoming the many shortcomings of lock based concurrency.
  
  
  
• MapReduce: Simplified Data Processing on Large Clusters [link]
  Proceedings of Operating Systems Design and Implementation 2004.
  
  This paper introduces Google's famous MapReduce framework for distribution processing of large data. It's simplicity is just truly amazing and beautiful.
  
  
  
• Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services [link]
  ACM SIGACT News, v. 33 issue 2, 2002, p. 51-59.
  
  A formal proof of the famous CAP (Consistent, Available, Partition-Toleranct) conjecture given by Eric Brewer in his Invited Talk "Towards robust distributed systems" in PODC 2000. In short it says that it's IMPOSSIBLE for a web service to provide Consistency, Availability and Partition-Tolerance.