Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Майкл Джон Фишер (родился в 1942 г.) - ученый-компьютерщик , работающий в области распределенных вычислений , параллельных вычислений , криптографии , алгоритмов и структур данных , а также сложности вычислений .

Карьера [ править ]

Фишер родился в 1942 году в Анн-Арборе , штат Мичиган , США. Он получил степень бакалавра математики в Мичиганском университете в 1963 году. Фишер получил степень магистра и доктора наук по прикладной математике в Гарвардском университете ; он получил степень магистра в 1965 году и доктора философии в 1968 году. Руководителем PhD Фишера в Гарварде была Шейла Грейбах .

После получения докторской степени Фишер был доцентом кафедры информатики в Университете Карнеги-Меллона в 1968–1969 годах, доцентом математики в Массачусетском технологическом институте (MIT) в 1969–1973 годах и доцентом кафедры электротехники в Массачусетском технологическом институте. в 1973–1975 гг. В Массачусетском технологическом институте он руководил докторантами, ставшими известными компьютерными учеными, в том числе Дэвидом С. Джонсоном , Фрэнсис Яо и Майклом Хаммером .

В 1975 году Фишер был назначен профессором информатики в Университете штата Вашингтон . С 1981 года он был профессором информатики в Йельском университете , среди его учеников была Ребекка Н. Райт . Фишер был главным редактором журнала ACM в 1982–1986 гг. [1] [2] Он был назначен членом Ассоциации вычислительной техники (ACM) в 1996 году. [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). «Улучшенный алгоритм эквивалентности». Коммуникации ACM . 7 (5): 301–303. DOI : 10.1145 / 364099.364331 . S2CID  9034016 .. [12]
  • Вагнер, Роберт А .; Фишер, Майкл Дж. (1974). «Проблема исправления строки в строку». Журнал ACM . 21 (1): 168–173. DOI : 10.1145 / 321796.321811 . S2CID  13381535 .. [18]
  • Ladner, Ричард Э .; Фишер, Майкл Дж. (1980). «Параллельное вычисление префикса». Журнал ACM . 27 (4): 831–838. DOI : 10.1145 / 322217.322232 . S2CID  207568668 .. [12] [19]
  • Фишер, Майкл Дж .; Линч, Нэнси А .; Патерсон, Майкл С. (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом». Журнал ACM . 32 (2): 374–382. DOI : 10.1145 / 3149.214121 . S2CID  207660233 .. [20] [21]
  • Коэн, Джош Д .; Фишер, Майкл Дж. (1985). «Надежная и проверяемая криптографически безопасная схема выборов». 26-й ежегодный симпозиум по основам информатики (sfcs 1985) . С. 372–382. DOI : 10.1109 / SFCS.1985.2 .. [16]
  • Фишер, MJ; Микали, С .; Ракофф, К. (1996). «Безопасный протокол для передачи без внимания (расширенное резюме)». Журнал криптологии . 9 (3): 191–195. DOI : 10.1007 / BF00208002 . S2CID  6333850 .. [16]

Заметки [ править ]

  1. ^ «Журнал ACM (JACM), том 30, выпуск 1 (январь 1983 г.)» . Портал ACM . Проверено 6 июля 2009 .
  2. ^ "Журнал ACM (JACM), Том 33, Выпуск 3 (июль 1986)" . Портал ACM . Проверено 6 июля 2009 .
  3. ^ "Стипендиаты ACM" . ACM . Архивировано из оригинала на 2009-01-01 . Проверено 6 июля 2009 ."ACM: Премия стипендиатов / Майкл Дж. Фишер" . ACM . Проверено 6 июля 2009 . «За выдающийся технический вклад в теоретическую информатику и за самоотверженное служение сообществу компьютерных наук».
  4. ^ Фишер, Линч и Патерсон (1985)
  5. ^ a b «Влиятельная бумажная премия PODC: 2001» . Проверено 6 июля 2009 .
  6. ^ «Хронологическая история СИГОПС» . ACM SIGOPS . Проверено 6 июля 2009 .
  7. ^ "Двадцать второй симпозиум ACM по принципам распределенных вычислений (PODC 2003), 13-16 июля 2003 г., Бостон, Массачусетс" . Проверено 6 июля 2009 .
  8. ^ Ладнер & Fischer (1980) .
  9. ^ Харвуд, Аарон (2003). «Алгоритм параллельного префикса Ладнера и Фишера» . Сети и сложность параллельной обработки - Примечания . Архивировано из оригинала на 2016-03-04 . Проверено 7 июля 2009 ..
  10. ^ Оффман, YP (1962). «Об алгоритмической сложности дискретных функций». Докл. Сов. Акад. Sci. (на русском). 145 (1): 48–51.. Английский перевод в сов. Phys. Докл. 7 (7): 589–591 1963.
  11. ^ Krapchenko, А. Н. (1970). «Асимптотическая оценка времени сложения параллельного сумматора». Syst. Теория Res . 19 : 105–122..
  12. ^ a b c Мейер, Альберт Р. (12 июля 2003 г.). «MJ Fischer, et al., Первое десятилетие: середина 60-х - 70-е годы» (PDF) . Проверено 6 июля 2009 . Слайды из PODC 2003.
  13. ^ Вагнер и Фишер (1974) .
  14. ^ Галлер и Фишер (1964)
  15. ^ Коэн и Фишер (1985)
  16. ^ a b c d Райт, Ребекка Н. (2003). «Криптографические протоколы Фишера». Proc. PODC 2003 . С. 20–22. DOI : 10.1145 / 872035.872039 ..
  17. ↑ Fischer, Micali & Rackoff (1996) , первоначально представленная в 1984 году.
  18. ^ "1592 цитаты" . Google Scholar . Проверено 6 июля 2009 .
  19. ^ «726 цитат» . Google Scholar . Проверено 7 июля 2009 .
  20. ^ Премия PODC Influential-Paper в 2001 году.
  21. ^ "2431 цитата" . Google Scholar . Проверено 6 июля 2009 .

Внешние ссылки [ править ]

  • Официальный веб-сайт
  • Майкл Джон Фишер на проекте « Математическая генеалогия»
  • Майкл Дж. Фишер на сервере библиографии DBLP
  • Фишер, Майкл Дж на zbMATH
  • Фишер, Майкл Дж на MathSciNet