Michael John Fischer (nacido en 1942) es un científico de la computación que trabaja en los campos de la computación distribuida , computación paralela , criptografía , algoritmos y estructuras de datos , y complejidad computacional .
Carrera profesional
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 ciencias de la computación en la Universidad Carnegie-Mellon en 1968-1969, profesor asistente de matemáticas en el Instituto de Tecnología de Massachusetts (MIT) en 1969-1973 y profesor asociado de ingeniería eléctrica en MIT en 1973-1975. En el MIT supervisó a estudiantes de doctorado que se convirtieron en científicos informáticos destacados, incluidos David S. Johnson , Frances Yao y Michael Hammer .
En 1975, Fischer fue nominado como profesor de informática en la Universidad de Washington . Desde 1981, ha sido profesor de informática en la Universidad de Yale , donde sus estudiantes incluyeron a 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 Asociación de Maquinaria de Computación (ACM) en 1996. [3]
Trabaja
Computación distribuída
Fischer es famoso por sus contribuciones en el campo de la computación distribuida. Su trabajo 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 mostró que en un sistema distribuido asincrónico, el consenso es imposible si hay un procesador que se estrella. 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 estaban motivados para aclarar sus afirmaciones sobre en qué circunstancias 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.
Computación paralela
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 una compensación entre la profundidad del circuito y el número de nodos. [9] Sin embargo, los mismos diseños de circuitos ya se estudiaron mucho antes en las matemáticas soviéticas . [10] [11]
Algoritmos y complejidad computacional
Fischer ha realizado un trabajo multifacético en informática teórica en general. El trabajo inicial de Fischer, incluida su tesis doctoral, se centró en el análisis sintáctico y las gramáticas formales . [12] Una de las obras más citadas de Fischer trata sobre la combinación de cadenas . [13] Ya durante sus años en Michigan, Fischer estudió estructuras de datos de conjuntos disjuntos junto con Bernard Galler . [14]
Criptografía
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. [dieciséis]
Otras contribuciones relacionadas con la criptografía incluyen el estudio de los problemas de intercambio de claves y un protocolo para la transferencia inconsciente . [16] En 1984, Fischer, Silvio Micali y Charles Rackoff [17] presentaron una versión mejorada del protocolo de Michael O. Rabin para transferencias inconscientes.
Publicaciones
- Galler, Bernard A .; Fischer, Michael J. (1964). "Un algoritmo de equivalencia mejorado". Comunicaciones de la ACM . 7 (5): 301-303. doi : 10.1145 / 364099.364331 . S2CID 9034016 .. [12]
- Wagner, Robert A .; Fischer, Michael J. (1974). "El problema de la corrección de cuerda a cuerda". Revista de la ACM . 21 (1): 168-173. doi : 10.1145 / 321796.321811 . S2CID 13381535 .. [18]
- Ladner, Richard E .; Fischer, Michael J. (1980). "Cálculo de prefijos en paralelo". Revista de la ACM . 27 (4): 831–838. doi : 10.1145 / 322217.322232 . S2CID 207568668 .. [12] [19]
- Fischer, Michael J .; Lynch, Nancy A .; Paterson, Michael S. (1985). "Imposibilidad de consenso distribuido con un proceso defectuoso". Revista de la ACM . 32 (2): 374–382. doi : 10.1145 / 3149.214121 . S2CID 207660233 .. [20] [21]
- Cohen, Josh D .; Fischer, Michael J. (1985). "Un esquema de elección criptográficamente seguro robusto y verificable". 26º Simposio anual sobre fundamentos de la informática (sfcs 1985) . págs. 372–382. doi : 10.1109 / SFCS.1985.2 .. [dieciséis]
- Fischer, MJ; Micali, S .; Rackoff, C. (1996). "Un protocolo seguro para la transferencia inconsciente (resumen ampliado)". Revista de criptología . 9 (3): 191-195. doi : 10.1007 / BF00208002 . S2CID 6333850 .. [dieciséis]
Notas
- ^ "Revista de la ACM (JACM), volumen 30, número 1 (enero de 1983)" . Portal ACM . Consultado el 6 de julio de 2009 .
- ^ "Revista de la ACM (JACM), volumen 33, número 3 (julio de 1986)" . Portal ACM . Consultado el 6 de julio de 2009 .
- ^ "Becarios ACM" . ACM . Archivado desde el original el 1 de enero de 2009 . Consultado el 6 de julio de 2009 ."ACM: Premio Fellows / Michael J Fischer" . ACM . Consultado el 6 de julio de 2009 . "Por contribuciones técnicas sobresalientes a la informática teórica y por el servicio dedicado a la comunidad informática".
- ^ Fischer, Lynch y Paterson (1985)
- ^ a b "Premio PODC Influential Paper Award: 2001" . Consultado el 6 de julio de 2009 .
- ^ "Una historia cronológica de SIGOPS" . SIGOPS ACM . Consultado el 6 de julio de 2009 .
- ^ "Vigésimo segundo simposio de ACM sobre principios de computación distribuida (PODC 2003), 13-16 de julio de 2003, Boston, Massachusetts" . Consultado el 6 de julio de 2009 .
- ^ Ladner y Fischer (1980) .
- ^ Harwood, Aaron (2003). "Algoritmo de prefijo paralelo de Ladner y Fischer" . Complejidad de redes y procesamiento paralelo - Notas . Archivado desde el original el 4 de marzo de 2016 . Consultado el 7 de julio de 2009 ..
- ^ Offman, YP (1962). "Sobre la complejidad algorítmica de funciones discretas". Dokl. Sov. Acad. Sci. (en ruso). 145 (1): 48–51.. Traducción inglesa en Sov. Phys. Dokl. 7 (7): 589–591 1963.
- ^ Krapchenko, AN (1970). "Estimación asintótica del tiempo de adición de un sumador paralelo". Syst. Teoría Res . 19 : 105-122..
- ^ a b c Meyer, Albert R. (12 de julio de 2003). "MJ Fischer, et al., La primera década: mediados de los 60 a los 70" (PDF) . Consultado el 6 de julio de 2009 . Diapositivas de PODC 2003.
- ^ Wagner y Fischer (1974) .
- ^ Galler y Fischer (1964)
- ^ Cohen y Fischer (1985)
- ^ a b c d Wright, Rebecca N. (2003). "Protocolos criptográficos de Fischer". Proc. PODC 2003 . págs. 20-22. doi : 10.1145 / 872035.872039 ..
- ^ Fischer, Micali & Rackoff (1996) , presentado originalmente en 1984.
- ^ "1592 citas" . Google Scholar . Consultado el 6 de julio de 2009 .
- ^ "726 citas" . Google Scholar . Consultado el 7 de julio de 2009 .
- ^ Premio PODC Influential-Paper en 2001.
- ^ "2431 citas" . Google Scholar . Consultado el 6 de julio de 2009 .
enlaces externos
- Página web oficial
- Michael John Fischer en el Proyecto de genealogía matemática
- Michael J. Fischer en el servidor de bibliografía DBLP
- Fischer, Michael J. en zbMATH
- Fischer, Michael J. en MathSciNet