Michael J. Fischer

Michael John Fischer (född 1942) är en datavetare som arbetar inom områdena distribuerad beräkning , parallell beräkning , kryptografi , algoritmer och datastrukturer och beräkningskomplexitet .

Karriär

Fischer föddes 1942 i Ann Arbor , Michigan , USA. Han fick sin BSc -examen i matematik från University of Michigan 1963. Fischer gjorde sina MA- och PhD -studier i tillämpad matematik vid Harvard University ; han fick sin magisterexamen 1965 och doktorsexamen 1968. Fischers doktorandhandledare vid Harvard var Sheila Greibach .

Efter att ha tagit sin doktorsexamen var Fischer biträdande professor i datavetenskap vid Carnegie-Mellon University 1968–1969, biträdande professor i matematik vid Massachusetts Institute of Technology (MIT) 1969–1973 och docent i elektroteknik vid MIT 1973–1975. Vid MIT handlede han doktorander som blev framstående datavetare, inklusive David S. Johnson , Frances Yao och Michael Hammer .

1975 nominerades Fischer till professor i datavetenskap vid University of Washington . Sedan 1981 har han varit professor i datavetenskap vid Yale University , där hans studenter inkluderade Rebecca N. Wright . Fischer tjänstgjorde som chefredaktör för Journal of the ACM 1982–1986. Han valdes in som Fellow i Association for Computing Machinery (ACM) 1996.

Arbete

Distribuerad databehandling

Fischers arbete 1985 med Nancy A. Lynch och Michael S. Paterson om konsensusproblem fick PODC Influential-Paper Award 2001. Deras arbete visade att i ett asynkront distribuerat system är konsensus omöjligt om det finns en processor som kraschar. Jennifer Welch skriver att "Detta resultat har haft en enorm inverkan i distribuerad datoranvändning, både teori och praktik. Systemdesigners var motiverade att förtydliga sina påståenden om under vilka omständigheter systemen fungerar.”

Fischer var programordförande för det första symposiet om principer för distribuerad datoranvändning ( PODC) 1982; numera är PODC den ledande konferensen på området. År 2003 hedrade den distribuerade datorgemenskapen Fischers 60-årsdag genom att organisera en föreläsningsserie under den 22:a PODC, med Leslie Lamport , Nancy Lynch, Albert R. Meyer och Rebecca Wright som talare.

Parallell beräkning

1980 presenterade Fischer och Richard E. Ladner en parallell algoritm för att effektivt beräkna prefixsummor . De visar hur man konstruerar en krets som beräknar prefixsummorna; i kretsen utför varje nod en addition av två tal. Med deras konstruktion kan man välja en avvägning mellan kretsdjupet och antalet noder. Men samma kretsdesign studerades redan mycket tidigare av sovjetiska matematiker.

Algoritmer och beräkningskomplexitet

Fischer har gjort mångfacetterat arbete inom teoretisk datavetenskap i allmänhet. Fischers tidiga arbete, inklusive hans doktorsavhandling, fokuserade på analys och formell grammatik . Ett av Fischers mest citerade verk handlar om strängmatchning . Redan under sina år i Michigan studerade Fischer disjunkta datastrukturer tillsammans med Bernard Galler .

Kryptografi

Fischer är en av pionjärerna inom elektronisk röstning . 1985 presenterade Fischer och hans elev Josh Cohen Benaloh ett av de första elektroniska röstningssystemen.

Andra bidrag relaterade till kryptografi inkluderar studiet av problem med nyckelutbyte och ett protokoll för omedveten överföring . 1984 presenterade Fischer, Silvio Micali och Charles Rackoff en förbättrad version av Michael O. Rabins protokoll för omedveten överföring.

Publikationer

•   Galler, Bernard A. ; Fischer, Michael J. (1964). "En förbättrad ekvivalensalgoritm" . Kommunikation från ACM . 7 (5): 301–303. doi : 10.1145/364099.364331 . S2CID 9034016 . .
•   Wagner, Robert A.; Fischer, Michael J. (1974). "Sträng-till-sträng-korrigeringsproblemet". Journal of the ACM . 21 (1): 168–173. doi : 10.1145/321796.321811 . S2CID 13381535 . .
•   Ladner, Richard E.; Fischer, Michael J. (1980). "Parallell prefixberäkning". Journal of the ACM . 27 (4): 831–838. doi : 10.1145/322217.322232 . S2CID 207568668 . .
•   Fischer, Michael J.; Lynch, Nancy A. ; Paterson, Michael S. (1985). "Omöjlighet av distribuerad konsensus med en felaktig process". Journal of the ACM . 32 (2): 374–382. doi : 10.1145/3149.214121 . S2CID 207660233 . .
•   Cohen, Josh D.; Fischer, Michael J. (1985). "26th Annual Symposium on Foundations of Computer Science (SFCS 1985)". 26:e årliga symposiet om grunderna för datavetenskap (sfcs 1985) . s. 372–382. doi : 10.1109/SFCS.1985.2 . ISBN 0-8186-0644-4 . .
•   Fischer, MJ; Micali, S .; Rackoff, C. (1996). "Ett säkert protokoll för den omedvetna överföringen (extended abstract)" . Journal of Cryptology . 9 (3): 191–195. doi : 10.1007/BF00208002 . S2CID 6333850 . .

externa länkar

• Officiell hemsida
• Michael John Fischer vid Mathematics Genealogy Project
• Michael J. Fischer på DBLP Bibliography Server
• Fischer, Michael J. vid zbMATH
• Fischer, Michael J. på MathSciNet