home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / la / seminars / 207 < prev    next >
Encoding:
Text File  |  1992-11-23  |  2.3 KB  |  56 lines
  1. Newsgroups: grads,seminars,la.seminars
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!ucla-cs!lanai.cs.ucla.edu!gpham
  3. From: gpham@lanai.cs.ucla.edu (Gisele Pham)
  4. Subject: GENERALIZED FLP IMPOSSIBILITY RESULT FOR t-RESILIENT ...
  5. Message-ID: <1992Nov23.182148.11382@cs.ucla.edu>
  6. Keywords: CS201 Seminar
  7. Sender: usenet@cs.ucla.edu (Mr Usenet)
  8. Nntp-Posting-Host: lanai.cs.ucla.edu
  9. Organization: UCLA, Computer Science Department
  10. Distribution: la
  11. Date: Mon, 23 Nov 92 18:21:48 GMT
  12. Lines: 42
  13.  
  14. DATE Tuesday December 1, 1992
  15. TIME 4:30-6:00 P.M.
  16. PLACE 3400 Boelter Hall
  17. Cookies & Coffee Will Be Served
  18. Starting at 4:00 PM
  19.  
  20. GENERALIZED FLP IMPOSSIBILITY RESULT FOR 
  21. t-RESILIENT ASYNCHRONOUS COMPUTATIONS.
  22. Eli Gafni
  23. Computer Science Department
  24. UCLA
  25.  
  26. ABSTRACT 
  27. Demarcation of the border between solvable and unsolvable distributed
  28. tasks under various models is the holy grail of the theory of 
  29. distributed computing. One of the most celebrated of these results 
  30. is (FLP) which established the impossibility of asynchronous 
  31. consensus that can tolerate a single undetected fail-stop processor. 
  32. Indeed, it has led to  the precise characterization of tasks solvable 
  33. and unsolvable under single fault. In this talk we show how to
  34. generalize FLP to multiple faults, and in the process resolves a 
  35. number of open problems.
  36.  
  37. We diverge from the classic FLP in studying the ``leader election''
  38. problem, and arguing impossibility within the wait-free context only.
  39. Then we show that the wait-free version t-equivalent to the 
  40. non-wait-free one.  Concentrating on the wait-free version for 
  41. impossibility allows us to deal with bounded executions and views 
  42. of processors there in.  We prove the impossibility using a variant 
  43. of the k-dimensional Sperner Lemma.  When k=1 we obtain a completely 
  44. different simple proof of the FLP result.
  45.  
  46. We show that ``multiple leader election'' is fundamental by reducing
  47. to it the previously suggested problems of k-set consensus, 
  48. k-set test-and- set, and renaming, thus resolving when these problems
  49. are solvable and when  they are not.  A by-product of our proof 
  50. technique is a wait-free read/write simulation of t-resilient
  51. computation by t+1-processors, which shows that resilient computations 
  52. can be investigated by concentrating on the corresponding waitfree
  53. computation.
  54.  
  55. (Joint work with Elizabeth Borowsky)
  56.