Winter 2013 Faith Ellen
This course will focus on the main techniques for proving unsolvability results and lower bounds for distributed computing, including indistinguishability, information theory arguments, covering arguments, valency arguments, combinatorial arguments, and simultaion. Examples of proofs that apply these techniques to various problems in a variety of different models will be presented.
The course is scheduled on Thursdays in BA 4010. It will start at 2:10pm and end sometime between 4:00pm and 4:30pm.
You should have taken a course in theory of distributed
computing (such as CSC2221).
People with good backgrounds in
complexity theory are welcome to take the course,
provided they
are willing to do some background reading.
Students will be assigned homework questions in which they will use
the techniques presented in class to prove other results.
Students will also present one impossibility result from the literature to the class.
50% homework
50% class presentation
January 10, 2013: Indistinguishability
Step Complexity of Approximate Agreement
A Chain Argument for Consensus
January 17, 2013: Indistinguishability continued
Impossibility of Set Consensus
January 24, 2013: Information theory
Round Complexity of Approximate Agreement
Step Complexity Tradeoff for Synchronoous Snapshots
January 31, 2013: Covering
Space Lower Bounds for Timestamps
February 7, 2013: Covering continued
Space and Step Complexity Lower Bounds for a Counter
Implemented from Swap Objects
Stall Lower Bound for a Counter
Implemented from Read Modify Write Objets
February 14, 2013: Valency
Impossibility of Consensus using m-assignment
A Round Lower Bound for Consensus
Impossibility of Consensus in Asynchronous Message Passing Systems
February 28, 2013: Valency continued
Space Lower Bound for Randomized Consensus
March 7, 2013: Combinatorial Arguments
Step Complexity of Weak Test and Set
Anonymous Conflict Detectors
March 14, 2013: Combinatorial Arguments
Yao's Principle
Randomized Implementations of a Max Register
March 21, 2013: Simulations
Impossibility of k-set consensus with at most f
process crashes
March 28, 2013: Simulations continued
undecidability of consensus number
April 4, 2013: class presentations
Hagit Attiya and Faith Ellen,
Impossibility Results for Distributed Computing, Morgan Claypool, 2013, to appear.
Chapters from this forthcoming book will be posted here.
Faith Ellen Fich and Eric Ruppert,
Hundreds of Impossibility Results for Distributed Computing,
Distributed Computing, volume 16, number 2--3, 2003, pages 121--163.
This survey article gives descriptions of the techniques, but not very many proofs.
Hagit Attiya and Jennifer L. Welch,
Distributed Computing: Fundamentals, Simulations, and Advanced
Topics,
second edition,
Wiley, 2004.
This textbook provides good background for the theory of distributed computing.
It is available online, through the University of Toronto Library, as an electronic resource.