Майкл Джон Фишер (родился в 1942 году) — американский учёный-компьютерщик , работающий в областях распределённых вычислений , параллельных вычислений , криптографии , алгоритмов и структур данных , а также сложности вычислений .
Фишер родился в 1942 году в Энн-Арборе , штат Мичиган , США.
Он получил степень бакалавра наук по математике в Мичиганском университете в 1963 году. Фишер изучал прикладную математику в Гарвардском университете , получив степень магистра в 1965 году и степень доктора философии в 1968 году. Руководителем докторской диссертации Фишера в Гарварде была Шейла Грейбах .
Получив докторскую степень, Фишер был доцентом кафедры компьютерных наук в Университете Карнеги-Меллона в 1968–1969 годах, доцентом кафедры математики в Массачусетском технологическом институте (MIT) в 1969–1973 годах и доцентом кафедры электротехники в MIT в 1973–1975 годах. В MIT он руководил докторантами, которые стали выдающимися компьютерными учёными, включая Дэвида С. Джонсона , Фрэнсис Яо и Майкла Хаммера .
В 1975 году Фишер был номинирован на должность профессора компьютерных наук в Вашингтонском университете . С 1981 года он является профессором компьютерных наук в Йельском университете , где среди его студентов была Ребекка Н. Райт . Фишер был главным редактором журнала ACM в 1982–1986 годах. [1] [2] В 1996 году он был избран членом Ассоциации вычислительной техники (ACM). [3]
Работа Фишера 1985 года с Нэнси А. Линч и Майклом С. Патерсоном [4] по проблемам консенсуса получила премию PODC Influential-Paper Award в 2001 году. [5] Их работа показала, что в асинхронной распределенной системе консенсус невозможен, если один процессор выходит из строя. Дженнифер Уэлч пишет, что «Этот результат оказал монументальное влияние на распределенные вычисления, как в теории, так и на практике. Разработчики систем были мотивированы прояснить свои заявления относительно того, при каких обстоятельствах работают системы». [5]
Фишер был председателем программы первого Симпозиума по принципам распределенных вычислений (PODC) в 1982 году; [6] в настоящее время PODC является ведущей конференцией в этой области. В 2003 году сообщество распределенных вычислений отметило 60-летие Фишера, организовав серию лекций во время 22-го PODC, [7] с Лесли Лэмпортом , Нэнси Линч, Альбертом Р. Мейером и Ребеккой Райт в качестве докладчиков.
В 1980 году Фишер и Ричард Э. Ладнер [8] представили параллельный алгоритм для эффективного вычисления префиксных сумм . Они показали, как построить схему, которая вычисляет префиксные суммы; в схеме каждый узел выполняет сложение двух чисел. С их конструкцией можно выбрать компромисс между глубиной схемы и количеством узлов. [9] Однако те же самые конструкции схем уже изучались гораздо раньше советскими математиками. [10] [11]
Фишер проделал многогранную работу в области теоретической информатики в целом. Ранние работы Фишера, включая его докторскую диссертацию, были сосредоточены на синтаксическом анализе и формальных грамматиках . [12] Одна из наиболее цитируемых работ Фишера посвящена сопоставлению строк . [13] Уже во время обучения в Мичигане Фишер изучал структуры данных непересекающихся множеств вместе с Бернардом Галлером . [14]
Фишер является одним из пионеров электронного голосования . В 1985 году Фишер и его ученик Джош Коэн Беналох [15] представили одну из первых схем электронного голосования. [16]
Другие вклады, связанные с криптографией, включают изучение проблем обмена ключами и протокола для забывчивой передачи . [16] В 1984 году Фишер, Сильвио Микали и Чарльз Ракофф [17] представили улучшенную версию протокола Майкла О. Рабина для забывчивой передачи.