The final exam is comprehensive, with about 60-70% of it covering the
material since the last midterm, and 30-40% on the material covered by
the previous midterm.

See the previous review topics for more information. Since the last
midterm, we have covered the following topics:

-Thread pools and parallelization
-Nonblocking synchronization
-Erlang
-RMI
-MapReduce
-Scalable servers
-Actors in Scala

The newer material is covered in JCIP Chapters 6, 8, 11, and 15. 

Good reference material on Erlang is at 
http://www.erlang.org/doc/getting_started/users_guide.html
http://queue.acm.org/detail.cfm?id=1454463

There are links to other bits of reference material in the lecture slides.

===

Definitions
=======
- Optimistic synchronization vs. pessimistic synchronization
  - Explain why the terms have these names: what are we being optimistic or pessimistic about?
- Latency
- Throughput
- Scalability
- Graceful degradation
- Lock contention
- Spinlock
- Non-blocking algorithm
- Data Parallel
- Task Parallel
- Thread pool
- Thread starvation deadlock
- Producer/Consumer pattern
- Work stealing scheduler
- Distributed object model
  - server vs. client, in terms of hosting objects
  - local vs. remote invocation (of a method)
  - registry
  - stub (and skeleton)
- Message passing
  - Marshaling / unmarshaling
  - Serialization / deserialization
- Mapper, reducer, combiner
- Hadoop vs. MapReduce
- HDFS vs. GFS
- Linearizable object
- Linearization point

Definitions (Erlang):
============
- Process
- Message passing
- Mailbox
- Atom
  - How does it relate to a string? How do strings relate to lists?
- Immutability
- Tuple vs. List
- Error vs. Exception vs. Exit
- Static vs. dynamic typing
  - Which one is Erlang?
- Anonymous functions
- List comprehension
- Server behavior (aka Actor)
- Call
- Cast

Topics/questions:
===========
Here's some terms and questions for you to review:

Executor questions:
- What are the elements of an Executor?
  - Which of these can you customize, and how would you do it?
- What are the steps in the Executor's lifecycle?
  - What is the difference between shutDown() and shudownNow()?
- What is the lifecycle of a Task submitted to an Executor?
- Why use an Executor rather than one Thread per task?
- If you submit a task to an Executor, how can you make it wait until all tasks have been submitted before it starts running?

ExecutorService questions:
- What is the difference between an ExecutorService and an Executor?
- How are Futures used with ExecutorServices?
- What is the difference between a Callable and a Runnable?
  - What happens if either dies with an exception when being run in an Executor?
- What function does a CompletionService provide, over and beyond an ExecutorService?
  - What is the difference between using such a service and waiting on tasks' Futures in the order they were submitted?

Design considerations:
- Why is it important to know whether tasks are dependent or independent?
- Why might it matter whether tasks run long or short, when executed in a thread pool?
- How many threads should you have in your thread pool (what's the formula)?

Parallelization
- Know the different kinds of parallelism (see terms above)
- Know the design recipe for parallelizing something (with futures)
  http://www.cs.umd.edu/class/fall2013/cmsc433/lectures/futures-design-recipe.txt
- What are the overheads of a parallel algorithm not present in the sequential one?
- What is Amdahl's law?
  - How does it compare to Gustafson's law?
  http://en.wikipedia.org/wiki/Gustafson's_law
- Justify the following claim: "Improving performance by parallelization can actually increase the total work performed by all threads while reducing the latency of performing the work by all threads in parallel.  "

Fork/join parallelism
- This style is useful for "divide and conquer" problems. Why does this mean?
- Compared to a normal threadpool, what advantages does Fork/Join offer for implementing this style?
- Is this style of parallelism good for compute-intensive tasks? Why or why not?
- Name a couple of applications that would do well with Fork/Join, and explain why.

Nonblocking synchronization:
- What are the disadvantages of locking?
- CAS (compare and swap) primitives are the basis of nonblocking algorithms, using an "optimistic" style.
  - What is the semantics of CAS?
  - How is it used to implement optimistic concurrency?
- Why is it difficult to use CAS to update data structures with multiple fields? What is one way to deal with the problem?
- Give an example of where you might use AtomicInteger fields
- Why is writing a nonblocking queue harder than writing a nonblocking stack?

RMI Questions:
- Why do we need the registry in RMI?
- What is the effect of having a class implement the Remote interface?
- What would be the effect of making String implement the Remote interface?
  - Assuming no failures, is it possible to get a different output from the program, compared to String not implementing Remote? Why or why not?

Erlang
- What's the relationship between Erlang strings and lists?
- Can I assign to a variable twice?
- How do I sent a message from one Erlang process to another?
- When receiving messages, which is prioritized: the pattern in the receive block, or the order in which the messages are received?
- Erlang dictionaries: mutable or immutable?
- What is the server behavior? 
  - What is it abstracting (i.e., what part can vary and what part stays the same)?
- How can I use servers to implement a stateful abstraction, like a counter or semaphore?
- Is process creation cheap or expensive in Erlang? In Java?

MapReduce questions:
- What is the difference in the programming model (e.g., the types) of map and reduce (aka fold) as used in Google MapReduce compared to the functions in ML?
- What are the benefits of the map and reduce functions are "purely functional" (i.e., they do not affect the outside world while running)?
- Why should we not implement "Group By Key" as a separate task following the map phase, and preceding the reduce phase?
- What kind of parallelism is achieved during the map phase? What kind during the reduce phase?
  - How can we improve parallelism in the reduce phase if the function is associative?
- Why must a combiner also be commutative?
- How is the input and output stored, and how are intermediate results communicated between phases?

Scalable servers:
- Why use microbenchmarks?
- What are good measures of server performance?
- What do you want your performance graphs to look like, as the
request rate goes up?
- What are some design considerations for server structure, which
affect performance?
  - E.g., multi-threaded vs. single-threaded ... others?
- Which design considerations seem not to work, generally, for
scalability, and why?
- Multi-threading/pooled does better or worse than
single-threaded/non-blocking? Why?
- What is a Selector?
- What is NIO?

Actors (Scala):
- What are the three traits that are used to implement actors?
  - What is a trait and how does it compare to a class?
- What is the difference between using react { ... } and receive { ... } in Scala?
- What are the four states of a Scala Reactor?
- Why does Scala have "control structures" like loop { ... } and andThen { ... } and loopWhile(c) { ... } ? What do they do?
- What is the difference between the following bits of Scala code: 
  - a ! 1
  - a !! 1 
  - a !? 1
- What is a case class, and how is it often used when programming with Actors?
- What is a channel, and is it used?