В 2015 году старший научный сотрудник ИППИ РАН, профессор Университета Мэрилэнда (США) Александр Барг вместе с Ицхаком Тамо из Тель-Авивского Университета (Израиль) получили одну из самых престижных премий в области теории информации и теории кодирования IEEE Information Theory Society Paper Award за статью в журнале IEEE Transactions on Information Theory, в которой были опубликованы результаты обширного исследования кодов с локальным восстановлением. В текущем году в том же журнале вышла совместная статья Тамо, Барга и старшего научного сотрудника ИППИ РАН Алексея Фролова, в которой предложены границы параметров для таких кодов, применяемых в распределенных системах хранения данных.

В современном мире практически любая информация — как на персональных компьютерах, так и в виртуальных хранилищах (социальные сети, «облака») — распределена на нескольких серверах или дисках. Это делается для того, чтобы обезопасить пользователей от потери данных, ведь выход из строя дисков является частым явлением. В современных распределенных системах применяются следующие методы защиты данных:

1) дублирование данных (т.н. back-up) на нескольких дисках. Если один из них выходит из строя, то для восстановления хранящейся на нем информации достаточно обратиться к одному диску с копией или, по-другому, служебной информацией. Время восстановления минимальное, однако, общий объем информации очень большой, например, если данные повторяются 3 раза, то объем служебной информации — 200 процентов.

2) использование кодов Рида-Соломона. В это случае объем служебной информации минимален, но восстановление происходит значительно дольше. К примеру, Facebook использует код Рида-Соломона с параметрами (14, 10). В этом случае объем служебной информации — 40 процентов, но для восстановления одного диска нужно считать данные с 10 других.

Наиболее частым явлением является выход из строя именно одного диска, поэтому возникает задача построения кодов со свойством локального восстановления. Такие коды должны быть способны восстановить один вышедший из строя диск с минимальным числом обращений к другим дискам. Объем служебной информации должен быть минимален.

Коды с локальным восстановлением впервые были предложены в статье сотрудников компании Microsoft П. Гопалана, С. Еханина и др., которые установили оценку минимального объема служебной информации при таком кодировании. В своей работе Александр Барг вместе со своим постдоком Ицхаком Тамо предложили общий алгебраический метод кодирования данных, достигающий этой оценки, т.е. обладающий наилучшей возможной эффективностью. В статье, опубликованной в июньском номере журнала, Тамо, Барг и Фролов исследовали обобщение кодов с локальным восстановлением и получили нижние и верхние границы для параметров кодов с многими восстанавливающими множествами, таких как объем служебной информации и минимальное расстояние.

«Мы рассматриваем случай, когда для каждого диска (символа большого алфавита) имеется несколько восстанавливающих множеств дисков. Это свойство гарантирует высокую доступность данных, к которым происходит частое обращение, ведь при выходе из строя диска, разные пользователи могут восстановить этот диск, обращаясь к разным серверам со служебными данными. Таким образом, достигается оптимальное распределение нагрузки в системе» — рассказал о проделанной работе Алексей Фролов.

Основная часть работы над статьей велась во время стажировки Алексея Фролова в университете Мэриленда в 2015 году.

Лауреатами премии IEEE Information Theory Society Paper Award за лучшие опубликованные работы по теории информации в разные годы становились сотрудники ИППИ РАН:

Валерий Гоппа (1972, 1973)

● Борис Цыбаков и Валерий Михайлов (1981)

Михаил Цфасман и Сергей Влэдуц (1983)

Юрий Штарьков (1996)

Премию Communications Society & Information Theory Society Joint Paper Award в 2012 году получил Камиль Зигангиров.

Выдающийся ученый, основатель Лаборатории №1 ИППИ РАН Марк Пинскер становился лауреатом самых престижных премий IEEE: премии Шеннона (1978) и золотой медали Хэмминга (1996).

ИППИ РАН — один из «пионеров» мирового развития теории кодирования и главный российский центр, где в настоящее время ведутся фундаментальные исследования в этой области, которые успешно сочетаются с практическими разработками по применению помехоустойчивого кодирования в современных телекоммуникационных системах и устройствах.

IEEE (Институт инженеров электротехники и электроники) является крупнейшей в мире профессиональной ассоциацией, которая насчитывает более 400 тыс. членов. Корни IEEE восходят к 1884 году, когда был организован Американский институт инженеров-электриков. IEEE публикует почти треть технической литературы в мире в области электротехники, информатики и электроники. Каждый год более 100 000 технических специалистов посещают более 1600 конференций, спонсируемых IEEE.