Задачи 2013 года (1158847), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Множество контрольных точек называется строго консистентным, если во время егофиксации никаких обменов между процессами не было.2. Множество контрольных точек называется консистентным, если для любойзафиксированной операции приема сообщения, соответствующая операция посылки такжезафиксирована (нет сообщений-сирот).Простой метод фиксации консистентного множества контрольных точек фиксация локальной контрольной точки после каждой операции посылки сообщения.Синхронная фиксация контрольных точек и восстановление.Требование: надежная передача сообщений (сообщения всегда приходят, схема FIFO).Два вида точек – постоянная (уже точно установлена) и пробная – становится постояннойпосле окончания работы алгоритма.Сохранение:1) процесс создает пробную точку, шлет всемвсе создают пробную точку, отвечают процессу-инициаторуЗ.Ы. при этом нельзя посылать неслужебные сообщения2) процесс шлет всем информацию о создании новой постоянной точки, пробнаястановится постояннойОптимизация: если не было сообщений после последней контрольной точки, то можно несоздавать новуюВосстановление:1) инициатор шлет всем сообщение о готовке к откатувсе отвечают, что готовыЗ.Ы.

после этого до конца алгоритма не посылается неслужебных сообщений2) инициатор шлет сообщение об откате, все откатываютсяОптимизация: если не было сообщений с момента фиксации, то можно не откатываться.Асинхронный алгоритм.Предположение: есть стабильная область памяти, в которой хранится информация о всехприсланных и отосланных сообщениях.Точки создаются в произвольные моменты. Откат до консистентного состояния (когда всепринятые и отправленные сообщения совпадают) – множество контрольных точекнеконсистенто, может возникнуть эффект домино, но меньше нагрузки на создание точек.Получение строгой консистентности:- делаем нестрогую консистентность (по синхронному алгоритму)- при этом считаем количество отосланных сообщений каждому процессу- проверяем, все ли сообщения дошли до адресатов, для этого шлем им счетчикотосланных сообщений, если совпал – шлем «ок» процессу-инициатору консистентности!!!З.Ы. этот пункт можно так сделать: все шлют одному процессу сообщения сосчетчиками (9 сообщений), он все суммирует и шлет каждому процессу сообщение собщим количеством сообщений, которое тот должен был принять (9 сообщений), всеотвечают готовностью, если готовы (9 сообщений) Итого 27 дополнительных сообщений;координатора проверять не надо, так как он уже всем отправлял сообщения -> каналыпусты.Итого: T1 + 3n (Ts + a*Tb)Задача 2.Протоколы голосования.1) Существует кворум записи Nw > N/2, кворум чтения Nr: Nw + Nr > N (N –количество процессов).

Смысл в том, что мы должны быть уверены, что финальнаяверсия данных есть у Nw процессов, таким образом, если мы опросим Nrпроцессов, то из присланных ими данных обязательно будет один ответ с самойпоследней версией данных.2) Алгоритм:a. Запись: шлем всем(!) процессам запрос на модификацию – шлем M байтданных и K байт доп. информации (куда пишем данные, версия данных)Должны получить Vw ответов об успешной записи.b. Чтение – шлем запрос всем (можно, наверное, не всем, а только Nrпроцессам), получаем необходимые данные (шлем K байт – идентификаторданных)Решении Задачи:N - число байт.10 – число процессов, с которыми контактирует данный процесс = M2 – число записей = w10 – число чтений = rНакладные расходы сообщения (пускай 5 байт), в которых хранятся версия переменной иуказание области памяти = kНа запись: w[M(Ts + (N + k)*Tb) + Vw*(Ts + Tb)] – отсылка записи и ответы от заданногочисла процессовНа чтение: r[Vr(Ts + k *Tb) + Vr(Ts + N*Tb) ]– запрос на чтение у Vr процессов иполучение ответа от Vr процессов.Считаем Vr + Vw = 11, после чего минимизируем число сообщений для Vr и Vw (при Т =300).

Характеристики

Список файлов решённой задачи