ࡱ> 9;8M  bjbj== .*WW ldddddddxF F F F Z 4x @ @ @ @  - 9 {}}}}}} }dA   A A }+ dd@ @ + + + A vd@ d@ {+ A {+ + dd @ HZxF ^ 0   + xxdddd INCLUDEPICTURE \d "C:\\Documents and Settings\\afek\\My Documents\\dist\\dc3_files\\tau-small.gif" \* MERGEFORMATINET   HYPERLINK "http://www.tau.ac.il/" Tel Aviv University  HYPERLINK "http://www.cs.tau.ac.il/" Computer Science Dept. Distributed Computing Fall 2002 Lecturer:  HYPERLINK "http://www.eng.tau.ac.il/~vered" Prof. Yehuda Afek   NEW !!!!! 2nd Homework DUE January 13th ! (one week postponement) Second homeworks ( HYPERLINK "http://www.cs.tau.ac.il/~afek/hw2.ps" ps). Due January 6.  HYPERLINK "http://www.cs.tau.ac.il/~afek/qa2.html" Questions & Answers regarding homework 2  HYPERLINK "http://www.cs.tau.ac.il/~afek/qa.html" Questions & Answers regarding homework 1 Course Summary A graduate 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 2. synchronization algorithms for {\em asynchronous} shared memory parallel machines. In addition we will discuss the connections and relations between these two models. Hopefully we will also go over a real distributed algorithm such as BGP.  Administrative Information Lectures: Sunday 17:00-20:00, Room: Schreiber 006 Course Topics and Schedule (tentative) DATETOPICOct 28Models, Broadcast & EchoNov 4Termination Detection, Snapshots, SynchronizersDec 2Leader Election, ring networksDec 9Leader Election Algorithms and Spanning tree algorithmsDec 16HanuckaDec 23Computing the maximal independent set, rings and general graphs, upper and lower boundsDec 30Data link protocols, the sequence transmition problem and End-to-End protocolsJan 6The consensus problem. Algorithms and lower boundsJan 13The shared memory modelJan 20The consensus problem, and its impossibility in asynchronous networks with one faulty processorJan 27Wait-free synchronization, the shared memory hierarchy and universal constructionsFeb 3Atomic Snapshots of shared memories, Immediate snap-shotsFeb 3Simulating Shared memory in message passing ? we will seeDistributed Shortest Path Algorithms, & the BGP example See  HYPERLINK "http://www.math.tau.ac.il/~afek/topics.ps" Course outline with references ( HYPERLINK "http://www.math.tau.ac.il/~afek/topics.pdf" pdf)  Grade The grade weighting for the semester will be: Home Works35%Take home exam:65%These weights are subject to change.  y|}~"#$QRdeghijuw  >?ghijO P p q ʶ jUCJaJ B*ph3fjB*Uph3fjB*Uph B*ph B*H*ph B*ph jeUCJaJ B*phB*CJ$OJQJaJ$ph0J jUB}ghj i  ^`$a$H$$IfK0 6$$634Ka $$Ifa$ $$Ifa$$If$If / D I O P W Yo$$Ifl0 0644 la$$If[$\$a$ $If[$\$$a$  ^` W p q w    |||||@||$Ifo$$Ifl0 0644 la $If[$\$   | }   . / 2 3 f g   G H K L N O V jKU 56\]6] jU0J jUCJaJ4 $ | }    . / 6 \o$$Ifl0 0644 la$If 2 3 9 f g u N l$Ifo$$Ifl0 0644 laN P V X^K$$If0G; 6234a$If$a$ ,1h/R . A!"#$%eDf9HC:\Documents and Settings\afek\My Documents\dist\dc3_files\tau-small.gif  C  C:\Documents and Settings\afek\My Documents\dist\dc3_files\tau-small.gifDd<V  3 C"((Dd<V  3 C"((Dd<V  3 C"((Dd<V  3 C"(( i8`8 NormalCJ_HaJmH sH tH F`"F Heading 2dd@&[$\$5CJ$\aJ$F`2F Heading 3dd@&[$\$5CJ\aJ>`B> Heading 4dd@&[$\$5\F`RF Heading 5dd@&[$\$5CJ\aJ<A@< Default Paragraph Font.U`. Hyperlink >*B*ph>V`> FollowedHyperlink >*B* ph:^`: Normal (Web)dd[$\$ *}ghj i/DIOPWpqw  $|}./6239fguN P V @0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@08@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0P @0P @0P @0P @0P @0P @0P @0P @0P  W  N  y{}#Qd >gi  G K CtXtXtXtXtXtXtXtXt8@0(  B S  ?ADMIN  X^_cH K joik 3333333 afek9C:\Documents and Settings\afek\My Documents\dist\dc2.htmlghDIOPWpqw  $|}./6239fgu @ 0@UnknownGz Times New Roman5Symbol3& z ArialCFComic Sans MS"qh,aƟ,ak]20 2Q.Communication Networks, Spring 2001: Home PageafekOh+'0 , H T `lt|/Communication Networks, Spring 2001: Home Page0ommommommommNormalcafeklc2ekMicrosoft Word 9.0r@F#@-Z@-Zk՜.+,D՜.+,\ hp|  /  /Communication Networks, Spring 2001: Home Page Title  8@ _PID_HLINKSA0%>+http://www.math.tau.ac.il/~afek/topics.pdfAX*http://www.math.tau.ac.il/~afek/topics.psYC&http://www.cs.tau.ac.il/~afek/qa.html4p'http://www.cs.tau.ac.il/~afek/qa2.htmlX  %http://www.cs.tau.ac.il/~afek/hw2.ps~u  http://www.eng.tau.ac.il/~vered http://www.cs.tau.ac.il/ http://www.tau.ac.il/  !"#$%&')*+,-./1234567:Root Entry F0HZ<Data 1TableWordDocument.*SummaryInformation((DocumentSummaryInformation80CompObjjObjectPool0HZ0HZ  FMicrosoft Word Document MSWordDocWord.Document.89q