The final is cumulative. It should go without saying that you should do all of the practice problems from the midterms and make sure you understand the answers to the midterms. I will be particularly focusing on questions people did not do well on for the first two midterms. For midterm 1, these were problems 3 and 4 (parallelization and identifying data races). For midterm 2, these were problems 2 and 4 (identifying deadlock and programming Erlang servers). New material ------------ ** Map-Reduce: - Why do all of the Mappers need to complete before we execute any calls to the Reducer.reduce(InputKey key, Iterable values, Context context) method? - In a real Hadoop or MapReduce implementation, the workers send back progress information to the Master (e.g., I’m now 65% done.... I’m now 66% done...). Suggest how this information might be used. - Do Map tasks running on workers send all of their output keys and values to the Master node? Why or why not? - MapReduce is inspired by functional programming, and the Map and Reduce are supposed to be “functional” or “not have side effects”, such as changing static fields or writing output other than via Context. Why? What can go wrong if mappers and reducers have side effects? - What are the algebraic properties required of mapper and reducer functions for mapreduce to work at all? What property is needed of the reducer in order to make a combiner useful? ** Parallelization using divide-and-conquer strategies (Dr. Luchangco's lecture, plus earlier stuff) - What are the main differences between accumulation-based computations over lists of data, and divide-and-conquer-based computations? Why is the first good for sequential programming and not for parallel, and vice versa? As an example, think of using an accumulator to sum all values in a list vs. using a divide-and-conquer strategy to do it. - It is important to distinguish between spatial order and temporal order of elements in a list being computed on. In a sequential algorithm, the two orders are often the same, while in a parallel algorithm they can be different. Explain. - A "Split list" is a datastructure that is designed to be easy to break in roughly equal-sized chunks. The definitions of the operations of this list were given in Dr. Luchangco's talk. Implement a split-list in Erlang, in particular, the following functions: empty() creates an empty split list is_empty(L) returns true if L is an empty split list singleton(X) returns a split list containing the single element X is_singleton(L) returns true if L is a singleton split list get(L) returns X if L is a singleton split list containing X concat(L1,L2) returns a split list that concatenates L1 and L2 is_split(L) returns true if L is a split node split(L) returns a pair {L1,L2} if L is a split node that joins split lists L1 and L2 from_list(L) returns a split list constructed from the standard list L Write an Erlang program to compute the length of a split list. Write a sequential version of this function (call it length(L)) and a parallel version (par_length(L)). For brownie points/fun, write a function to "balance" the split list so that each child of a split node has roughly equal length. For even more brownie points, write a function to_list that converts a split list to a standard list, in parallel. - Practice implementing divide-and-conquer algorithms by implementing a parenthesis matcher. The idea is that you are given a buffer consisting of a sequence of open and closed parentheses. Your job is to compute whether all of the parentheses match. You can use fork/join to do implement this using divide-and-conquer. Start from two files that are based on the MaxSolver we went over in class: http://www.cs.umd.edu/class/fall2010/cmsc433/examples/MatchSolver.java and http://www.cs.umd.edu/class/fall2010/cmsc433/examples/MatchProblem.java . The entrypoint to the program is MatchSolver's main() method. You need to fill in code bits in both classes to implement sequential parenthesis matching, along with code to combine the results of applying parenthesis matching to both sides of an array. ** Distributed computing - How is writing a distributed program similar to writing a parallel program? How is it different? Why might you prefer a distributed implementation to a parallel one? - What is an advantage to using an RPC library compared to performing network-oriented communications directly? What is a potential disadvantage? - If one part of a distributed program sends a request to another part and receives no response, either the remote side received the message but did not respond (or the response was lost by the network), or the remote side never received the request. What is the important distinction between these two cases? - Consider the following Erlang program, which creates two processes that send messages back and forth. Change this program so that instead of running the pong process on the local node, it runs it on a remote node called bigmac@gandalf. -module(pingpong). -compile(export_all). ping(_Pid,0) -> ok; ping(Pid,N) when N > 0 -> Me = self(), Pid ! {ping,Me}, receive {pong,Me} -> ping(Pid,N-1) end. pong() -> receive {ping,Pid} -> Pid ! {pong,Pid}, pong() end. start(N) -> Pid = spawn(fun pong/0), ping(Pid,N). - Consider the above program again. Change it so that it registers a pong_server, which is just a process running pong(). Then change the program so that it uses the Erlang rpc module to start the pong server on bigmac@gandlf, and then likewise uses the rpc module to remotely call a function that invokes ping() at bigmac@gandalf. - Write a service that receives messages consisting of a function to run and the arguments to give to that function. (Note that you can call apply(F,A) to run such a function and arguments. For example, if you did apply(fun (X,Y) -> X + Y end,[1,2]) you'd get 3.) The service then sends back the result. Then use the keep_alive function presented in class to keep this service running indefinitely. To test that it's working, send the service a bogus message, e.g., a function that takes two arguments but you only give it one. Make sure the service properly restarts. ** Dynamic Software Updating - Name a problem that could occur with a dynamic update, if we weren't careful, e.g., if we allowed the update to take effect at an arbitrary time. How does the gen_server framework's approach to code updating help avoid such problems? - Extend the example for updating the Erlang name server we went over in class so that instead of just re-using the old state after updating the module, we apply a state transformation function instead, to change the state to work with the new code. Change the new_name_server.erl module to additionally have an "undo" function. This function can be used to undo any deletions from the dictionary. To implement this, you want to change the state of the name server so that it's not just a dictionary, as is the case now, but is a pair of a dictionary (just as now) and a list of deleted items. Undo will restore to the dictionary the last deleted item. Your state transformation code will have to initialize this list (it should be empty) and you will have to change the implementations of add, allNames, etc. in the handle_call(...) cases to use the state properly. Additional old material ----------------------- Will post something before Monday. Concentrate on the old exams and practice problems for now.