Distributed Systems and Common Knowledge

Today we discussed distributed systems. I explained what distributed computer systems are, what are their advantages and disadvantages (over centralized systems), and we analyzed the two fundamental problems of decentralized control: (1) state uncertainty, i.e., no node can know with complete certainty the states of the other nodes, and (2) action uncertainty, i.e., no node can know with complete certainty the actions of other nodes. We discussed the Byzantine Generals problem, and the problem of "common knowledge." The latter was especially fun, because I had various groups of students sit in chairs at the front and wear blue or pink headbands. Each student in the group had to figure out if they were wearing a blue headband. This can be done by pure deduction given three pieces of information: (1) a publicly given hint that at least one has a blue headband, (2) the ability to see the headbands of others, and (3) the responses (or non-responses) they give to my repeated question, "Are you wearing a blue headband?". If there are N students wearing blue headbands, then those N students will all be able to simultaneously answer "Yes" after the Nth time the question is asked. My hat goes off to Ziaozhe who came closest to figuring out how this is done.

This was the final session of the Beyond Media Computing thread. It is a little sad to see it end. I think we did a good job in showing some of the variety and depth of problems in computer science. I hope the students will remember what they learned in our thread.

PS: After class, we had a surprise birthday party for our GREAT Teacher Fellow, Shirley. I think she was genuinely surprised and happy. We all think she is the best!