Michael John Fischer (nacido en 1942) es un científico informático estadounidense que trabaja en los campos de la computación distribuida , la computación paralela , la criptografía , los algoritmos y las estructuras de datos y la complejidad computacional .
Fischer nació en 1942 en Ann Arbor , Michigan , EE.UU.
Recibió su licenciatura en matemáticas de la Universidad de Michigan en 1963. Fischer realizó sus estudios de maestría y doctorado en matemáticas aplicadas en la Universidad de Harvard ; recibió su maestría en 1965 y su doctorado en 1968. La supervisora de doctorado de Fischer en Harvard fue Sheila Greibach .
Después de recibir su doctorado, Fischer fue profesor asistente de informática en la Universidad Carnegie Mellon entre 1968 y 1969, profesor asistente de matemáticas en el Instituto Tecnológico de Massachusetts (MIT) entre 1969 y 1973, y profesor asociado de ingeniería eléctrica en el MIT entre 1973 y 1975. En el MIT supervisó a estudiantes de doctorado que se convirtieron en destacados científicos informáticos, entre ellos David S. Johnson , Frances Yao y Michael Hammer .
En 1975, Fischer fue nombrado profesor de informática en la Universidad de Washington . Desde 1981, ha sido profesor de informática en la Universidad de Yale , donde entre sus estudiantes se encontraba Rebecca N. Wright . Fischer se desempeñó como editor en jefe del Journal of the ACM entre 1982 y 1986. [1] [2] Fue incluido como miembro de la Association for Computing Machinery (ACM) en 1996. [3]
El trabajo de Fischer de 1985 con Nancy A. Lynch y Michael S. Paterson [4] sobre problemas de consenso recibió el premio PODC Influential-Paper Award en 2001. [5] Su trabajo demostró que en un sistema distribuido asincrónico, el consenso es imposible si hay un procesador que falla. Jennifer Welch escribe que “este resultado ha tenido un impacto monumental en la computación distribuida, tanto en la teoría como en la práctica. Los diseñadores de sistemas se sintieron motivados a aclarar sus afirmaciones sobre las circunstancias en las que funcionan los sistemas”. [5]
Fischer fue el presidente del programa del primer Simposio sobre Principios de Computación Distribuida (PODC) en 1982; [6] hoy en día, PODC es la conferencia líder en el campo. En 2003, la comunidad de computación distribuida honró el 60 cumpleaños de Fischer organizando una serie de conferencias durante el 22º PODC, [7] con Leslie Lamport , Nancy Lynch, Albert R. Meyer y Rebecca Wright como oradores.
En 1980, Fischer y Richard E. Ladner [8] presentaron un algoritmo paralelo para calcular sumas de prefijos de manera eficiente. Muestran cómo construir un circuito que calcula las sumas de prefijos; en el circuito, cada nodo realiza una suma de dos números. Con su construcción, se puede elegir un equilibrio entre la profundidad del circuito y el número de nodos. [9] Sin embargo, los mismos diseños de circuitos ya habían sido estudiados mucho antes por matemáticos soviéticos . [10] [11]
Fischer ha realizado un trabajo multifacético en la informática teórica en general. Los primeros trabajos de Fischer, incluida su tesis doctoral, se centraron en el análisis sintáctico y las gramáticas formales . [12] Uno de los trabajos más citados de Fischer trata sobre la comparación de cadenas . [13] Ya durante sus años en Michigan, Fischer estudió estructuras de datos de conjuntos disjuntos junto con Bernard Galler . [14]
Fischer es uno de los pioneros en el voto electrónico . En 1985, Fischer y su alumno Josh Cohen Benaloh [15] presentaron uno de los primeros esquemas de votación electrónica. [16]
Otras contribuciones relacionadas con la criptografía incluyen el estudio de problemas de intercambio de claves y un protocolo para transferencia inconsciente . [16] En 1984, Fischer, Silvio Micali y Charles Rackoff [17] presentaron una versión mejorada del protocolo de Michael O. Rabin para transferencia inconsciente.