Michael J. Fischer - Michael J. Fischer

Michael John Fischer (narozen 1942) je a počítačový vědec který pracuje v oborech distribuované výpočty, paralelní výpočty, kryptografie, algoritmy a datové struktury, a výpočetní složitost.

Kariéra

Fischer se narodil v roce 1942 v Ann Arbor, Michigan, USA. Dostal svůj BSc vzdělání v oboru matematika z Michiganská univerzita v roce 1963. Fischer udělal své MA a PhD studuje v aplikovaná matematika na Harvardská Univerzita; získal magisterský titul v roce 1965 a titul PhD v roce 1968. Fischerovým školitelem na Harvardu byl Sheila Greibachová.

Po získání titulu PhD byl Fischer odborným asistentem na informatice na Carnegie-Mellon University v letech 1968–1969 odborný asistent matematiky na Massachusetts Institute of Technology (MIT) v letech 1969–1973 a docent elektrotechnika na MIT v letech 1973–1975. Na MIT dohlížel na doktorandy, kteří se stali významnými informatiky, včetně David S. Johnson, Frances Yao, a Michael Hammer.

V roce 1975 byl Fischer nominován za profesora počítačová věda na University of Washington. Od roku 1981 působí jako profesor informatiky na univerzita Yale, kde byli jeho studenti Rebecca N. Wright. Fischer sloužil jako šéfredaktor časopisu Deník ACM v letech 1982–1986.[1][2] Byl uveden jako Fellow of the Sdružení pro výpočetní techniku (ACM) v roce 1996.[3]

Práce

Distribuované výpočty

Fischer je známý svými příspěvky v oblasti distribuovaných výpočtů. Jeho 1985 práce s Nancy A. Lynch a Michael S.Paterson[4] na problémy s konsensem obdržel Cena PODC Influential-Paper v roce 2001.[5] Jejich práce ukázala, že v asynchronním distribuovaném systému je shoda nemožná, pokud dojde k chybě jednoho procesoru. Jennifer Welch píše, že „tento výsledek měl monumentální dopad na distribuované výpočty, a to jak v teorii, tak v praxi. Návrháři systémů byli motivováni objasnit svá tvrzení ohledně podmínek, za kterých systémy fungují. “[5]

Fischer byl předsedou programu prvního Symposium on Principles of Distributed Computing (PODC) v roce 1982;[6] v současné době je PODC přední konferencí v oboru. V roce 2003 komunita distribuované výpočetní techniky oslavila Fischerovy 60. narozeniny uspořádáním přednáškového cyklu během 22. PODC,[7] s Leslie Lamport, Nancy Lynch, Albert R. Meyer a Rebecca Wright jako řečníci.

Paralelní výpočty

V roce 1980 Fischer a Richard E. Ladner[8] představil a paralelní algoritmus pro výpočet součty prefixů efektivně. Ukazují, jak sestrojit obvod, který počítá součty předpon; v obvodu provádí každý uzel sčítání dvou čísel. Díky jejich konstrukci lze zvolit kompromis mezi hloubkou obvodu a počtem uzlů.[9] Stejné návrhy obvodů však byly již studovány mnohem dříve v roce sovětský matematika.[10][11]

Algoritmy a výpočetní složitost

Fischer provedl mnohostrannou práci v teoretické informatice obecně. Fischerova raná práce, včetně jeho disertační práce, byla zaměřena na analýza a formální gramatiky.[12] Jedna z nejcitovanějších Fischerových prací se zabývá shoda řetězce.[13] Fischer už během let v Michiganu studoval disjunktní datové struktury dohromady s Bernard Galler.[14]

Kryptografie

Fischer je jedním z průkopníků v oblasti elektronické hlasování. V roce 1985 Fischer a jeho student Josh Cohen Benaloh[15] představil jeden z prvních schémat elektronického hlasování.[16]

Mezi další příspěvky týkající se kryptografie patří studium výměna klíčů problémy a protokol pro lhostejný přenos.[16] V roce 1984 Fischer, Silvio Micali, a Charles Rackoff[17] představil vylepšenou verzi Michael O. Rabin Protokol pro lhostejný přenos.

Publikace

  • Galler, Bernard A.; Fischer, Michael J. (1964). Msgstr "Vylepšený algoritmus ekvivalence". Komunikace ACM. 7 (5): 301–303. doi:10.1145/364099.364331. S2CID  9034016.CS1 maint: ref = harv (odkaz).[12]
  • Wagner, Robert A .; Fischer, Michael J. (1974). Msgstr "Problém s opravou řetězce na řetězec". Deník ACM. 21 (1): 168–173. doi:10.1145/321796.321811. S2CID  13381535.CS1 maint: ref = harv (odkaz).[18]
  • Ladner, Richard E .; Fischer, Michael J. (1980). Msgstr "Výpočet paralelní předpony". Deník ACM. 27 (4): 831–838. doi:10.1145/322217.322232. S2CID  207568668.CS1 maint: ref = harv (odkaz).[12][19]
  • Fischer, Michael J .; Lynch, Nancy A.; Paterson, Michael S. (1985). "Nemožnost distribuované shody s jedním vadným procesem". Deník ACM. 32 (2): 374–382. doi:10.1145/3149.214121. S2CID  207660233.CS1 maint: ref = harv (odkaz).[20][21]
  • Cohen, Josh D .; Fischer, Michael J. (1985). "Robustní a ověřitelné kryptograficky bezpečné volební schéma". 26. výroční sympozium o základech informatiky (sfcs 1985). 372–382. doi:10.1109 / SFCS.1985.2.CS1 maint: ref = harv (odkaz).[16]
  • Fischer, M. J .; Micali, S.; Rackoff, C. (1996). "Zabezpečený protokol pro lhostejný přenos (rozšířený abstrakt)". Journal of Cryptology. 9 (3): 191–195. doi:10.1007 / BF00208002. S2CID  6333850.CS1 maint: ref = harv (odkaz).[16]

Poznámky

  1. ^ „Journal of the ACM (JACM), Volume 30, 1. vydání (leden 1983)“. Portál ACM. Citováno 2009-07-06.
  2. ^ „Journal of the ACM (JACM), Volume 33, Issue 3 (July 1986)“. Portál ACM. Citováno 2009-07-06.
  3. ^ „Členové ACM“. ACM. Archivovány od originál dne 01.01.2009. Citováno 2009-07-06.„ACM: Fellows Award / Michael J Fischer“. ACM. Citováno 2009-07-06. „Za vynikající technické příspěvky k teoretické informatice a za oddanou službu komunitě informatiky.“
  4. ^ Fischer, Lynch & Paterson (1985)
  5. ^ A b „Cena PODC Influential Paper Award: 2001“. Citováno 2009-07-06.
  6. ^ „Chronologická historie SIGOPS“. ACM SIGOPS. Citováno 2009-07-06.
  7. ^ „Dvacáté druhé sympózium ACM o zásadách distribuovaného výpočtu (PODC 2003), 13. – 16. Července 2003, Boston, Massachusetts“. Citováno 2009-07-06.
  8. ^ Ladner & Fischer (1980).
  9. ^ Harwood, Aaron (2003). „Algoritmus paralelní předpony Ladner a Fischer“. Sítě a složitost paralelního zpracování - poznámky. Archivovány od originál dne 04.03.2016. Citováno 2009-07-07..
  10. ^ Offman, Y. P. (1962). "O algoritmické složitosti diskrétních funkcí". Dokl. Sov. Acad. Sci. (v Rusku). 145 (1): 48–51.CS1 maint: ref = harv (odkaz). Anglický překlad v Sov. Phys. Dokl. 7 (7): 589–591 1963.
  11. ^ Krapchenko, A. N. (1970). "Asymptotický odhad doby přidání paralelního sčítače". Syst. Theory Res. 19: 105–122.CS1 maint: ref = harv (odkaz).
  12. ^ A b C Meyer, Albert R. (12. července 2003). „M. J. Fischer a kol., První desetiletí: polovina 60. až 70. let“ (PDF). Citováno 2009-07-06. Prezentace z PODC 2003.
  13. ^ Wagner & Fischer (1974).
  14. ^ Galler & Fischer (1964)
  15. ^ Cohen & Fischer (1985)
  16. ^ A b C d Wright, Rebecca N. (2003). "Fischerovy kryptografické protokoly". Proc. PODC 2003. str. 20–22. doi:10.1145/872035.872039.CS1 maint: ref = harv (odkaz).
  17. ^ Fischer, Micali a Rackoff (1996), původně představený v roce 1984.
  18. ^ „1592 citací“. Google Scholar. Citováno 2009-07-06.
  19. ^ „726 citací“. Google Scholar. Citováno 2009-07-07.
  20. ^ Cena PODC Influential-Paper v roce 2001.
  21. ^ „2431 citací“. Google Scholar. Citováno 2009-07-06.

externí odkazy