Manage My Supervisions at Cambridge University

Undoubtedly, the University of Cambridge is famous for its college and supervision systems. Both are quite unique and you probably cannot find other similar correspondences easily in other places. The longer you stay in Cambridge, the more attractive you will find about this amazing system. In some sense, this system leaves a strong Cambridge label on its students and makes them so unique comparing to other students. Sometimes, I must admit that I am more impressed by the undergraduates I supervised than by the PhD students (especially if he/she didn't do his/her undergraduate here).

The supervision usually takes place within a small group of two or three students with a supervisor. The form of supervision can be flexible and versatile, but there are usually a lot of discussions between the supervisor and supervisees.  Even though I had a long experience of doing TA (Teaching Assistant) in the University of Helsinki, I must say the teaching in Cambridge is much more challenging also much more fun. Of course, it has more financial benefits since the colleges pay you extra money for your teaching.

I was lucky enough to get affiliated with Queens' College (one of the oldest colleges) just after a couple of months' arrival in Cambridge, which gave me an invaluable chance to look into this system. Moreover, I also started doing supervisions soon after the Michaelmas term started. Herein, I will share some experience in doing supervision at the University of Cambridge, which might be useful for other newly joined Postdocs, especially those who did not have undergraduate experience here.

The university does provide a decent system (CamCORS) for writing final reports for students. However, there is no useful systems in practice to help in scheduling supervisions, a supervisor and his students need to handle the scheduling all by themselves. I was quickly overwhelmed by email exchanges for discussing a suitable time in Michaelmas term while I was taking care of 20 students (7 groups). In this Lent term, I need to supervise 27 students (10 groups) on two topics (Information Retrieval & Operating Systems), so I definitely need to come up something smarter.

Therefore, I wrote down the following email and send it to my students. Haha, now it is their job to do the scheduling and compete for the "CPU resources" themselves. So far, this works pretty well and has saved me from a lot of hassles.

Hello all,

I made a Doodle poll which provided a list of all my available time slots in this Lent term. These time slots can be the candidates of our supervisions in the following weeks. To reduce hassles and email exchanges, let's schedule together using the following rules (essentially a distributed algorithm with relaxed contention avoidance ;-)

1. Each supervision group makes one poll. Do not make another separate poll if your group already made one. So for all the supervisions of a given course, each group should only take one row in the poll.

2. When making the poll, the group name should follow the following convention: COURSE_NAME(crsid_1; crsid2; crsid_3) so that I can know which course and which group it is. We have two courses: please use OS for Operating System and IR for Information Retrieval. Here is an example: OS(lw525; mbt11; szuh233)  another example: IR(tzx234; xrt233; bgh512)

3. For OS, we have three supervisions so you need to mark three time slots in all the available ones (try to distribute them evenly in three weeks). You need to discuss with your group members first to agree on a time before filling the poll. Do not mark multiple time slots for one supervision. For IR, we have two supervisions, the same rule applies.

4. If you notice that a time slot is already taken by another group, do NOT mark it anymore. Essentially, each column in the poll should NOT have more than one reservation. if contention does occur (less likely), run your randomisation or back-off protocol to resolve the contention ;-)

Here is the link to the poll —> [link]

I hope you can finish the poll as soon as possible to make all of our life much easier. If you have any questions, please do ask me. Thank you very much.

Best regards,

Liang Wang

Computer Laboratory

The Spherical Cow in System Science - Matrix Multiplication on Apache Spark (Part III)

As mentioned in the previous [blog], we introduced the big data framework into teaching in 2014, and we specifically chose to use Apache Spark in 2015. Besides calculating the basic statistic, we also asked the students to do something more skillful -- matrix multiplications. The detailed assignment description can be found [here].


I. Two Simple (But Representative) Matrix Multiplication Problems

In the assignment, we gave the students a tall and thin matrix which is of size $10^3 \times 10^6$. Let's call it matrix $A$. The matrix $A$ has one million rows and each row has one thousand double numbers. In total, there are one billion double numbers. We asked the students to calculate $X$ as blow:

1. $X = A \times A^T \times A$
2. $X = diag(A \times A^T)$

Solving large linear equation systems is very common in both engineering and scientific fields, and knowing how to manipulate matrices is basic skills for engineers and scientists. These two examples, though seemingly simple, are quite representative in scientific computing. Then how to solve them actually?


II. Order Matters

Let's start from the first question $X = A \times A^T \times A$. There are two ways to calculate $X$, namely $X = (A \times A^T ) \times A$ and $X = A \times (A^T \times A)$. Mathematically, they are equivalent, namely same result and same computation complexity. However, from engineering and system perspective, there is a big difference! Why?

Let me first ask you "What is the size of $X$?". Yes, it is exactly the same as $A$, namely $10^3 \times 10^6$. No matter whether we calculate the first two first (i.e., $(A \times A^T )$) or the latter two first (i.e., $(A^T \times A)$), the intermediate result need to be transmitted on many nodes to finish the calculation in order to give us the $X$ of the same size as $A$. However, the two intermediate results are quite different, see the figure below:

You must get the point after seeing this figure, right? If we call it matrix $B$ as our intermediate result. We can see $(A \times A^T )$ leads to a huge $B$ which is $10^6 \times 10^6$ in case I, whereas $(A^T \times A )$ only leads to a very small $B$ which is $10^3 \times 10^3$. Now, you tell me, "which matrix is easier to distribute in the network?". There is going to be several orders of magnitudes difference in the network traffic. If the matrix $A$ is very very tall (i.e., contains huge amount of rows), it is not even possible to finish the calculate of $(A \times A^T )$. So, the lesson we learnt here is "Order does matter!"


III. Decomposition and Aggregation

We know getting a smaller $B$ is more beneficial, but how shall we carry on to compute $(A^T \times A )$? We know Spark cuts the $A$ into many chunks and stores them separately on different machine. Let's call these chunks of $A$ as $A_1, A_2, A_3, A_4 ... A_m$. Note these chunks have same number of columns (i.e., $10^3$) but may have different number of rows, in other words, their chunk size may be different.

Now, let me ask you another question - "Choose any $i \leq m$, what is the size of $A_i \times A_i^T$?". Yes, they are all the same, namely $10^3 \times 10^3$. Actually, this is just the partial result of final $B$. To calculate the final $B$, we just need to aggregate these partial results and sum them up as below:

$B = \sum_1^m A_i \times A_i^T$

After having $B$, getting the final result $A$ is trivial. We just need to broadcast $B$ onto every node, then finish the calculation on every chunk as below:

$X_i = A_i \times B$

Assemble all the $X_i$. More precisely, concatenate them. Then you have $X$.


IV. Getting Diagonal Elements

I was actually a bit hesitant about whether to give the second question or not. I thought it might be too easy for the students. However, the truth is that most of the students actually did try to compute the complete matrix $A \times A^T$ which is so big that you cannot even fit into the normal memory, then extract the diagonal elements.

When the students brought such solutions to me and complained about the memory issue, I just ask them to do one thing - "Can you tell me the definition of the diagonal elements and describe how you calculate them? "

They usually started with -- "Well, the first row of  $A$ (dot) multiply the first column of $A^T$ ...".

Then I continued to ask -- "Then what is the first column of $A^T$?"

Suddenly, the students got the point -- "Haha, it is still the first row of the $A$!!!"

So, you do not need to calculate the whole matrix in order to get the diagonal elements. You just need process the data set line by line, each row will give you one diagonal element.

$X_(i,i) = \sum_{j=1}^{1000} A_{i,j}^2$

V. Common Issues

Same as the previous [median example], this set of questions were also very successful. The students quite liked the problem design even though very few of them actually got all the solutions right. One common issue from the students is that they tried very hard to have precise control on how the matrix/data set is cut in Spark. Controlling how the data is divided is not impossible but just meaningless regarding solving the problem, of course given you have sufficient knowledge in linear algebra and matrix operations.


Read this series: The Spherical Cow in System Science - Part I, Part II, Part III

The Spherical Cow in System Science - Calculating Median Value in Big Data Sets (Part II)

As system students of 90s, we remember that the classic distributed system course usually had strong assumptions on heterogeneity of nodes' geography and configurations (regarding both software and hardware). Many universities used Tanebaum's classic textbooks, and the distributed algorithms taught in the classes mostly dealt with fault tolerant, consistency and focused on a point-to-point communication paradigm. These algorithms are still very valuable and being will used in the various system. However, the industry force shifted the paradigm to a more centralized, more homogeneous, richer bandwidth-based high performance computer clusters. Or using more widely known and hyped name, we call it clouds computing.

To catch up the trend, we introduced the big data framework into DSP course (check my previous blog) in 2014 and 2015. We chose to use Hadoop in 2014 course and "upgraded" to Spark in 2015, but the questions remain more or less the same. Compared with the previous example I introduced, this set of exercises turned out to be a big success. So what did we actually asked the students to do?


I. Finding A Needle in A Haystack

The power of big data framework is fast processing and analyzing huge data sets by taking advantage of the computational and storage resources in high performance computer clusters. In the question set, we gave the students a date set of a very simple structure -- just one double number per line. The data set contains 10 billions lines. For generating data, I used Weibull and Gaussian mixture model. Technically, this is not really "Big Data", but I think it is pretty enough for the students to grasp the idea. We asked the students to provide the following statistics of the data set.

• Minimum value
• Maximum value
• Mean value
• Variance value
• Median value

By the way, we did not allow the students to use the default functions provided in the framework. We asked them to implement the functions by themselves using map-reduce paradigm (see figure blow). Some students did complain about reinventing wheels. But in my opinion, as a system engineer, you should know what happens behind the scene. However, to help the student start, I provided the example code to calculate the minimum value.

A figure summarizes the map-reduce-based data-parallel computing paradigm. 

For getting the maximum, it is very easy by simply tweaking my example code. Map-reduce is very good at handling data-parallel computation. A data set is divided into chunks then distributed on multiple nodes then processes in parallel. The minimum of the minimums (of all the chunks) is the minimum of the whole data set. The same applies to the maximum. However, the students need pay a bit more attention when dealing with mean value, since the mean of all mean values is simply not the mean value of the whole data set. It turned out some students did make this silly mistake.

The variance value needs even more thinking. We know there are (at least) two ways to calculate variance.

1. $Var(X) = E[(X - \mu)^2]$
2. $Var(X) = E[X^2] - (E[X])^2$

The first method is familiar to almost everyone, and indeed most students chose to use it. However, it needs to iterate the data set twice. Whereas for the second method, you only need to iterate the data set once. It is worth noting that iteration used to be expensive, especially for Hadoop in the early days. Though Spark has improved quite a lot, scheduling still contributes a significant time overhead in the calculations. So reducing the number of iterations is still a good idea when dealing with big data.


II. Handling Order Statistic

Things turned to be extremely interesting when the students started calculating the median value. Similar to the mean value, median of the medians are not the median of the whole data set. Median is one of the order statistic like Quantile, Percentile, Decile and etc. By definition, the median separates a data set into two equal parts. Technically, you need sort the data from the smallest to the largest and choose the middle one (break the tie if necessary). However, such conventional operation of getting median is not really suitable when dealing with large data sets.

Can you image sorting a data set of hundreds of GB or TB or even PB? First, you simply do not have enough memory to do that on one node. Second, you will introduce huge traffic if you try to do that in distributed way. Well, some of the students did try to sort the data, then quickly got frustrated. At this point, they realized they need to think differently in the context of big data. What's more, they also realized that the map-reduce may not be as straightforward as they thought.

The students eventually came up various solutions which can be categorized as below:

Median of medians - it is an approximation algorithm which gives a quick estimate of the median. But you still need sort the data set at least partially and only get an estimate, which is not good. For the algorithmic details, please check the [wiki page].

Random sampling - this method tries to get a random sample from the data set and use the median of the sample to estimate the median of the population. This method may work well on certain data which follow well-defined distributions like Gaussian, uniform and etc. However, let's imagine a data set wherein the first half numbers are 1, the latter half are 100, and the actual median is 57. Then the random sampling method is doomed to fail with high probability.

Binary search - if we think about the definition of median, it is not difficult to notice the median is bigger than 50% of the data and smaller then the other 50%, because this is simply its definition. So we can just randomly guess a number and check how many data fall on the left (i.e. smaller than the guessed number), and how many data fall on the right (i.e. bigger than the guessed number). Then we can know whether we under- or over-estimated the median. We can narrow down the scope by iterating this search until we find the true median.

Buckets/Histogram method - Binary search is already very close to the correct solution. But let me ask another question - how many iterations does binary search need to find the actual median? Easy, it is just $\log_2(N)$ where $N$ is the size of the data set. For those students who successfully reached the binary search solution, I asked them - "Can you further improve the performance by reducing the number of iterations?"

Of course you can! In some sense, the binary search uses two buckets and count the number of data in each bucket. We can certainly use more buckets and apply the same algorithmic logic here, then the narrow down the range where the median falls much faster. E.g., if we use $b$ buckets, then we only need  $\log_b(N)$ iterations. So feel free to choose $b = 1000$ or $b = 10000$, the introduced traffic overhead is negligible. Such method also has another name - histogram method. The figure blow sketches the crude idea, and there are some other materials on the Internet talking about this method. E.g., this YouTube video [here].

III. Do the Students Like This Exercise?

It turned out this exercise set was extremely successful. From teaching perspective, the exercise only uses simple statistics which every student can understand with very mathematical background. The wonderful part of the exercise is that all these statistics look similar and straightforward in the mathematical sense. However, from (data) engineering perspective, you need treat them completely differently. The exercise set reminds the student that porting the classic algorithms into big data context may not be as straightforward as they originally thought.


In the actual teaching, all the students solved min and max without any problem. Surprisingly, over 60% of the students still chose the slower way to calculate the variance. For median, it is even more striking. For these two years, only three students independently came up histogram method without any help from me. About the students' attitudes, in general, they like the question set very much, the main reason of which, I believe is because their strong curiosity on the hyped big data.

Read this series: The Spherical Cow in System Science - Part I, Part II, Part III

The Spherical Cow in System Science - Teaching Distributed System Course (Part I)

I. What Do We Want to Teach Students in System Courses?

I have been the teaching assistant of the Distributed System Project course, which is one of the compulsory course for every master student specialized in system and networking, for over five years' time in the University of Helsinki. Now it is my last year to handle this course before moving to the Cambridge University. During these four years, I learnt quite a lot by interacting with different students in the class. Since I designed most of the exercises for the course and graded all the students' solutions, it provided me the first-hand experience to understand how the students thought about the teaching and the content. I feel obliged to write down some of my thoughts and share the experience with current and future teaching assistants/staffs.

The Distributed System Project was the first course I had ever got involved in teaching in my life. I independently taught this course in 2013 while my PhD supervisor was away taking his sabbatical in the U.S. Because it is a project course, the core philosophy is "Learn by doing", we do not really need prepare any slides to actually lecture the students in the class. Instead, we try to let the students gain the hands-on experience by finishing some small projects. Therefore, the course assignments need to be carefully designed so that the students can apply those abstract theories (i.e., the spherical cow mentioned in the title) they have learnt in the distributed system course in a more concrete scenario. You can find all the information of the course via the following links:

• Distributed System Project Course 2011
• Distributed System Project Course 2012
• Distributed System Project Course 2013
• Distributed System Project Course 2014
• Distributed System Project Course 2015

The exercises are generally divided into two categories. First category usually covers the classic distributed algorithms (e.g., Lamport clock, vector clock, election algorithm and etc.) which is quite trivial and does not require me too much efforts to design. The second category is much more challenging since we tried to let the students take a system-level view when they are solving the problems. Some of the questions were very successful, some were not. In this series of posts, I will choose some examples and discuss them one by one.

About the title, assuming you know that joke, I think my purpose is quite obvious. So let me safely assume we can save the strength in explaining the title and simply start our first example.

II. Example I - The Migration of Complexity in the Distributed System Design

This was the exercise we gave in both 2011 and 2012. The exercise is very straightforward, the detailed the assignment description can be found [here]. In short, we simply ask the students to implement a naive calculator application which can plot the sine function using client/service model. We chose to use web browser, AJAX and RESTful API to avoid letting the students develop everything from scratch. We also specify that every request to the service can only carry one operator and two operands.

However, the story did not end like this simple. We asked the students to implement three versions of the aforementioned calculator under three different cases as following:

• The server is smart enough  to know how to calculate sine function. The client only plots the figure.
• The server is stupid and only plots the figure for the given points. The client is smart enough to know how to calculate sine function.
• Both server and clients are stupid. The server only knows +, -, *, / four arithmetic operations, and the client only knows how to plot.

I think you probably already got the idea. Case 1 and case 2 actually represent the evolution of our computation model within these several decades. In the beginning of computer systems, we had a really "powerful" server (powerful is a relative sense) who would take care of all the computations. A user only needs a terminal to connect to the server. A terminal, in some sense, is just a naked and stupid client which is responsible for submitting jobs and displaying the results. In technical terms, we call it thin client and fat server model. This model is reflected in our first case.

As time goes by, functionality started shifting to the client side. CPU became much faster, the storage grew much bigger and the price dropped a lot. Then more and more features were added to the client side. As the PC became more powerful, the applications were also growing in their complexity and more applications started running at the client side to improve user experience. The shift of the use pattern eventually led to fat client and thin server model. Nowadays, even a moderate smartphone is more powerful than a mainframe dozens of years ago. Apparently, our second case tries to capture this model.

It is very interesting to notice that the hyped clouds computing is shifting the computations back to a centralized entity again. Note that the entity here can refer a cluster of computers instead of a standalone server. The key enabler of this trend is the virtualization technology. People realized that the horizontal scalability is a more feasible solution from both economy and engineering perspective.

III. Do Not Forget the Communication Channel Is Also An Integral Part of A Distributed System!

However, our third assumption tries to capture another (maybe a bit unfortunate) case wherein both the server and client are stupid. In such a case, how can a client collaborate with a server only supporting  +, -, *, / four basic arithmetic operations to finish the calculation of sine function? One solution is using Taylor Series to approximate the sine function. Because we explicitly required the solution need to reach certain precision, the students have to figure out the minimal degree needed in the polynomials. When solving this case, we can clearly see that the complexity migrates to the communication channel. Namely, the client and server need to collaborate many rounds in order to finish the computation task.

I am pretty sure you already got the big picture of this assignment. In the first case, the server takes care of the (computation) complexity while the client handles the complexity in the second case. However, if neither can deal with the complexity, the complexity needed to finish the computation has to go somewhere, then it goes to the communication channel in our third case. The exercise reminds the student that the communication channel (usually our network) is also an integral part of a distributed system design.

IV. Is This Really A Good Exercise?

About this exercise, the comments from my colleagues were quite positive. However, the actual feedback from the students in the class were rather bad. Most students failed to grasp the core idea of the exercise and simply thought that we asked them to develop a naive AJAX application. I even got some angry complaints from a student saying "I am not coming here to become a web developer!" Oh, well, you know what? The web is actually the biggest distributed computer system in the world nowadays (excluding the mobile devices ;-) ). Besides, being a web developer is not a bad idea at all in the first place :D

All in all, we finally realized that, without explicitly explaining what is the purpose of this exercise, the students could not really grasp its idea. However, if we put everything across in the first place, there is simply no fun any more in solving the problem. Eventually, we dropped this exercise out after its two trials in 2011 and 2012, which was really sad in my opinion!

Read this series: The Spherical Cow in System Science - Part I, Part II, Part III