Distributed Computing

0368-4429-01

Spring-Summer 2009 (2008/2009)

Lecturer: Prof. Yehuda Afek

Grades

ID	HW1	HW2	HW3	HW4	HW	EX1	EX2	EX3	EX4	EX5	Exam Total	fina grade
302823	100	90	92	100	96	21	25	30.88	11	10	97.88	98
32565	99	89	93	100	95	21	25	30.88	11	10	97.88	97
40404	93	90	92	95	93	21	25	32.94	10.35	10	99.29	97
32873	88	89	98	98	93	25.2	25	26.76	10.35	10	97.32	96
40861	80	80	74	93	82	25.2	25	30.88	10.35	10	101.44	95
311894	100	97	89	100	97	12.6	25	30.88	11	10	89.48	92
300066	99	89	94	100	96	16.8	25	27.79	11	10	90.59	93
34947	96	85	88	100	92	11.2	25	32.94	11	10	90.14	91
40475	92	85	93	100	93	16.8	25	25.74	11	10	88.54	90
61992	66	76	91	65	75	30.8	21	24.71	11	10	97.51	90
317844	100	87	89	100	94	7	25	35	10.35	10	87.35	90
40031	99	74	87	91	88	11.2	25	33.97	10.35	10	90.52	90
300584	86	66	93	100	86	11.2	25	32.94	10.35	10	89.49	89
40918	100	84	95	91	93	11.2	25	30.88	9.059	8.82	84.96	88
317610	100	91	90	100	95	11.2	25	23.68	9.706	8.82	78.41	85
61201	96	80	89	100	91	7	21	30.88	10.35	10	79.24	84
46110	79	82	76	78	79	11.2	24	35	11	5.29	86.49	84
40546	74	95	77	78	81	9.8	25	27.79	10.68	10	83.27	83
40893	42	61	93	61	64	28	12	29.85	8.412	10	88.26	80
304240	55	83	61	95	74	7	21	26.76	10.35	10	75.12	75
4312	100	68	73	66	77	7	25	22.65	11	7.06	72.71	75
33801	82	66	55	78	70	21	14	26.76	7.118	0	68.88	70
319570	42		23	66	44	7	12	0	7.765	8.82	35.59	69
317321	89				89			0	0	0	0.00	31.15
66495	64				64			0	0	0	0.00	22.4
37676	40		76		58			0	0	0	0.00	20.3
309080	71	35	73	47	57			0	0	0	0.00	19.775

Assignment #5, take home exam. QA page.

Limor's class notes. Week 1-7, week 8-13.

Homework #4 due June 14 in the class.

Homework #3 due May 10 in the class.

Proof for Q3 in HW1

Homework #2 due April 19 in the class.

Homework #1 due March 25 by 3:30 PM in Schreiber 214 (Galit)

Administrative Information

· Lectures: Sunday 17:10-20:00, Holsblat/ Melamed 007

· Office Hours, by appointment (email) Sunday 16:00-17:00

Course Topics and Schedule (tentative, subject to change)

DATE	TOPIC
March 8	Models, Broadcast & Echo
March 15	Termination Detection, Snapshots, Synchronizers Snapshot paper pdf
March 22	Leader Election, ring networks, unidirectional case
March 29	Leader Election Algorithms and Spanning tree algorithms
April 19	Computing the maximal independent set, rings and general graphs, upper and lower bounds
April 26	Data link protocols, the sequence transmition problem and End-to-End protocols and another pdf
May 3
May 10	The consensus problem. Algorithms and lower bounds
May 17	The shared memory model, Wait-free synchronization, the shared memory hierarchy and universal constructions. Atomic Snapshots of shared memories, Immediate snap-shots,
May 24	The consensus problem, and its impossibility in asynchronous networks with one faulty processor
May 31	Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper Moir Anderson, Lamport-87
June 7	Simulating Shared memory in message passing, Randomized Consensus.
June 14	Lower bound techniques (log ^* n for maximal independent set on ring of size n).
Time permitting	Renaming, Eventually connected end-to-end STP, Concurrent Time Stamps,

See OLD (!!!!) Course outline (NOT up to date) with references (pdf)

---

Grade

The grade weighting for the semester will be:

Home Works	35%
Take home exam:	65%

These weights are subject to change.

---

Winter 2008 Course page

Winter 2007 Course page

Winter 2006 Course page