Distributed Computing

0368-4429-01

Winter 2005 (2004/2005)

Lecturer: Prof. Yehuda Afek

ציונים סופיים (הבחינות, שני עותקים בתאים שונים, יהיו בחדר צילום שרייבר קומה 1)

ת.ז.	תרגיל 1	תרגיל 2	תרגיל 3	תרגיל 4	בחינת בית	ציון סופי
066062100	95	96	90	100	99	100
034374843	101	95	99	100	98	100
027306091	62	76	93	97	82	91
313879942	62	73	67	70	76	85
040854192	57	68	78	99	55	76
310604905	29	34	9	60	21	50
032269995	0	58	84	97	66	78
035749787	56	70	73	95	73	84
033833849	64	78	84	93	78	88
031686462	95	77	92	95	84	94
033661703	72	55	82	98	72	85
313989089	72	67	74	60	72	83
307402461	75	73	84	92	78	89
310874300	65	52	0	70	40	62
036121622	48	65	83	100	78	87
313064370	78	88	86	95	86	94
031413453	87	64	80	95	69	85
41855750	36	66	73	95	85	88
034287060	66	81	87	96	60	81
310944384	83	73	82	96	80	90
034208090	75	75	91	97	94	97
306997487	71	49	82	105	61	80
038452892	54	67	84	97	87	92
310148481	76	73	81	92	71	85
029399458	75	61	83	97	66	83
065596694	77	82	84	100	81	91
052326121	91	80	86	100	90	96
303926000	63	61	0	70	47	65
31853476	67	85	88	97	93	97
309393510	63	76	92	97	86	92
310058474	34	73	79	105	72	83
306638081	59	75	97	100	86	93
032258725	43	50	81	95	77	85
036420438	63	58	78	95	69	83
021475686	51	72	86	99	43	71
039166913	75	94	99	105	94	99
034474544	32	69	86	0	51	71
025042862	0	12	81	80	20	53
040818304	63	63	96	100	90	94
034191072	74	87	90	99	87	94
061257150	83	16	0	0	0	40
040858219	71	72	89	96	73	87
042347534	83	90	96	100	97	100
034491688	71	67	67	0	0	48
321061913	21	52	73	90	34	63
040051963	71	95	97	95	87	95
040138554	61	70	84	98	78	88
052697315	76	66	73	0	67	79
037294667	74	62	72	95	84	90
021384946		73	92	99	91	91
053088845	64	55	84	85	84	90
035933530	68	61	83	97	80	89
015422934	79	91	90	100	87	95
022687297	54	68	77	98	39	69
043117761	97	86	96	100	86	96
027238856	89	88	97	97	84	94
036563591	67	60	79	98	66	82
062860978	59	68	77	100	74	85
037572559	28	0	0	0	0	35
040686321	57	66	68	96	81	87
065951550	38	69	66	96	83	87
040033920	56	71	66	30	26	60

אתם מתבקשים להשתתף בסקר ההוראה הממוחשב של סמסטר ב' תשס"ה.

EXAM Q&A

Take-home exam (pdf) May 29^th to June 5^th at 4PM.

Except those I tell them differently by email, each of you have another 24 hours on her/his deadline to submit the exam to Larisa *** before 15:30PM ***.

Graded home work 3 are in the zerox room (1^st floor Schreiber)

Some notes from the Mutual Exclusion Presentation

Homework 4 pdf Due: May 29.

Q&A Regarding Homework 3.

Homework 3 pdf Due: May 8th.

Scanning of a paper relevant to the first two lectures

Q&A Regarding Homework 2.

Homework 2 pdf Due: April 3rd.

Scanning of a paper relevant to the first two lectures

Q&A Regarding Homework 1.

Homework 1 pdf Due: March 13^th.

Course Summary

A graduate level course exploring topics from the current literature in distributed computing, focusing on theoretical issues: models, upper and lower bounds, and proof methods. Two major topics:

1. Distributed algorithms for data communication networks (Message Passing)

2. Synchronization algorithms for asynchronous shared memory parallel machines.

In addition we will discuss the connections and relations between these two models.

---

Administrative Information

· Lectures: Sunday 17:10-20:00, Schreiber 006

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

Course Topics and Schedule (tentative, subject to change)

DATE	TOPIC
Feb 20	Models, Broadcast & Echo
Feb 27	Termination Detection, Snapshots, Synchronizers Snapshot paper pdf
March 6	Leader Election, ring networks, unidirectional case
March 13	Leader Election Algorithms and Spanning tree algorithms
March 20	Computing the maximal independent set, rings and general graphs, upper and lower bounds
March 27	Data link protocols, the sequence transmition problem and End-to-End protocols and another pdf
April 3	The consensus problem. Algorithms and lower bounds
April 10	The consensus problem, and its impossibility in asynchronous networks with one faulty processor
April 17	The shared memory model, Wait-free synchronization, the shared memory hierarchy and universal constructions.
May 8	Atomic Snapshots of shared memories, Immediate snap-shots,
May 15	Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper Moir Anderson, Lamport-87
May 22	Simulating Shared memory in message passing, Randomized Consensus.
May 29	Distributed Shortest Path and the BGP protocol.
Time permitting	Renaming, Eventually connected end-to-end STP, Concurrent Time Stamps,

See Course outline 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.

---