Syllabus

The items below are tentative. We may add and/or delete items on the list below. What we actually do is subject to change, in part due to the thinking of the enrolled students.

References below to "Textbook" are to the optional book:
Java Concurrency in Practice, Brian Goetz with Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug Lea. Addison-Wesley, 2006.

1. Course introduction
2. Java Remote Method Invocation (RMI)
   • RMI: Hello, world!
   • Java RMI tutorial
   • Java RMI Programmer's Checklist
3. Distributed computing: Some programming language considerations
   • Jim Waldo, Geoff Wyant, Ann Wollrath, and Sam Kendall. A Note on Distributed Computing. SMLI TR-94-29, Sun Microsystems Laboratories, M/S 29-01, 2550 Garcia Avenue Mountain View, CA 94043, November 1994.
4. Functional Programming in Java: 1 Hello, Lambda Expressions! - GitHub
5. Fallacies of Distributed Computing - Fallacies Explained.
6. Design Pattern: Singleton
7. How to Build a Compute Farm
8. Design Pattern: Producer-Consumer
   • BlockingQueue: Textbook: Section 5.3
   • code sample
9. Design Pattern: Remote Proxy
   • A simple chat client/server
     • OOD overview (ppt)
     • Code
10. Performance limits of sequential task decomposition & composition
11. Functional Programming in Java: 2 Using Collections
12. Divide-and-Conquer API
    • The Cilk Project
    • Cilk: An Efficient Multithreaded Runtime System - paper presentation
    • Implementation of the Cilk-5 Multithreaded Language
    • CX: A Scalable, Robust Network for Parallel Computing - paper presentation
    • Work stealing vs. Eager scheduling
13. Distributed Branch-and-Bound
    • Illustrated
    • Generic algorithm
    • A Development and Deployment Framework for Distributed Branch-and-Bound
14. Traveling Salesman Problem: Lower bounds
    • Partial tour
    • (Sum for each vertex of the 2 least cost edges)/2
    • Minimum cost maximum cardinality matching
    • Minimal cost spanning tree
    • 1-tree
    • Held-Karp - a clear explanation (Stack Overflow)
    • Rigorous development of HK algorithm
15. Metric Traveling Salesman Problem: Upper bounds
    • A 2-approximation, using an Eulerian cycle
    • A 1.5-approximation (Christofides), using Eulerian cycle & mini cost max cardinality matching
16. Jicos (ppt)
    • Exploiting multicore Computers
    • Design Pattern: Thread Pool
      • See subsection 6.2.3 of the textbook, in section 6.2: the Executor framework.
      • Java ThreadPoolExecutor API
    • Overlapping communication with computation
17. CX
    • Generalizing the expression for parallel efficiency for a multiset of heterogenous processors
    • Estimating T₁ for recursive functions
18. Design Pattern: Command
19. An abstract distributed system component (ppt)
20. Parallelizing Iterative Computations
21. Pregel
    • Quora/Pregel
    • Pregel presentation
    • jpregel-aws - Pregel atop JVMs, easily deployable on Amazon Web Services