Майкл Дж. Фишер
Майкл Джон Фишер (род. 1942) — американский ученый-компьютерщик , работающий в области распределенных вычислений , параллельных вычислений , криптографии , алгоритмов и структур данных , а также сложности вычислений .
Ранний период жизни
[ редактировать ]Фишер родился в 1942 году в Анн-Арборе , штат Мичиган , США.
Он получил бакалавра степень математики в Мичиганском университете в 1963 году. Фишер получил степень магистра и доктора философии в области прикладной математики в Гарвардском университете ; он получил степень магистра в 1965 году и доктора философии в 1968 году. Научным руководителем Фишера в Гарварде была Шейла Грейбах .
Карьера
[ редактировать ]После получения докторской степени Фишер был доцентом кафедры информатики в Университете Карнеги-Меллона в 1968–1969 годах, доцентом математики в Массачусетском технологическом институте (MIT) в 1969–1973 годах и доцентом кафедры электротехники в Массачусетском технологическом институте в 1969–1973 годах. 1973–1975. В Массачусетском технологическом институте он руководил докторантами, которые стали выдающимися учеными-компьютерщиками, в том числе Дэвидом С. Джонсоном , Фрэнсис Яо и Майклом Хаммером .
В 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] представил улучшенную версию протокола Майкла О. Рабина для передачи по незнанию.
Публикации
[ редактировать ]- Галлер, Бернард А .; Фишер, Майкл Дж. (1964). «Улучшенный алгоритм эквивалентности» . Коммуникации АКМ . 7 (5): 301–303. дои : 10.1145/364099.364331 . S2CID 9034016 . . [12]
- Вагнер, Роберт А.; Фишер, Майкл Дж. (1974). «Проблема построчной коррекции» . Журнал АКМ . 21 (1): 168–173. дои : 10.1145/321796.321811 . S2CID 13381535 . . [18]
- Ладнер, Ричард Э.; Фишер, Майкл Дж. (1980). «Параллельное вычисление префиксов» . Журнал АКМ . 27 (4): 831–838. дои : 10.1145/322217.322232 . S2CID 207568668 . . [12] [19]
- Фишер, Майкл Дж.; Линч, Нэнси А .; Патерсон, Майкл С. (1985). «Невозможность распределенного консенсуса при одном неисправном процессе» . Журнал АКМ . 32 (2): 374–382. дои : 10.1145/3149.214121 . S2CID 207660233 . . [20] [21]
- Коэн, Джош Д.; Фишер, Майкл Дж. (1985). «Надежная и проверяемая криптографически безопасная схема выборов». 26-й ежегодный симпозиум по основам информатики (SFC, 1985) . стр. 372–382. дои : 10.1109/SFCS.1985.2 . ISBN 0-8186-0644-4 . . [16]
- Фишер, MJ; Микали, С. ; Ракофф, К. (1996). «Безопасный протокол для незаметной передачи (расширенное резюме)» . Журнал криптологии . 9 (3): 191–195. дои : 10.1007/BF00208002 . S2CID 6333850 . . [16]
Примечания
[ редактировать ]- ^ «Журнал ACM (JACM), том 30, выпуск 1 (январь 1983 г.)» . Портал АКМ . Проверено 6 июля 2009 г.
- ^ «Журнал ACM (JACM), том 33, выпуск 3 (июль 1986 г.)» . Портал АКМ . Проверено 6 июля 2009 г.
- ^ «Стипендиаты ACM» . АКМ . Архивировано из оригинала 1 января 2009 г. Проверено 6 июля 2009 г. «ACM: Премия Fellows / Майкл Дж. Фишер» . АКМ . Проверено 6 июля 2009 г. «За выдающийся технический вклад в теоретическую информатику и за преданную службу сообществу информатики».
- ^ Фишер, Линч и Патерсон (1985)
- ↑ Перейти обратно: Перейти обратно: а б «Награда PODC за влиятельную бумагу: 2001» . Проверено 6 июля 2009 г.
- ^ «Хронологическая история СИГОПС» . АСМ СИГОПС . Проверено 6 июля 2009 г.
- ^ «Двадцать второй симпозиум ACM по принципам распределенных вычислений (PODC 2003), 13–16 июля 2003 г., Бостон, Массачусетс» . Проверено 6 июля 2009 г.
- ^ Ладнер и Фишер (1980) .
- ^ Харвуд, Аарон (2003). «Параллельный префиксный алгоритм Ладнера и Фишера» . Сети и сложность параллельной обработки – Примечания . Архивировано из оригинала 4 марта 2016 г. Проверено 7 июля 2009 г. .
- ^ Оффман, Ю.П. (1962). «Об алгоритмической сложности дискретных функций». Докл. Сов. акад. наук. (на русском языке). 145 (1): 48–51. . Английский перевод на сов. Физ. Докл. 7 (7): 589–591 1963.
- ^ Крапченко А.Н. (1970). «Асимптотическая оценка времени сложения параллельного сумматора». Сист. Теория Рес . 19 : 105–122. .
- ↑ Перейти обратно: Перейти обратно: а б с Мейер, Альберт Р. (12 июля 2003 г.). «М. Дж. Фишер и др., Первое десятилетие: с середины 60-х по 70-е годы» (PDF) . Проверено 6 июля 2009 г. Слайды с PODC 2003.
- ^ Вагнер и Фишер (1974) .
- ^ Галлер и Фишер (1964)
- ^ Коэн и Фишер (1985)
- ↑ Перейти обратно: Перейти обратно: а б с д Райт, Ребекка Н. (2003). «Криптографические протоколы Фишера». Учеб. ПОДК 2003 . стр. 20–22. дои : 10.1145/872035.872039 . .
- ^ Фишер, Микали и Ракофф (1996) , первоначально представлено в 1984 году.
- ^ «1592 цитаты» . Google Академик . Проверено 6 июля 2009 г.
- ^ «726 цитат» . Google Академик . Проверено 7 июля 2009 г.
- ^ Премия PODC Influential-Paper в 2001 году.
- ^ «2431 цитирование» . Google Академик . Проверено 6 июля 2009 г.
Внешние ссылки
[ редактировать ]- Официальный сайт
- Майкл Джон Фишер в проекте «Математическая генеалогия»
- Майкл Дж. Фишер на DBLP библиографическом сервере
- Фишер, Майкл Дж. из zbMATH
- Фишер, Майкл Дж. из MathSciNet
| Международный | |
|---|---|
| Национальный | |
| академики | |
- 1942 года рождения
- Живые люди
- Исследователи распределенных вычислений
- Американские ученые-теоретики-компьютерщики
- Выпускники Колледжа литературы, науки и искусств Мичиганского университета
- Выпускники Гарвардского университета
- Преподаватели Йельского университета
- 1996 г. Члены Ассоциации вычислительной техники.
- Ученые из Анн-Арбора, штат Мичиган
- Лауреаты премии Дейкстры