The lecture on Tuesday Dec 10, will cover the following topics  :

- A simple randomized Byzantine Agreement protocol (by Ben Or)
- Efficiency analysis and correctness proof
- A meta-protocol with O(log n) expected running time
- A feasibility analysis

If time permits, the lecture will also contain a brief on the implementation of the said meta-protocol.

The lecture is based on the followings papers:

http://dl.acm.org/citation.cfm?id=806707 (Michael Ben-Or, Another advantage of free choice: Completely asynchronous
agreement protocols, PODC'83)

http://dl.acm.org/citation.cfm?doid=31846.42229 (Gabriel Bracha, An O(log n) expected rounds randomized byzantine generals protocol, Journal of the ACM'87)

The proof of the simple randomized protocol will be based on the one from
http://www.cs.yale.edu/homes/aspnes/papers/randomized-consensus-survey.pdf (section 5.1)

The following is an interesting lecture video that surveys Byzantine agreements and leadership election
http://www.youtube.com/watch?v=UVzCZqNngaU