Course on "Knowledge and Games in a Distributed System"
|Please note the following course announcement from Yoram Moses.|
I will be giving a graduate course on
"Knowledge and Games in a Distributed System" in the EE faculty this semester.
(Sundays at 2:30-4:30, room 351 in the EE building; first meeting March 6th.)
This course presents the theory of knowledge in distributed and multi-agent systems.
It introduces a framework for ascribing knowledge, distributed knowledge and common
knowledge to individuals and groups of agents in any game or distributed protocol.
Various results are presented relating knowledge to coordination and information flow,
demonstrating how it can be applied to the design and analysis of problems and protocols
in distributed computing.
The subject is an example of applied mathematical logic (different from, but in the spirit of,
temporal logic), although the course deals more with protocols and multi-agent systems
than with formal logical issues. The course is self-contained.
Video lectures on Youtube
|Lectures of the course can be watched on the Technion's channel in Youtube.|
The playlist is in
Yoram Moses on 5/1/2011
|On January 5, we'll have a special guest lecture by Prof. Yoram Moses, from the Technion's EE department.|
Title: Knowledge in Distributed Systems Then and Now
Speaker: Yoram Moses, Technion EE dept.
The theory of knowledge in distributed systems is now over 25 years old. This talk will review some of
theory, its premises and its goals. in distributed systems. The basic notions of knowledge, distributed
knowledge, and common knowledge will be described and their role will be illustrated through a number of
examples. Some early work will be presented, as will some very recent work illustrating how the analysis
of knowledge and information flow can be used to capture essential aspects of coordination in a
The talk will not assume familiarity with the subject, and is intended for a broad audience.
It is a good place to look for anyone that may be considering taking a graduate course on the topic that I will teach in the
Eli Gafni on 21/12
|On Wednesday, we'll have the pleasure of hosting Prof. Eli Gafni (from UCLA) at the course.|
For k-Set Consensus, is 1 different than 12?
Or Distributed Computing on One Foot
The integer 1 is the unity of multiplication. The integer 12 is corresponds the senior high-school year. They surely are different in many respects. But distributed computing does not multiply, neither it attends school, so why should it distinguish between the two integers?
I refer to the nice generalization of consensus introduced by Chaudhuri called k-set consensus. While in consensus processors vote for a unique participating processor to be their representative, in set consensus their vote may diverge but at most to k will be voted for.
Are there properties that hold for consensus but do not have a corresponding property for k-set consensus? This talk will survey a slew of interesting results arising from the conviction that for distributed computing 1 is not different than 12.
The talk will survey results with: Afek, Travers, Guerraoui, Kuznetsov, Raynal, and Rajsbaum.
Bio: Eli Gafni received his first degree form the Technion, second from UIUC, and third from MIT, all in E.E. He was involved with the Internet in the early days when it consisted of only few nodes. Unlike his contemporaries in MIT, of which quite a few went on to become few hundred times Internet Millionaires, he joined UCLA computer-science department and abstracted the Internet to the point that he became even too theoretical for that discipline. Nevertheless, with tenure, he is still a Professor at UCLA, holding forth that intellectual fun or the ability to roam perhaps aimlessly through intellectually challenging roads, is the reason to be in University rather than Industry. He does not envy the Millionaires, and he is only partially responsible for the sorry financial-state of the UC system.
No lecture on 8/12
|There will be not lecture next week (December 8).|
Home assignment 2 is published
|Due date is December 1, 2010. Good luck!|
Home assignment 1 is published
|Due date is November 17, 2010. Good luck!|
Notes for Lecure 3 are also published.
Video lectures are available
|The first lecture is now available on the Technion video server:|
|Welcome to the course, which will concentrate on using topology in the study of distributed computing.|
Note the time change: The course will take place on Wednesdays, 14:30-16:30, in Taub 5.
Slides and notes for the first lecture have been loaded in the material section of the website.