Michael John Fischer (nacido en 1942) es un informático estadounidense que trabaja en los campos de la computación distribuida , la computación paralela , la criptografía , los algoritmos y estructuras de datos , y la complejidad computacional .
Fischer nació en 1942 en Ann Arbor , Michigan , Estados Unidos.
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 del 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 en 1968-1969, profesor asistente de matemáticas en el Instituto Tecnológico de Massachusetts (MIT) en 1969-1973 y profesor asociado de ingeniería eléctrica en el MIT. en 1973-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 alumnos se encontraba Rebecca N. Wright . Fischer se desempeñó como editor en jefe del Journal of the ACM en 1982-1986. [1] [2] Fue admitido 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 asíncrono, el consenso es imposible si hay un procesador. eso choca. 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 en qué circunstancias funcionan los sistemas”. [5]
Fischer fue el presidente del programa del primer Simposio sobre principios de informática distribuida (PODC) en 1982; [6] hoy en día, PODC es la conferencia líder en este campo. En 2003, la comunidad de informática 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 calcule las sumas de los prefijos; en el circuito, cada nodo realiza una suma de dos números. Al construirlos, 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 fueron estudiados mucho antes por los matemáticos soviéticos . [10] [11]
Fischer ha realizado un trabajo multifacético en 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 coincidencia 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 del voto electrónico . En 1985, Fischer y su alumno Josh Cohen Benaloh [15] presentaron uno de los primeros sistemas de votación electrónica. [dieciséis]
Otras contribuciones relacionadas con la criptografía incluyen el estudio de problemas de intercambio de claves y un protocolo para transferencia ajena . [16] En 1984, Fischer, Silvio Micali y Charles Rackoff [17] presentaron una versión mejorada del protocolo de Michael O. Rabin para la transferencia ajena.