Э́дсгер Ви́бе Де́йкстра (нидерл. Edsger Wybe Dijkstra — нидерландский учёный, труды которого оказали влияние на развитие информатики и информационных технологий; один из разработчиков концепции структурного программирования, исследователь формальной верификации и распределённых вычислений. Тьюринговский лауреат.
Премия Кнута — премия, присуждаемая с 1996 года за особый вклад в развитие основ информатики, названная в честь американского математика и автора книг о теории вычислительных систем Дональда Кнута. Премия вручается каждые полтора года и сопровождается денежным вознаграждением размером в 5000 долларов.
Премия Гёделя — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT, и EATCS, за выдающиеся труды по логике и теоретической информатике.
Лесли Лэмпорт — американский учёный в области информатики, первый лауреат премии Дейкстры. Разработчик LaTeX — популярного набора макрорасширений системы компьютерной вёрстки TeX, исследователь теории распределённых систем, темпоральной логики и вопросов синхронизации процессов во взаимодействующих системах. Лауреат Премии Тьюринга 2013 года.
Communications of the ACM (CACM) — ведущий ежемесячный журнал Ассоциации вычислительной техники (ACM), издаётся с 1957 года. Рассылается всем членам ассоциации, число которых более 80 тыс. Сочетает стили научно-популярного, профессионального и научного журналов: материалы ориентированы на максимально широкий круг читателей и охватывают все направления информатики, а наибольший фокус сосредоточен на практических результатах развития информационных технологий. Зачастую материалы являются обобщением ранее опубликованных исследований, в каждом номере публикуется одна или несколько статей из ранее выходивших в ACM Queue. Также публикуются письма читателей и наиболее примечательные заметки ведущих исследователей с сайта блогов ACM.
Логические часы — механизм определения хронологической и причинно-следственной связи событий в распределённых системах, не имеющих единых физических часов. Алгоритмы логических часов позволяют получать частичное упорядочение событий по времени и обнаруживать нарушения причинно-следственных связей. Состояние логических часов может включаться в состав внутренних сообщений, пересылаемых между узлами системы. Впервые предложен и реализован Лэмпортом в 1978 году, его работа была отмечена Премией Тьюринга 2013 года.
Часы Лэмпорта — алгоритм определения порядка событий в распределённой системе, разработанный Лэсли Лэмпортом в 1978 году, является прообразом векторных часов.
Паксос — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных. Данная задача используется, например, для утверждения транзакций в распределённых системах.
Теорема — эвристическое утверждение о том, что в любой реализации распределённых вычислений возможно обеспечить не более двух из трёх следующих свойств:
- согласованность данных — во всех вычислительных узлах в один момент времени данные не противоречат друг другу;
- доступность — любой запрос к распределённой системе завершается откликом, однако без гарантии, что ответы всех узлов системы совпадают;
- устойчивость к фрагментации — расщепление распределённой системы на несколько изолированных секций не приводит к некорректности отклика от каждой из секций.
Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления: последовательной, ветвлений и повторов или циклов.
Задача об обедающих философах — классический пример, используемый в информатике для иллюстрации проблем синхронизации при разработке параллельных алгоритмов и техник решения этих проблем.
Considered harmful — фразема, широко используемая в заголовках критических эссе по информатике и смежных дисциплинах. Вошла в оборот благодаря заметке «Go To Statement Considered Harmful» Эдсгера Дейкстры, опубликованной в мартовском выпуске журнала Communications of the ACM 1968 года, в которой автор критиковал чрезмерное использование оператора goto в языках программирования той эпохи и пропагандировал вместо него структурное программирование. Оригинальным заголовком письма, посланного в журнал, было «A Case Against the Goto Statement», но редактор Никлаус Вирт изменил заголовок на «Go To Statement Considered Harmful». Дональд Кнут в отношении нового заголовка письма саркастически сказал, что «доктор Гото [Goto] с улыбкой пожаловался, что им всегда пренебрегают».
Нэнси Энн Линч — американский учёный, профессор компьютерных науки и инженерии Массачусетского технологического института, известная прежде всего автоматами ввода-вывода — обобщением автоматов Мили на распределённые алгоритмы, позволяющим формально демонстрировать их корректность с помощью иерархических доказательств. На сегодняшний день существует много разновидностей автоматов ввода-вывода: временны́х, гибридных, вероятностных и динамических, все созданы самой Линч и её сотрудниками. Последними на 2016 год были предложены динамические автоматы ввода-вывода, моделирующие динамические системы и позволяющие создавать и уничтожать автоматы по мере вычисления, что существенно повышает их выразительность и приближает формализм к современному программному обеспечению. Динамические автоматы ввода-вывода могут объединяться в иерархическую систему, запускаться параллельно, переименовывать и скрывать события, порождать новые автоматы и поддерживать монотонность через семантическую типизацию.
Теория вычислительного обучения — это подобласть теории искусственного интеллекта, посвящённая разработке и анализу алгоритмов машинного обучения.
SIGACT — специальная группа в ACM, целью которой является поддержка исследований в теоретической информатике. Основана Патриком Фишером в 1968 году.
Морис Херлихи — американский ученый в области информатики, специализирующийся на теме синхронизации в мультипроцессорах. Херлихи внес вклад в такие области как теоретические основы неблокирующей синхронизации, линиаризируемые структуры данных, приложение комбинаторной топологии к распределенным вычислениям, а также программная транзакционная память. Он занимает должность профессора информатики в Брауновском Университете, где он работает с 1994 года.
Нир Шавит — израильский учёный в области информатики. Профессор факультета информатики в Тель-Авивском университете и профессор электротехники и информатики в Массачусетском технологическом институте.
Gossip — это группа протоколов в одноранговой компьютерной коммуникации, в которых распространение информации идёт способом, схожим с образом распространения эпидемий, и сводящимся к тому, что каждый или некоторые из узлов могут передавать обновляемые данные известным этому узлу соседям. Некоторые распределенные системы используют такой тип протокола, чтобы обеспечить распространение данных между всеми узлами распределённой системы. В некоторых сетях нет центрального реестра узлов, и использование gossip — единственный способ надёжно распространять между узлами общие данные. В качестве синонима этого термина также иногда используют словосочетание эпидемический протокол, имея ввиду, что сплетни и вирусы распространяются в обществе схожим способом.
Регулярные числа — это числа, которые равномерно делят степени 60 (или, что эквивалентно, степени 30). Например, 602 = 3600 = 48 × 75, поэтому и 48, и 75 являются делителями степени 60. Таким образом, они являются обычными числами. Эквивалентно, это числа, единственные простые делители которых равны 2, 3 и 5.
Консенсус в распределённых вычислениях — процесс согласования данных в распределённых вычислениях и многоагентных системах. Фундаментальной проблемой в распределённых вычислениях и многоагентных системах является достижение общей надёжности системы при наличии ряда ошибочных процессов. Это часто требует координации процессов или согласования некоторого значения данных, которое необходимо во время вычислений. Такой процесс принято называть достижением консенсуса.