автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Управление доступом к общим ресурсам в пиринговых системах

На правах рукописи

003486820

ОБЕЙДАТ АТЕФ АХМЕД

УПРАВЛЕНИЕ ДОСТУПОМ К ОБЩИМ РЕСУРСАМ В ПИРИНГОВЫХ СИСТЕМАХ

Специальности: 05.13.13 - Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

" 3 ДЕК 2009

Санкт-Петербург 2009

003486820

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет» на кафедре Вычислительной техники

Научный руководитель: Заслуженный деятель науки РФ, Заслуженный работник ВШ РФ, д.т.н., профессор Губарев Василий Василевич

Официальные оппоненты:

доктор технических наук, профессор Яковлев Сергей Алексеевич кандидат технических наук, доцент Данилов Виталий Иванович

Ведущая организация: ГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», г.Новосибирск

Защита состоится 23 декабря 2009г. в 15.00 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.238.01 Санкт-Петербургского государственного электротехнического университета им. В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан " " ноября 2009 г.

Ученый секретарь

совета по защите докторских

и кандидатских диссертаций

Пантелеев М.Г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Пиринговые сети (от англ. peer-to-peer (Р2Р) - ровня с ровней, равный с равным (Р2Р) или пользователь - пользователь (П2П)) - это среда, основанная на равноправии всех участников, среди которых нет специально выделенных серверов данных или приложений, а каждый его участник - узел (peer) является как клиентом (получателем информации), так и сервером (поставщиком информации). Иными словами Р2Р-сети являются распределенной дуальной системой (средой), содержащей взаимосвязаные узлы, способные к самоорганизации в сетевую технологию с целью разделения различных ресурсов (контентов, циклов процессоров, устройств хранения, полос пропускания и т.п.), самоадаптирующихся к отказам и переменному числу узлов, поддерживая при этом приемлемый уровень связности и производительности без необходимости в посредниках или поддержке глобального центрального сервера. Они изначально ориентированны на нестабильность, переменное количество узлов в сети, устойчивость к отказам и самоадаптацию. Их дуальность (двойственность) связана с тем, что, с одной стороны, это совокупность распределенных взаимосвязанных узлов, абсолютно равноправных с точки зрения функциональности и выполняемых задач, необязательно однородных, с другой, совокупность приложений, которые используют одни и те же объекты (ресурсы , диски, циклы процессоров, контент и т.п.).

В настоящее время резко возрос интерес к пиринговым сетям (П2П), в которых, посредством Интернета в качестве средств (среды) обмена неизменяемых объектов, используются такие системы как Kazaa, Gnutella и BitTorrent. Недавние исследования показывают, что в течение последних лет 70% трафика Интернета связаны с деятельностью пиринговых сетей. Это обусловлено тем, что использование пиринговых сетей для управления ресурсом даёт преимущества в виде уменьшения стоимости, хорошей масштабируемости и поддержки специальных сетей. Наряду с таким развитием появилась потребность в приложениях, позволяющих сотрудничать друг с другом большему количеству пользователей. До сих пор большинство решений связано с моделью «клиент-сервер», в которой сервер контролирует обновление общих данных приложения. Эта модель позволяет легко поддерживать одновременно доступ к ресурсам и аутентичность данных приложений, однако сервер становится точкой отказа системы и «узким местом», которое может препятствовать тому, чтобы приложение было доступно большому количеству пользователей.

Более перспективным является развитие децентрализованных сетей. Однако в них появляются такие проблемы как взаимное исключение, тиражирование и обеспечение аутентичности (тождественности) дубликатов динамически изменяемых объектов (файлов или вычислительных ресурсов). Эти проблемы особенно обостряются в силу следующих обстоятельств. 1) В связи с желанием выполнять с объектами исключающие друг друга одновременные действия, например, чтение и запись, изменение содержания

оригинала объекта одним пользователем и одновременное чтение его дубликата другим. 2) Из-за непредсказуемой изменчивости объектов, структуры сети, необходимости при этом обеспечения нужного тиражирования дубликатов и их аутентичности (тождественности) объекту.

Основные вопросы проблемы взаимного исключения одновременного доступа к общим ресурсам в вычислительных системах и сетях рассматриваются в работах L. Lamport., R. Agrawala, G. Ricart, A. Agrawala, M. Singhal, K. Raymond, M. Maekawa и др. В результате для централизованных вычислительных сетей предложено множество решений этой проблемы. Однако специфика динамично изменяемых децентрализованных пиринговых сетей не всегда позволяет эффективно использовать известные решения из-за различий в базовых моделях сетей, их строения и функционирования, отсутствия централизации, быстрой непредсказуемой изменчивости оригинальных объектов, требующих изменения дубликатов.

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

В связи с этим тема работы является актуальной и практически важной.

Целью работы является разработка и исследование модельного, алгоритмического и программного обеспечения эффективного бесконфликтного доступа в динамических пиринговых сетях к общим изменяемым объектам, т.е. доступа с гарантированным исключением одновременного выполнения противоречивых запросов на работу с одним и тем же объектом и обеспечением множественности и аутентичности его дубликатов.

В соответствии с поставленной целью решаются следующие задачи исследования:

1. Выбрать класс семейства пиринговых сетей, как базовую основу для разработки и исследования алгоритмов, рассматриваемых в диссертации, и создать для него системную модель. Выполнить анализ архитектурных особенностей выбранного семейства пиринговых сетей, провести систематизацию и исследование существующих методов и алгоритмов предоставления распределенного доступа к объектам в них.

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

3. Создать средства для оценки показателей качества предложенных алгоритмов и провести сравнительное исследование алгоритмов.

4. Опробовать разработанные алгоритмы доступа к дубликатам объектов

Методы исследования. Для решения задач, поставленных в диссертации, используются методы анализа эффективности функционирования распределенных вычислительных систем, элементов SWOT-анализа, математической статистики, имитационного моделирования.

Научная новизна полученных в диссертационной работе результатов состоит в следующем.

1. Создана формализованная системная модель класса рассматриваемых сетей.

2. Систематизированы и проанализированы существующие алгоритмы взаимного исключения одновременного доступа к общим объектам, тиражирования и обеспечения аутентичности дубликатов объектов в динамических пиринговых сетях.

3. Разработаны новые бесконфликтные алгоритмы доступа к общим ресурсам, обеспечивающие взаимное исключение одновременного доступа к запрашиваемому объекту: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).

4. Разработаны алгоритмы тиражирования и обеспечения аутентичности (непротиворечивости) дубликатов динамически изменяемых объектов.

5. Разработано программное обеспечение для имитационного исследования предложенных алгоритмов по основным показателям их качества, проведено апробирование и исследование алгоритмов.

Практическая ценность работы заключается в том, что:

1. Использование предложенных алгоритмов и методов позволяет разработчикам при написании Р2Р-приложений не беспокоиться о поддержании низкоуровневых механизмов защиты от одновременного доступа к совместно используемым объектам и об обеспечении аутентичности их дубликатов.

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

3. Предложенные алгоритмы взаимного исключения имеют меньшую сложность. Результаты имитации алгоритмов выявили, что они обладают намного большей масштабируемостью, требуют в среднем в 3-4 раза меньшего количества служебных сообщений.

4. Созданное на основе системы Free-pastry приложение позволяет обеспечить функционирование и тестирование предложенных алгоритмов.

Реализация работы. Созданный программный пакет, реализующий алгоритмы управления доступом к объектам в пиринговых сетях, был принят к

внедрению в компаниях, занимающихся разработкой и внедрением программных систем, - ООО «Инфо-Стрим» и ООО «ИДЕЛЬ» для решения задач исследования моделей проектируемых приложений. Результаты работы также используются в учебном процессе Новосибирского государственного технического университета (НГТУ), что подтверждено соответствующими документами, копии которых приведены в приложении к диссертации.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на: II Всероссийском смотре научных и творческих работ иностранных студентов и аспирантов, 28- 29 апреля, 2008 г., Томск, Россия; Международной конференции «The Third International Forum on Strategie Technologies (IFOST)», 23-29 июня, 2008 г., Новосибирск, Россия; Международной конференции «The 10th International Workshop on Computer Science and Information Technologies (CSIT)», 15-17 сентября, 2008г., Antalya, Turkey; Российской научной конференции «НАУКА, ТЕХНОЛОГИИ, ИННОВАЦИИ», 4-7 декабря,2008г., Новосибирск, Россия; XV международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА»// 26 - 27 февраля, 2009г., Москва, Россия; Всероссийской конференции «Винеровские чтения 2009» , 11 - 16 марта, 2009 г., Иркутск, Россия; Международной конференции «International Siberian Conference on Control and Communications (SIBCON-2009)», 27-28 марта , 2009 г., Томск, Россия; Седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии», 24-27 февраля, 2009г., ТПУ, г. Томск, Россия; II Всероссийской научно-практической конференции «Научная инициатива иностранных студентов и аспирантов российских вузов», 21- 22 мая, 2009г., ТПУ, г.Томск, Россия; Международной конференции «The Förth International Forum on Strategie Technologies (IFOST 2009)», 21-23 октября, 2009 г., Ho Chi Minh city, Vietnam.

На защиту выносятся следующие результаты

1. Эффективные алгоритмы бесконфликтного доступа к запрашиваемому объекту в децентрализованных пиринговых системах: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).

2. Алгоритмы тиражирования динамично получаемых дубликатов непредсказуемо изменяемых объектов с обеспечением их аутентичности.

3. Программное обеспечение для проведения имитационного исследования предложенных алгоритмов по выбранным показателям качества и результаты их исследования.

4. Программное обеспечение для работы в пиринговых сетях согласно предложенным алгоритмам.

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 15 работах, среди которых 2 публикации в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК, а также 13 докладов, перечисленных в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка литературы, включающего 104 наименования, из которых 88 иностранных, и пяти приложений. Текст диссертации изложен на 171 страницах, включает 34 рисунка и 7 таблиц. В приложении содержатся копии документов о внедрении и дипломов за участие в научно-технических конференциях.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертационной работы, формулируются цель и задачи исследования, указываются методы исследованная, приводятся сведения об основных результатах роботы, их практической ценности, внедрении и апробации.

В первой главе определяются основные понятия, используемые в диссертации; приводится обзор литературных источников и анализ имеющихся по теме диссертации результатов.

Изложен обзор клиентских информационно-вычислительных средств с особым выделением пиринговых приложений для совместного доступа к общим ресурсам. Дается классификация пиринговых систем.

Описывается задача взаимного исключения в Р2Р-сетях - исключения одновременного доступа к одним и тем же файлам (а в более общей постановке - к любым другим объектам (ресурсам) разных пользователей), т.е. одновременный допуск с критическими операциями более одного пользователя к одному и тому же объекту сети. Части файлов, которые могут подвергаться критическим операциям, оформляются в виде критических секций (КС) областей объектов соответствующих узлов. Выявлены недостатки и слабые стороны существующих алгоритмов.

Описываются показатели качества задач взаимного исключения в Р2Р системах и их характеристики. В качестве таких показателей выбраны: число сообщений, пересылаемых друг другу узлами во время использования критической секции; время Т0 ответа на запрос - интервал времени, в течение которого запрос ждет разрешение на работу с критической секцией после отправки сообщения ЗАПРОС; время Тзс задержки синхронизации - временной интервал между двумя успешными обращениями к критической секции; средняя задержка передачи сообщений Ти (они показывают, как скоро запросный узел может войти в критическую секцию); пропускная способность Ь - число запросов, обработанных за единицу времени.

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

Предлагается формализованная системная модель класса динамических пиринговых сетей, на основе которой будут рассматриваться разрабатываемые

далее алгоритмы. Основные положения модели. Система состоит из равноправных узлов р, каждый из которых может быть клиентом (получателем) и сервером (поставщиком) ресурсов. Каждому доступному пользователям объекту RJ (реальному файлу или вычислительному ресурсу) соответствует определенный набор узлов, содержащих его точные копии (дубликаты). Взаимодействие узлов между собой осуществляется согласно правилам работы Р2Р-сети, которые предписывают любому узлу посылать сообщения другим узлам. Дубликаты объекта всегда доступны, но их внутреннее состояние может быть случайно сброшено вследствие сбоя. После обнаружения сбоя дубликат вновь восстанавливается в сети с прежним значением идентификатора узла. Количество клиентов сети непредсказуемо и может быть очень большим. Предполагается, что клиенты не настроены злонамеренно. В сети может быть высокая динамичность (текучесть клиентов) - узлы могут входить и покидать сеть в любое время; клиенты и узлы, содержащие дубликаты, взаимодействуют друг с другом посредством сообщений, посылаемых через ненадежные каналы. Каждый объект Rt имеет уникальный идентификатор кп который используется как хэш текстового имени объекта. Хэш может быть вычислен с помощью конфликтоустойчивой хэш-функции, которая гарантирует равномерное распределение идентификаторов объекта. Каждый узел р. может определять идентификатор объекта Rr Любой пользователь, присоединенный к Интернету, может выступать в качестве узла после установки соответствующего программного обеспечения. Набор узлов формирует в Интернете оверлейную сеть. Узел для пользователя выступает в качестве точки доступа. Каждый узел может предоставлять в сети место для хранения информации, участвовать в маршрутизации запросов в пределах сети, предоставлять различные услуги другим узлам сети и/или получать доступ к объектам.

Во второй главе исследованы существующие решения взаимного исключения и описаны разработанные алгоритмы бесконфликтного доступа (взаимного исключения) к общим объектам для динамических пиринговых сетей. Были рассмотрены следующие алгоритмы: Сигма-протокол (Sigma), сквозной протокол (Е2Е) и несквозной протокол (Non-E2E). Проведено аналитическое исследование их свойств. Результаты сформулированы в виде теорем (С - число оверлейных операций, с помощью которых сообщение может быть послано от одного узла к другому, п - число дубликатов объектов).

Теорема 2.1 (Сигма-протокол ). Наибольшее число сообщений в Сигма-протоколе не превышает 5Сп.

Теорема 2.2 (Е2Е). Наибольшее число сообщений в Епс1-2-Епс1-протоколе не превышает 5Сп.

Теорема 2.3 (NonE2E). Наибольшее число сообщений в Non-End-2-End-протоколе не превышает 4Сп.

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

Выявлено, что алгоритмы Sigma и Е2Е не удовлетворяют требованиям отказоустойчивости и упорядоченности запросов, a Non-E2E не удовлетворяет требованию упорядоченности запросов.

Были предложены два новых алгоритма взаимного исключения, свободные от перечисленных недостатков, - алгоритм взаимного исключения «Узел-Координатор» (У2К) и древовидной алгоритм взаимного исключения (ДАВИ).

Алгоритм У2К основан на организации набора узлов и передаче сообщений только между запросными узлами и координатором (вместо передачи сообщения между запросным узлом и всеми узлами, хранящими дубликаты, как это было в существующих решениях, см. рис. 1).

Q Кооодиратоо

Кооснь ©

•Подкорневый

. (Щё В \в

(а) Существующие алгоритмы ' (б) Алгоритм У2К ' (В) Алгоритм ДАВИ Рис.1. Примеры реализации трех запросных операций предложенного и существующих алгоритмов; г, - узел, содержащий дубликат г, ; ПУ -промежуточный узел (подкорневой узел); ЗУ, - i'-ый запросный узел.

Блок-схема алгоритма приведена на рис. 2. Входными данными для алгоритма являются: Щ - объект с идентификатором j\ q - идентификатор клиента , владеющего объектом R/, tcj - время получения полномочий (разрешения) на доступ к объекту Rf teo - временная метка, переменная состояния, всегда хранящаяся в р,\ Qj - полная очередь запросов, изначально пустая, Qj используется только координатором; pQj - частичный перечень ожидающих запросов, который содержит сведения о предыдущих запросах узлов, упорядоченных по времени; pQj используется запросным узлом; .? -идентификатор источника сообщения запросного узла; d - идентификатор узла доставки сообщения; Тип - тип сообщения ; М - сообщения между узлами, которые обычно содержат: d; t„„;pQj; (Cj,tcj); Tun ).

Сначала запросные узлы посылают запрос координатору vj (на рис. 1а -узел pi), чтобы получить доступ к объекту Rj. В качестве координатора выступает узел сети с идентификатором, наиболее близким к хешированному идентификатору kj объекта Rj. При получении запроса на использование объекта Rj координатор Vj посылает ответ запросному узлу (на рис.1б - узел v,-, содержащий дубликат г/). Ответ содержит информацию о текущем владельце, работающим с объектом, и очереди ожидающих узлов. После завершения

работы с объектом узел посылает координатору сообщение ОСВОБОЖДЕНИЕ. Когда координатор Vj получает сообщение ОСВОБОЖДЕНИЕ от текущего владельца объекта, он уведомляет об этом все запросные узлы набора, и, если

только что завершивший работу с объектом узел производил модификацию объекта, сообщает им о новой версии объекта, а при необходимости тиражирует ее.

Полномочие доступа к объекту предоставляется при одновременном соблюдении следующих условий: (а) допустимо множество операций чтения в одно и то же время; (Ь) разрешается только одна операция записи в одно и то же время; (с) отсутствие (запрет) пар операций «чтение-запись» в одно и то же время.

Был проведен анализ производительности алгоритм У2К. Результаты сформулированы в виде нескольких теорем.

Теорема 2.4. Наибольшее число оверлейных операций, реализуемых в алгоритме, не превышает (т+2)С (т

- число запросных узлов в очереди, С

- число операций оверлея для каждого сообщения).

Теорема 2.5. Среднее время ответа Та в У2К алгоритме не больше 2г, где / - среднее время прохождения сообщения от одного узла к другому.

Теорема 2.6 Среднее время задержки синхронизации Т,< в У2К алгоритме составляет не более чем 2/ + г1с, где г - среднее время прохождения сообщения от одного узла к другому и гь - среднее время работы с критической секцией. Теорема 2.7. Максимальный

Рис. 2. Блок-схема алгоритма У2К

параллелизм алгоритма - п операций типа чтения или одна операция типа запись, где п - число дубликатов объекта.

Лодкорневой узел Узел (¡су) Корневой узел Ж .Очередь запросов гау) Запросный узел Д дочерние узлы

Рис. 4. Дерево узлов в ДАВИ

Основная идея алгоритма ДАВИ - построить дерево, образованное объединением только тех узлов, которые расположены на пути от запросного узла до корневого (рис. 1,4). В качестве корневого узла (КУ) дерева выбирается узел,

идентификатор которого близок или равен идентификатору

запрашиваемого объекта

(хешированному ключу). Точки ветвления дерева - это промежуточные узлы (ПУ) на пути от запросных узлов (ЗУ) до корневого.

Назовем их подкорневыми.

Любой узел, желающий получить доступ к объекту, должен соединиться с деревом. Тогда запросные узлы будут листьями дерева. Сеть может содержать множество деревьев - лес деревьев. Каждое дерево соответствует одному объекту. Подкорневые узлы поддерживают частичную очередь запросных узлов и список дочерних элементов. Дочерние элементы для узла - это ближайшие к р. узлы на пути следования запроса от запросного узла р1 к корневому. Очередь запросов содержит все запросы, которые проходят через этот узел, а в список очереди дочерних элементов включаются сведения только об их источниках сообщений (т.е. о предыдущих узлах пути). Корневой узел содержит полную очередь запросов Qj и принимает решение относительно доступа к запрашиваемому объекту. Блок-схема алгоритма ДАВИ приведена на рис. 5.

Входящими данными алгоритма являются: Ы,- идентификатор узла I; су -идентификатор клиента, владеющего объектом К/, <2]\- полная очередь запросов;

- перечень ожидающих запросов, который содержит сведения о запросах всех клиентов, упорядоченных по времени; ЬС} - список дочерних элементов, соединяемых через данный узел; 7?, - идентификатор объекта _/; - временная отметка, переменная состояния, всегда хранящаяся в £ - идентификатор источника сообщения, запросного узла р/, и - идентификатор предыдущего узла ры для промежуточного узла р1 на пути от запросного узла р, к корневому; г - идентификатор следующего узла рм для промежуточного узла р. на пути от запросного узла р, к корневому; тип сообщения; ё - идентификатор узла рй, которому посылается сообщения; М - сообщение между узлами, содержащее:{.у, и, г, й, Тип).

Любой узел, желающий получить доступ к объекту, посылает запрос только корневому узлу для того, чтобы минимизировать загрузку сети служебным трафиком и исключить нагрузку на другие дубликаты объекта. Все

узлы дерева отслеживают состояние своего родителя (не вышел ли он из строя) для удовлетворения требований децентрализации и

отказоустойчивости.

Когда любой дочерний узел обнаруживает, что его родитель выходит из строя, он сразу начинает операцию

восстановления дерева.

Дочерний узел узнает, что его родитель вышел из строя, когда от родителя перестают поступать тактовые сообщения. На всем протяжении маршрута

промежуточные узлы хранят реестры дочерних элементов и запросных узлов. Только корневой узел принимает решение относительно доступа к объекту в соответствии со своей информацией. Кроме того, только он формирует в каждом такте полную очередь запросов, сообщая ее затем всем своим дочерним, запросным и промежуточным узлам. Если объект занят, корневой узел посылает ОТВЕТ «НЕТ» на запросы всех узлов. Когда объект свободен или когда корневым узлом (КУ) получено сообщение ОСВОБОЖДЕНИЕ, корневой узел посылает ОТВЕТ «ДА» следующему узлу, запрос которого стоит первым в очереди. ОТВЕТ «ДА» содержит разрешение на использование объекта. По его получении запросный узел получает доступ к совместно используемому объекту путем входа в его КС. Другие узлы (кроме узла, который получил разрешение на доступ к объекту) просто ждут получения разрешения от корневого узла. Когда узел заканчивает работу в КС, он посылает сообщение

Рис. 5. Блок-схема алгоритма древовидного взаимного исключения

ОСВОБОЖДЕНИЕ корневому узлу, перед тем как снова запросить доступ к какому-либо объекту. Очередь запросов любого узла сети содержит все запросы, которые проходят через этот узел, а список дочерних элементов содержит сведения о предыдущих узлах пути. Корневой узел содержит полную очередь запросов Q¡ и принимает решение относительно доступа к запрашиваемому объекту.

Был проведен анализ производительности алгоритма ДАВИ. Результаты сформулированы в виде нескольких теорем.

Теорема 2.11. Наибольшее число операций в ДАВИ не превышает 4С.

Теорема 2.12. Среднее время ответа Г в ДАВИ удовлетворяет неравенству Т„ <21, где t - среднее время прохождения сообщения от одного узла к другому.

Теорема 2.13. Средняя задержка синхронизации Т,с в алгоритме ДАВИ составляет не более чем 2/ + /<,-, где t - среднее время прохождения сообщения от одного узла к другому и tu - среднее время работы в критической секции.

Показано, как алгоритмы У2К и ДАВИ могут справляться с ошибками, возникающими в сети (любой узел сети может отказать, а узлы взаимодействуют посредством сообщений, передаваемых по ненадежным каналам). Для обоих алгоритмов рассмотрены такие ошибки как неисправность узла, присутствующего в настоящий момент в КС; неисправность любого узла в сети, а также неисправность в координаторе для У2К и неисправность в корневом узле или промежуточных подкорневых узлах для ДАВИ.

Показано, что алгоритмы У2К и ДАВИ обладает следующими свойствами: упорядоченности, аутентичности, децентрализации, меньшей степенью загрузки сети служебным трафиком, масштабируемости, отказоустойчивости.

В работе была доказана корректность алгоритмов У2К и ДАВИ, т.е. соблюдение ими требований безопасности, живучести и упорядоченности (справедливости).

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

С целью исправления отмеченных недостатков были предложены два новых алгоритма. На рис 6, 7 приведены их блок-схемы.

Первый предложенный алгоритм подходит для службы рассылки/получения данных на условиях подписки и имеет название -

алгоритм тиражирования с использованием опубликования информации о местоположении всех дубликатов у координатора (ТОДК).

Рис.6. Блок-схема алгоритма ТОДК (узел р>) Второй алгоритм подходит для службы распространения данных и называется -

алгоритм тиражирования с использованием сцепленной хэш-функции (ТСХФ)(см. рис. 7).

С

D

_I_,

Опрос очереди событий |

-Соединение

.Возратить объект(5.

—Ду бл и ронать( objects, s, i Поиск/ вставка—Ц

Послать ВОЗВРАТИТЬ ОБЪЕКТ(Л/,.Л id,. id,) преемнику р, I с идентификатором Id, < /

Копировать все объекты, которые должны храниться па учле/?,./ , п массив objects_

Послать ДУБЛИРОВАТЫ objects, s, е) к р,.,

' Копировать массив objects на _массив local-objects_

Г,-Ф

Послать параллельно веем держателям дубликата сообщение ПОИСК/ВСТАВКА

Запрос поиска/вставки от

т—

Процесс поиск/вставка

Послать ОТВЕТ на поиск/вставка к т

Ответ поиска от —Восстановление—►

Послатъпараллельно всем держателям дубликата сообщение ВОССТАНОВЛЕНИЕ

_Запрос восстановления

Rj or т

Если {R, е Objects) , послать ОБНОВЛЕНИЕ к т

—"ООновле»Iие(значение,версия) из v,-

измени ть(значение)

_Разъединение

Послать ВОЗВРАТИТЬ ОБЪЕКТА,./, Id,. Id,,,) _себе {id,)_

Копирование всех своих объектов, которые должны храниться в своем потомке, в массив objects__|

Послать ДУБЛИРОВАТЬ(objects, id,.,, id,) к преемнику р

Рис.7. Блок-схема алгоритма ТСХФ (узел pi)

Основная идея алгоритма ТОДК - продолжение идеи метода лист-набора. Вместо размещения дубликатов как в лист-наборе узлов предлагается

публиковать информацию о владельцах (местоположении дубликатов) в координаторе, которым является узел с идентификатором, наиболее близким к идентификатору объекта.

Входящими данными для алгоритма ТОДК являются: Л, - объект с идентификатором М,; К, - идентификатор (ключ) объекта Я, (узел сети с идентификатором, наиболее близким к идентификатору А', объекта Л,, является координатором),- ОРл - список модификаций между двумя версиями дубликатов объекта; г, - набор узлов, содержащих дубликаты объекта /?,; .V -идентификатор источника сообщения запросного узла; с1 - идентификатор узла доставки сообщения; Тип - тип сообщения; М - сообщения между узлами, которые содержат: {«; й\ Тип }.

Идея алгоритма ТСХФ заключается в том, что для определения местоположения первого дубликата производится рекуррентным хешированием имени объекта с помощью хэш-функции .чка-!. Местоположение (ключ) для каждого дубликата вычисляется путем хеширования ключа предыдущего дубликата. Формально это означает, что если мы имеем /?/= объект "X", то хэш-функция первого дубликата будет К^=Ы$Щ"Х"), а ключи для всех остальных дубликатов будут вычисляться следующим образом: где ¡=2,...,п, п - коэффициент дублирования.

Входящими данными для алгоритма ТСХФ являются: Л, - объект с идентификатором 1(1]; Г -набор узлов, содержащих дубликаты объекта ОЦеШ(О) - двумерный (/,п)-массив, где / - это количество объектов, п -количество дубликатов; .у - идентификатор источника сообщения запросного узла; й - идентификатор узла доставки сообщения; Тип - тип сообщения; М -сообщения между узлами, которые содержат: {«; с/; О; Тип }.

Был выполнен анализ сложности алгоритмов тиражирования (существующих и предложенных) по числу сообщений (и - степень тиражирования дубликатов объекта, С - максимальное число операций оверлея для каждого сообщения, С*= 1, т.к. сообщения между узлом и его близкими узлами требуется 1 операция). Результаты приведены в табл. 1.

Таблица 1

Сравнение алгоритмов по сложностью операций_

Алгоритм Операция Набор различных хэш-функций Наборы преемников и лист-наборы ТОДК ТСХФ

Поиск / вставка <Сп <С(п+1) <с <2С

Соединение / разъединение <С <Сп <пС* +С <с*

Восстановление - - <2С <с

Обновление - - <С(п+1) <Сп

Итого (все операция) <С(п+1) <С(2п+1) <пС*+С(п+5) <С(п+3)+ С*

(без новых операций) <С(п+1) <С(2п+1) <пС'+2С <2С+ С*

Из нее видно, что производительность предлагаемых алгоритмов по числу всех операций лучше, чем у существующих алгоритмов. С другой стороны,

предложенные алгоритмы содержат новые операции "восстановление" и "обновление". Эти операции отсутствуют в существующих методах, поскольку считается, что объект не изменяемый.

Для достижения п степеней тиражирования во всех алгоритмах требуется тиражировать новый дубликат вместо каждого выходящего из системы. В табл. 2 приведено сравнение алгоритмов по количеству операции тиражирования нового дубликата. Видно, что алгоритм ТСХФ всегда сохраняет степень тиражирования, как и существующие методы, а алгоритму ТСХФ не требуется дополнительных шагов для сохранения степени тиражирования.

Таблица 2

Сравнение алгоритмов по количеству операций на тиражирование (С =1, т.к. для сообщения между узлом и его ближайшим соседом требуется 1

операция оверлея)

Набор различных хэш-функции Наборы преемников и лист-наборы ТОДК ТСХФ

<с"> <Сп <пС*+С 0

(I) Требуется инверсия хэш-функции

Четвертая глава посвящена описанию созданного алгоритмического и программного обеспечения, пригодного для имитации функционирования и исследования качества разработанных алгоритмов.

В качестве рабочей версии выбрана полностью децентрализованная пиринговая модель Pastry и её реализация FreePastry. В качестве языка программирования был выбран язык Java, так как именно он используется при реализации FreePastry.

Описывается структура программного пакета, разработанного для исследования Р2Р сетей. Приводится описание разработанных подсистем редактирования, а также подсистемы прогона модели.

Пятая глава. Описываются схемы экспериментов и приведены результаты их проведенная с указанием достоверности. Сравнение проводится по производительности алгоритмов (число сообщений, время ответа, время задержки синхронизации). На рис. 8 показан пример результатов проведенных исследований. Также были проведены исследования и сравнения алгоритмов по таким показателям, как пропускная способность, текучесть. Из сравнения результатов исследований следует, что предложенные алгоритмы имеют лучшие характеристики производительности.

Шестая глава. Описывается созданный программный пакет для реальной работы в Р2Р сетях согласно требованиям, сформулированным в первой главе, и по предложенным во второй и третей главах алгоритмам.

Созданный программный пакет был использован в компаниях, занимающихся разработкой и внедрением программных систем, - ООО «Инфо-Стрим» и ООО «Идель» на задачах исследования моделей проектируемых приложений, что подтверждается документами, приведенными в приложении к диссертации. Разработанный пакет применяется также в учебном процессе на факультете АВТ НГТУ, кафедра вычислительной техники.

X -*$~-NonE2E -"ií- Sigma E2E —«—ДАВИ Ж У2К

7.E+04 -

3,E+04.....

ж ж у--Ж

2.Е+04 ^——--* *

1,Е*04 _ „ -----О ■ ' —9

О, Г > 00

500 1000 госи 3000 40«! 5000 6000

Число N узлов

Отношение а /х

NON-E2E (1.1-2.0)% Sigma (0.7-1.7)% Е2Е (1.4-2.4)% У2Щ2.1-5.0)% ДАВИ (4.5-6.6)%

Рис.8. Сравнение предложенных и существующих алгоритмов по среднему количеству сообщений х и масштабируемости; а - оценка среднеквадратического отклонения количества сообщений

3 5000 S 4000 = 3000 Í 2000

~ íOGi г - ! НЩ а 5000

Е2£ NONE2E SIGMA ДАВИ У2К Е2Е NONE2E

Алгоритмы

Алгоритмы

Рис. 10.Влияние на нагрузку сети Рис 9. Влияние на нагрузку сети

типа алгоритмов тиражирования количества дубликатов

В заключении приведены основные результаты и выводы по диссертационной работе.

В приложении представлены копии документов об использовании результатов работы и дипломов участия конференций.

Основные выводы и результаты работы

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

1. Выполнен обзор децентрализованных файловых пиринговых сетей и дана их классификация. Выявлены требующие решения задачи, характерные для пиринговых сетей. Это задачи взаимного исключения, тиражирования и обеспечения аутентичности дубликатов объектов. Формализована системная модель класса рассматриваемых сетей.

2. Проведена систематизация и дан анализ существующих решений взаимного исключения в пиринговых сетях, рассмотрены их сильные и слабые стороны. Предложены и исследованы алгоритмы взаимного исключения «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ),

детально описаны их основы и свойства. Рассмотрена возможность обнаружения отказов в сети с помощью предложенных алгоритмов. Проведено аналитическое исследование свойств алгоритмов и показано, что разработанные алгоритмы являются более эффективными по сравнению с существующими.

3. Проведена систематизация и дан анализ существующих методов тиражирования объектов, показаны их недостатки. Разработаны алгоритмы тиражирования ТОДК и ТСХФ, детально описаны их основы, рассмотрены преимущества, показано, что они эффективнее существующих методов и свободны от их недостатков. Решена задача обеспечения аутентичности динамично получаемых дубликатов непредсказуемо изменяемых объектов в этих алгоритмах.

4. Разработан, реализован, апробирован и внедрен программный пакет для исследования предложенных алгоритмов. С его помощью проведено имитационное исследование предложенных алгоритмов, сравнение их с существующими. Показано, что предложенные алгоритмы по всем показателям превосходят известные алгоритмы.

5. Проведена апробация разработанного программного пакета для задач исследования проектируемых вычислительных сетей.

Основные публикации по теме диссертации

Публикации, входящие в Перечень ВАК:

1. Губарев В. В., Обейдат А. А. Алгоритм взаимного исключения одновременного доступа пользователей к общим ресурсам в пиринговых системах II Научный Вестник НГТУ, 2009. - № 2 (35). - С. 69-85.

2. Губарев В. В., Обейдат А. А. Алгоритм взаимного исключения в пиринговых системах//Извесгия Томского политехнического университета. -2009. - Т. 314. - № 5. - С. 32-36.

Другие публикации:

3. Обейдат А. А., Губарев В.В. Обзор алгоритмов распределенного взаимного исключения в динамических пиринговых системах // Сб. научных трудов НГТУ, Новосибирск: НГТУ, 2007. - № 2 (48). - С. 63-68.

4. Обейдат А. А., Губарев В. В. Систематизация и SWOT-анализ протоколов взаимного исключения в пиринговых системах // Сб. научных трудов НГТУ, Новосибирск: НГТУ, 2008. - № 2 (52). - С. 59-64.

5. Obeidat A. A., Gubarev V. V. Developing End-To-End Mutual Exclusion Protocol in Peer-to-Peer Systems (Разработка Сквозного Протокола Взаимного Исключения в Пиринговых Системах) // The Third International Forum on Strategie Technologies (IFOST), Novosibirsk, NSTU, 2008. - P. 282-286.

6. Obeidat A. A., Gubarev V. V., Al-yousef A. A. Decentralized and Fair Mutual Exclusion Protocol in Peer-to-Peer Systems. (Протокол Взаимного исключения с обеспечением децентрализации и упорядоченности в пиринговых системах) // The 10th International Workshop on Computer Science and Information Technologies (CSIT), Antalya, Turkey, Ufa State Aviation Technical University, 2008. — P. 11-16.

7. Губарев В.В., Гужов В.И., Джо К.Х., Обейдат A.A. Клиентские информационно-вычислительные средства как объекты изучения // Материалы НПК «Инновации в условиях развития информационно-коммуникационных технологий» (Инфо-2009): Качество - Безопасность - Диагностика .- М.: Изд-во МИЭМ.-2009 .- С. 105-107.

8. Обейдат А. А. Алгоритм узел - узел взаимного исключения в пиринговых системах// Всероссийская научная конференция студентов, аспирантов и молодых ученых "Наука. Технологии. Инновации". -Новосибирск: Изд-во НГТУ, 2008. -Ч. 1. - С. 202-223.

9. Обейдат А. А. Голосование лидера в пиринговых системах // Современные проблемы информатизации в проектировании и информационных системах: Сб. трудов. - Вып. 14. - Воронеж: «Научная книга», 2009. - С. 520-522.

10. Обейдат А. А. Управление доступом к объектам изменчивых данных в пиринговых системах // XV международной научно-техническая конференция студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА».- Москва, Издательский дом МЭИ.- 2009. - С. 314-315.

11. Обейдат А. А., Губарев В.В. Назначение лидера в пиринговых системах // Материалы III Всероссийской конференции «Винеровские чтения 2009» [Электронный ресурс]. - Иркутск: ГОУ ВПО ИрГТУ, 2009 .- № 24.

12. Obeidat A. A., Gubarev V. V. Leader election in peer-to-peer systems (Выбор лидера в пиринговых системах) // International Siberian Conference on Control and Communications (SIBCON-2009), Томск: ТГУ, 2009. - P.25-32.

13. Обейдат А. А. Свойства алгоритма «узел-координатор» взаимного исключения в динамичных пиринговых системах // II Всероссийская научно-практическая конференция «Научная инициатива иностранных студентов и аспирантов российских вузов»,- Томск: ТПУ, 2009.- С. 142-145.

14. Обейдат А. А. Обеспечение аутентичности дубликатов ресурса в пиринговых системах // II Всероссийская научно-практическая конференция «Научная инициатива иностранных студентов и аспирантов российских вузов»,-Томск. ТПУ, 2009.- С. 137-141.

15. Obeidat A.A. Replication of Mutable Objects in Peer-to-Peer Systems (Тиражирование изменяемых объектов в пиринговых системах) // The Third International Forum on Strategie Technologies (IFOST 2009), Ho Chi Minh city, Vietnam: Ho Chi Minh City University of Technology-2009 -P.171 - 175.

Отпечатано в типографии Новосибирского государственного технического университета 630092, г. Новосибирск, пр. К. Маркса,20, тел./факс (383) 346-08-57, ngtu@ngs.ru формат 60 х 84/16, объем 1.25 п.л., тираж 100 экз., заказ № 1606, подписано в печать 17.11.09г.

ВВЕДЕНИЕ.

ГЛАВА 1. КЛИЕНТСКИЕ РАСПРЕДЕЛЕННЫЕ СРЕДСТВА.

1.1. Клиентские информационно-вычислительные средства

1.2. Децентрализованные файловые пиринговые сети.

1.3. Классификация пиринговых сетей.

1.3.1. Структурированные пиринговые сети.

1.3.2. Неструктурированные пиринговые сети.

1.3.3. Сети с супер-узлами.

1.4. Проблема взаимного исключения в пиринговых сетях.

1.4.1. Вводные замечания.

1.4.2. Анализ существующих решений в распределенных системах

1.4.3. Подходы для решения проблемы взаимного исключения.

1.4.4. Показатели качества алгоритмов взаимного исключения.

1.5. Тиражирование и аутентичность и дубликатов объекта.

1.5.1. Тиражирование в структурированных пиринговых сетях.

1.5.2. Аутентичность дубликатов объекта.

1.6. Модель пиринговых сетей.

2.2. Существующие решения взаимного исключения в пиринговых сетях.44

2.2.1. Описание алгоритмов.44

2.2.2. Анализ нагрузки сети и производительности существующих решений.45

2.2.3. SWOT-анализ существующих алгоритмов.47

2.3.Предлагаемые алгоритмы.51

2.3.1. Алгоритм взаимного исключения «Узел-Координатор»(У2К) 51

2.3.1.1. Основы алгоритма.51

2.3.1.2. Описание алгоритма У2К.53

2.3.1.3. Обработка отказов в сети с помощью алгоритма У2К.56

2.3.1.4. Свойства алгоритма У2К.57

2.3.1.5. Анализ производительности алгоритма У2К.59

2.3.1.6. Корректность алгоритма У2К.61

2.3.2. Древовидной алгоритм взаимного исключения (ДАВИ).64

2.3.2.1. Вводные замечания.64

2.3.2.2. Основа алгоритма.65

2.3.2.3. Архитектура и блок-схема алгоритма ДАВИ.68

2.3.2.4. Обработка отказов в сети с помощью ДАВИ.73

2.3.2.5. Свойства алгоритма.75

2.3.2.6. Корректность ДАВИ.77

2.3.2.7. Анализ производительности ДАВИ.81

2.4. Основные результаты и выводы по главе.83

ГЛАВА 3. ТИРАЖИРОВАНИЕ И ОБЕСПЕЧЕНИЕ АУТЕНТИЧНОСТИ

ДУБЛИКАТОВ ОБЪЕКТА В ПИРИНГОВЫХ СЕТЯХ .84

3.1. Вводные замечания.84

3.2. Существующие методы тиражирования для структурированных пиринговых сетей.85

3.2.1. Различные хэш-функции.85

3.2.2. Наборы преемников и лист-наборы узлов.85

3.3. Предлагаемые алгоритмы тиражирования.91

3.3.1. Алгоритм тиражирования с использованием опубликования информации о местоположении всех дубликатов у координатора

ТОДК).91

3.3.1.1 .Опубликование дубликатов в алгоритме ТОДК.92

3.3.1.2. Операции алгоритма ТОДК.92

3.3.1.3.Преимущества алгоритма ТОДК.97

3.3.2. Алгоритм тиражирования с использованием сцепленной хэш-функции (ТСХФ).98

3.3.2.1.Основы алгоритма.98

3.3.2.2,Операции алгоритма ТСХФ.100

3.3.2.3.Преимущества алгоритма ТСХФ.104

3.3.2.4.0бработка отказов.105

3.4. Анализ сложности алгоритмов.106

3.5. Заключение и выводы по третьей главе.109

ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ

МОДЕЛЕЙ ПИРИНГОВЫХ СЕТЕЙ.111

4.1. Обоснование выбора программных средств.111

4.2. Описание Pastry.Ill

4.2.1. Схема маршрутизации Pastry.113

4.2.2. Вход и выход узла.113

4.2.3. Программный прикладной интерфейс Pastry.115

4.3. Программное обеспечение для исследования моделей пиринговых сетей.116

4.4. Средства имитации.'.117

4.4.1. Подсистема редактирования модели.119

4.4.2. Подсистема прогона модели.119

4.4.3. Подсистема обработки результатов.121

4.4.4. Реализация программного пакета для реальной работы в Р2Р сетях.122

4.5. Апробация разработанного программного пакета.123

4.7. Основные результаты и выводы по главе.123

ГЛАВА 5. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ.125

5.1. Описание подхода к моделированию.125

5.2. Результаты имитационного моделирования алгоритмов.126

5.2.1. Проверка масштабируемости и загрузки сети служебным трафиком.126

5.2.2. Сравнение показателей вида: среднее время ответа, задержка синхронизации и пропускная способность.128

5.2.3. Влияние на нагрузку сети коэффициента текучести.131

5.2.4. Влияние на нагрузку сети количества дубликатов.131

5.2.5. Влияние на нагрузку сети типа алгоритмов тиражирования .132

5.3. Основные результаты и выводы по главе.133

ГЛАВА 6. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАБОТЫ В Р2Р

СЕТЯХ.135

6.1. Программный прикладной интерфейс Pastry.135

6.2. Описание программное обеспечения.136

6.3. Средства программы.143

6.4. Интерфейс программного пакета.145

6.5. Апробация разработанного программного пакета.147

6.6. Основные результаты и выводы по главе.148

ЗАКЛЮЧЕНИЕ.149

СПИСОК ЛИТЕРАТУРЫ.151

ПРИЛОЖЕНИЕ 1. Копии документов об использовании результатов работы.163

ПРИЛОЖЕНИЕ 2. Копии дипломов участника конференции.168

ВВЕДЕНИЕ

Актуальность темы. Пиринговые сети (от англ. peer-to-peer (Р2Р) — ровня с ровней, равный с равным (Р2Р) или пользователь — пользователь (П2П)) — это среда, основанная на равноправии всех участников, в которых нет специально выделенных серверов данных или приложений, а каждый его участник - узел (peer) является как клиентом (получателем информации), так и сервером (поставщиком информации). Иными словами Р2Р-сети являются распределенной дуальной системой (средой), содержащей взаимосвязанные узлы, способные к самоорганизации в сетевую технологию с целью разделения различных ресурсов (контентов, циклов процессоров, устройств хранения, полос пропускания и т.п.), самоадаптирующихся к отказам и переменному числу узлов, поддерживая при этом приемлемый уровень связности и производительности без необходимости в посредниках или поддержки глобального центрального сервера. Они изначально ориентированны на нестабильность, переменное количество узлов в сети, устойчивость к отказам и самоадаптацию. Их дуальность (двойственность) связана с тем, что, с одной стороны, это совокупность распределенных взаимосвязанных узлов, абсолютно равноправных с точки зрения функциональности и выполняемых задач, необязательно однородных, с другой, совокупность приложений, которые используют одни и те же ресурсы (диски, циклы процессоров, контент и т.п.).

В настоящее время резко возрос интерес к пиринговым сетям (Р2Р), в которых, посредством Интернета в качестве средств (среды) обмена неизменяемых объектов, используются такие системы как Kazaa, Gnutella и BitTorrent. Недавние исследования показывают, что в течение последних лет 70% трафика Интернета связаны с деятельностью пиринговых сетей. Это объясняется тем, что использование пиринговых сетей для управления ресурсом даёт преимущества в виде уменьшения стоимости, хорошей масштабируемости и поддержки специальных сетей. Наряду с таким развитием появилась потребность в приложениях, позволяющих сотрудничать друг с другом большему количеству пользователей. До сих пор большинство решений связано с моделью «клиент-сервер», в которой сервер контролирует обновление общих данных приложения. Эта модель позволяет легко поддерживать одновременно доступ к ресурсам и аутентичность (тождественность) данных приложений, однако сервер становится единой точкой отказа системы и «узким местом», которое может препятствовать тому, чтобы приложение было доступно большому количеству пользователей. Для того, чтобы в полной мере использовать потенциал широкополосных сетей, необходимо хорошее распределение данных, являющееся ключом к обеспечению свойства масштабируемости системы. Последние исследования в области пиринговых систем были направлены на поиск решений, обеспечивающих хорошее распределение работы, выполняемой приложением, с учетом, во-первых, динамически подключающихся и отключающихся от системы узлов, во-вторых, допустимости большой динамики изменений общих ресурсов. Несмотря на то, что пиринговые системы обычно ассоциируются с размещением распределенных данных, они также могут быть использованы для объединения или крупномасштабного распространения информации.

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

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

Разработанные алгоритмы, реализованные в распределенном окружении при наличии динамизма, гарантируют, во-первых, доступ к совместно используемому и изменяемому объекту в любое заданное время только одному пользователю, во-вторых, аутентичность дубликатов объекта в условиях присоединения узлов к сети и отсоединения их от нее.

Сложность разработки таких алгоритмов связана с тем, что для поддержания взаимодействия динамично изменяемой по структуре пиринговой сети в режиме реального времени необходимо обеспечить требования ее эффективности и масштабируемости, в частности обеспечение масштабируемых коммуникаций управления процессами и изменением информации среди взаимодействующих узлов наиболее эффективным и непротиворечивым (согласованным) способом. Система должна допускать подключения или выходы из нее любого количества узлов в любые моменты времени. Это требует разработки таких алгоритмов взаимного исключения для децентрализованной пиринговой сети, которые исключат возможность одновременного доступа пользователей (узлов) с противоречивыми намерениями (запись, чтение; изменение или сохранение содержимого и т.п.) и позволят изменять масштаб сети, т.е. количество узлов и процессов в ней. Это также требует разработки и исследования алгоритмов тиражирования дубликатов объектов и обеспечения их аутентичности.

Основные вопросы проблемы взаимного исключения одновременного доступа к общим ресурсам в вычислительных системах и сетях рассматриваются в работах L. Lamport. , R. Agrawala, G. Ricart, A. Agrawala, M. Singhal, K. Raymond, M. Maekawa и др. В результате для децентрализованных вычислительных сетей предложено множество решений этой проблемы. Однако специфика пиринговых сетей не всегда позволяет эффективно использовать известные решения из-за различий в базовых моделях сетей, строения и функционирования пиринговых и других сетей. Например, ряд алгоритмов не может быть применен из-за отсутствия в пиринговых сетях централизованного сервера для отслеживания местоположения членов сети и наличия таких требований к пиринговым сетям, как отсутствие централизованного сервера индексного поиска информации для хранения списка членов и обеспечения координации между ними. Другим отличием является то, что классические децентрализованные алгоритмы используют несколько передач «от каждого к каждому» (all-to-all), что не является масштабируемым и эффективным. В результате не все известные решения могут быть эффективно и отказоустойчиво использованы в пиринговых сетях. Специальные же существующие решения для Р2Р систем обладают рядом недостатков (например, наличие единой точки отказа сети, отсутствие упорядоченности, высокая загрузка сети служебным трафиком, отсутствие обеспечения аутентичности дубликатов ресурса).

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

В связи с этим тема работы является актуальной и практически важной.

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

В соответствии с поставленной целью решаются следующие задачи исследования:

1. Выбрать класс семейства пиринговых сетей, как базовую основу для разработки и исследования алгоритмов, рассматриваемых в диссертации, и создать для него системную модель.

2. Выполнить анализ архитектурных особенностей выбранного семейства пиринговых сетей, провести систематизацию и исследование существующих методов и алгоритмов предоставления распределенного доступа к объектам в них.

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

4. Создать средства для оценки показателей качества предложенных алгоритмов и провести сравнительное исследование алгоритмов.

5. Опробовать разработанные алгоритмы доступа к дубликатам объектов.

Методы исследования. Для решения задач, поставленных в диссертации, используются методы анализа эффективности функционирования распределенных вычислительных систем, элементы SWOT-анализа, математической статистики, имитационного моделирования.

Научная новизна полученных в диссертационной работе результатов состоит в следующем:

1. Создана формализованная системная модель класса рассматриваемых сетей.

2. Систематизированы и проанализированы существующие алгоритмы взаимного исключения одновременного доступа к общим объектам и обеспечения аутентичности дубликатов объектов в динамических пиринговых сетях.

3. Разработаны новые бесконфликтные алгоритмы доступа к общим ресурсам, обеспечивающие взаимное исключение одновременного доступа к запрашиваемому объекту: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).

4. Разработаны два алгоритма тиражирования с обеспечением аутентичности (тождественности) и множественности дубликатов динамически изменяемых объектов.

5. Разработано программное обеспечение для имитационного исследования предложенных алгоритмов по основным показателям качества, проведено апробирование и исследование алгоритмов.

Практическая ценность работы заключается в том, что:

1. Использование предложенных алгоритмов и методов позволяет разработчикам при написании Р2Р-приложений не беспокоиться о поддержании низкоуровневых механизмов защиты от одновременного доступа к совместно используемым объектам и об обеспечении аутентичности их дубликатов.

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

3. Предложенные алгоритмы взаимного исключения имеют меньшую сложность. Результаты имитации алгоритмов выявили, что они обладают намного большей масштабируемостью, требуют в среднем в 3-4 раза меньшего количества служебных сообщений.

4. Созданное на основе системы FreePastry приложение позволяет обеспечить функционирование и тестирование предложенных алгоритмов.

Реализация работы. Созданный программный пакет, реализующий алгоритмы управления доступом к объектам в пиринговых сетях, был использован в компаниях, занимающихся разработкой и внедрением программных систем, - ООО «Инфо-Стрим» и ООО «ИДЕЛЬ», для решения исследования моделей проектируемых приложений. Результаты работы также использованы в учебном процессе Новосибирского государственного технического университета (НГТУ), что подтверждается соответствующими документами, копии которых приведены в приложении к диссертации.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на:

1. II Всероссийском смотре научных и творческих работ иностранных студентов и аспирантов, 28- 29 апреля, 2008 г., Томск, Россия;

2. Международной конференции «The Third International Forum on Strategic Technologies (IFOST)», 23-29 июня, 2008 г., Новосибирск, Россия;

3. Международной конференции «The 10th International Workshop on Computer Science and Information Technologies (CSIT)», 15-17 сентября, 2008г., Antalya, Turkey;

4. Российской научной конференции «Наука, Технологии, Инновации», 4-7 декабря,2008г., Новосибирск, Россия;

5. XV международной научно-технической конференции студентов и аспирантов «РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА»// 26 - 27 февраля, 2009 г., Москва, Россия;

6. Всероссийской конференции «Винеровские чтения 2009», 11-16 марта, 2009 г., Иркутск, Россия;

7. Международной конференции «International Siberian Conference on Control and Communications (SIBCON-2009)», 27-28 марта, 2009 г., Томск, Россия.

8. Седьмой всероссийской научно-практической конференции студентов, аспирантов и молодых ученых с международным участием «Молодежь и современные информационные технологии», 24-27 февраля, 2009г., ТПУ, г. Томск, Россия;

9. II Всероссийской научно-практической конференции «Научная инициатива иностранных студентов и аспирантов российских вузов», 21-22 мая, 2009 г., ТПУ, г. Томск, Россия.

10.The Forth International Forum on Strategic Technologies (IFOST), 21-23 октября , 2009 г., Ho Chi Minh city, Vietnam.

Публикации. Содержание диссертации отражено в 15 печатных работах, из которых 2 статьи опубликованы в изданиях, рекомендованных ВАК РФ.

На защиту выносятся следующие результаты:

1. Результаты исследования существующих решений.

2. Эффективные алгоритмы бесконфликтного доступа к запрашиваемому объекту в децентрализованных пиринговых системах: алгоритм «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ).

3. Алгоритмы тиражирования динамично получаемых дубликатов непредсказуемо изменяемых объектов с обеспечением их аутентичности

4. Программное обеспечение для проведения имитационного исследования предложенных алгоритмов по выбранным показателям качества и результаты их исследования.

Структура и содержание работы

Диссертация состоит из введения, шести глав, заключения, списка литературы, включающего 105 наименований, из которых 88 иностранных, и двух приложений. Текст диссертации изложен на 171 странице, включает 36 рисунков и 8 таблиц. В приложении содержатся копии документов об использовании результатов работы и дипломов за участие в научно-технических конференциях.

5.3. Основные результаты и выводы по главе

Методами имитационного моделирования проведены исследования предложенных алгоритмов и сравнения их с существующими. Проведены следующие исследования.

ДАВИ У2К Е2Е NONE2E SIGMA

Алгоритмы

1. Проверка масштабируемости и загрузки сети служебным трафиком.

2. Сравнение показателей вида: среднее время ответа, задержки синхронизации и пропускная способность.

3. Влияние показателя текучести.

4. Влияние количества дубликатов на нагрузку сети.

5. Влияние типа алгоритмов тиражирования на нагрузку сети. Показано, что предложенные алгоритмы по всем показателям превосходят известные алгоритмы.

ГЛАВА 6. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАБОТЫ В Р2Р СЕТЯХ

В данной главе описывается созданный программный пакет для реальной работы в Р2Р сетях согласно требованиям, сформулированным в первой главе, и по предложенным алгоритмам во второй и третей главах а|е ф ф $

4 ,7 ,13 ,105 ]. Программный пакет называется РМАМО-Р2Р (Program of Management the Access to Mutable Objects in Peer-to-Peer Networks — Программное обеспечение для управления доступом к изменяемым объектам в пиринговых сетях). Программный пакет РМАМО-Р2Р гарантирует одновременное выполнение противоречивых запросов на работу с одним и тем же объектом и обеспечение аутентичности и множественности его дубликатов. Под объектом мы будем понимать реальный файл или базу данных. В нем были реализованы алгоритмы, показавшие лучшие результаты после практических исследований, описанных в главе 5. 6.1. Программный прикладной интерфейс Pastry

В качестве рабочей версии для реализации пакета РМАМО-Р2Р выбрана полностью децентрализованная пиринговая модель Pastry и её реализация FreePastry. Обоснование выбора реализации аналогично изложенному в главе 4.

Далее кратко описывается программный прикладной интерфейс (API -Application Programming Interface) Pastry. Для ясности представленный API немного упрощен. Кроме того API был применен для написания приложений без привязки к определенному протоколу, что обеспечивает переносимость приложений из Pastry в Chord, CAN, Tapestry и др.

Pastry реализует следующие операции:

• Id = pastryln\t(Credentials, Application) приводит к присоединению нового узла к существующей сети Pastry (или создает новую), инициализации всех значимых состояний и возврату идентификатора Id нового узла.

Специализированные параметры Credentials содержат информацию для аутентификации нового узла. Аргумент Application является идентификатором объекта приложения, который обеспечивает вызов процедур на узле Pastry при возникновении определенных событий, например, при получении сообщения.

• route(M, key) приводит к отправке сообщения М узлу с идентификатором Id, численно наиболее близким к идентификатору (ключу) key среди всех активных узлов Pastry.

ЗАКЛЮЧЕНИЕ

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

1. Выполнен обзор децентрализованных файловых пиринговых сетей и дана их классификация. Выявлены требующие решения задачи, характерные для пиринговых сетей. Это задачи взаимного исключения, тиражирования и обеспечения аутентичности дубликатов объектов. Формализована системная модель класса рассматриваемых сетей.

2. Проведена систематизация и дан анализ существующих решений взаимного исключения в пиринговых сетях, рассмотрены их сильные и слабые стороны. Предложены и исследованы алгоритмы взаимного исключения «узел-координатор» (У2К) и древовидный алгоритм взаимного исключения (ДАВИ), детально описаны их основы и свойства. Рассмотрена возможность обнаружения отказов в сети и устранения их последствий с помощью предложенных алгоритмах. Проведено аналитическое исследование свойств алгоритмов и показано, что разработанные алгоритмы являются более эффективными по сравнению с существующими.

3. Проведена систематизация и дан анализ существующих методов тиражирования объектов, показаны их недостатки. Разработаны алгоритмы тиражирования ТОДК и ТСХФ, детально описаны их основы, рассмотрены преимущества, показано, что они эффективнее существующих методов и свободны от их недостатков. Решена задача обеспечения аутентичности динамично получаемых дубликатов непредсказуемо изменяемых объектов в этих алгоритмах.

4. Разработан, реализован, апробирован и внедрен программный пакет для исследования предложенных алгоритмов. С его помощью проведено имитационное исследование предложенных алгоритмов, сравнение их с существующими. Показано, что предложенные алгоритмы по всем показателям превосходят известные алгоритмы.

5. Проведена апробация разработанного программного пакета на задачах исследования проектируемых вычислительных сетей.

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

151

1. Введение в пиринговые сети: Bittoreent — (MetalMind I I http: // www. Metalmind.ru / wedenie v piringovyie seti bittorrent.html).

2. Velazquez М. G. A Survey of Distributed Mutual Exclusion Algorithms/ M. G. Velazquez //Colorado State University, Technical Report CS.93-116.-1993.

3. Открытые системы 2004 .- № 12.

4. Сухорослов O.B. Пиринговые системы: концепции, архитектура и направления исследований / О.В. Сухорослов // Проблемы вычисленийв распределенной среде: прикладные задачи. Труды ИСА РАН .- М.: РОХОС.-2004.-С. 7-43.

5. Таненбаум Э. Распределенные системы. Принципы и парадигмы / Э. Таненбаум, М. Ван Стен// СПб.: Питер .- 2003 .- 877 с.

6. Agrawal D. Exploiting logical structures in replicated databases/ D.Agrawal, A. EL ABBADI // Information Processing Letters, Vol. 33, №. 5 .- January 1990 .-P. 255-260.

7. Ahamad M. Replicated data management in distributed systems/M. Ahamad, M. Ammar, S. Cheung // IEEE Computer Society .- Los Alamitos, CA .— January 1994 .-P.572-591.

8. Androutsellis-Theotokis S. A survey of peer-to-peer content distribution technologies / S. Androutsellis-Theotokis, D. Spinellis// A CM Computing Surveys, 36(4), December 2004 P.335-371.

9. Bamboo, http: // bamboo-dht.org 2006.

10. Bernstein P. A. A proof technique for concurrency control and recovery algorithms for replicated databases / P. A. Bernstein, N. Goodman// Distributed Computing, 2(1) January 1987 .-P.32-44.

11. Carvalho O. On mutual exclusion in computer networks / O. Carvalho, G. Roucairol // Technical Correspondence," Communications of the ACM", Vol. 26. -№. 2 .-Feb. 1983 .-P. 146-147.

12. Castro M. Scribe: A large-scale and decentralized application level multicast infrastructure / M. Castro, P. Druschel, A. Kermarrec // IEEE J. Sel. Areas Commun .-Vol.20. -№. 8 Oct. 2002 .-P. 1489- 1499.

13. Cheung S. Y. The Grid protocol: A high performance scheme for maintaining replicated data / S. Y. Cheung , M. H. Ammar, and M. Ahamad // IEEE

14. Transactions on Knowledge and Data Engineering, 4(6) December 1992 .— P.582-592

15. Clarke I. Freenet. A distributed anonymous information storage and retrieval system / I. Clarke, O. Sandberg, B. Wiley, T. Hong // In Proc. of the ICSI Workshop on Design Issues in Anonymity and Unobservability.- Berkeley, CA.- July 2000 P. 311-320.

16. Crespo A. Routing indices for peer-to-peer systems / A. Crespo, H. Garcia-Molina // In Proc. of the IEEE Int. Conf. on Distributed Computing Systems (ICDCS) .- Vienna, Austria .- July 2002 .- P. 23-33.

17. Dijkstra E.W. Solution of a Problem in Concurrent Programming Control, Communications/ E.W. Dijkstra // ACM 8.-9 Sept. 1965 .- P.569.

18. Dingledine R.The FreeHaven project: distributed anonymous storage service/ R. Dingledine, M. Freedman, D. Molnar // In Proc. of the Workshop on Design Issues in Anonymity and Unobservability .- Berkeley, California — July 2000 .-P. 67-95.

19. Direct connect.- 2007 .- (http://www.dconnect.net).

20. FIPS 180-1. Secure hash standard // Tech. Rep. Publication 180-1, Federal Information Processing Standard (FIPS), National Institute of Standards and Technology, US Department of Commerce, Washington D.C .- April 1995.

21. Foster I. The Grid: Blueprint for a new computing infrastructure / I. Foster, C. Kesselman // Morgan Kaufman .- 1998 677 p.

22. Harrell F. Survey of Locating & Routing in Peer-to-Peer Systems / F. Harrell, H. Yuanfang , G. Wang, H. Xia // Department of Computer Science and Engineering .- 2001 .-(http://www.cse.ucsd.edu/classes/fa01/cse221/projects/groupl5.pdf).

23. Freepastry .- 2006 —URL: http://freepastry.rice.edu/

24. Ganesan P. Canon in G major: Designing DHTS with hierarchical structure / P. Ganesan, P. K. Gummadi, H. Garcia-Molina // 24th international conference on distributed computing systems (ICDCS 2004).-23-26 March .- 2004.- Tokyo, Japan.-P. 263-272.

25. Coulours G. Distributed systems / G. Coulours, J. Dollimore ,T. Kindberg // 4th edition, Addison-wesley .- 2005 .- 927p.

26. Gifford D. K. Weighted voting for replicated data / D. K. Gifford // In Proc. of the 7th Symposium on Operating Systems Principles .- Pacific Grove, CA .-December 1979 .-P. 150-162.

27. Файлообмен: Freenet и Gnutella .- 1997 . .— (http ://www.computerra.ru/ softerra/net/32144/).

28. Gnutella .— 2000 .— ( http://www.gnutelliums.com).

29. Helary J. A distributed algorithm for mutual exclusion in an arbitrary network/ J.Helary, N. Plouzeau , M. Raynal // Computer Journal, Vol. 31, №. 4.- 1988 .-P. 289-295.

30. Jovanovic M. Scalability issues in large peer-to-peer networks: a case study of Gnutella. Technical report/ M. Jovanovic, F. Annexstein, K. Berman // ECECS Department, University of Cincinnati, Cincinnati, Ohio, January 2001.

31. JXTA Community .- 2008 .- ( http://www.jxta.org/).

32. Kalogeraki V. A local search mechanism for peer-to-peer networks / V. Kalogeraki, D. Gunopoulos, D. Zeinalipour-Yazti // In Proc. of the ACM Int. Conf. on Information and Knowledge Management (CIKM) .- McLean, Virginia .-November 2002 .-P. 300-307.

33. Kazaa .- 2006 .- (http://www.kazaa.com/).

34. Kumar A. Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data / A. Kumar // IEEE Transactions on Computers.- vol.40. n.9- 1991.-P. 996-1004.

35. Lamport L. Time, clocks and the ordering of events in a distributed system / L. Lamport // Communications of the ACM .- Vol. 21 .- 1978 .- P. 558-565.

36. LvQ. Search and replication in unstructured peer-to-peer networks/ LvQ. , CaoP., CohenE. , K. Li , S. Shenker // In Proc. of the ACM Int. Conf. on Supercom-puting (ICS) .- ACM New York, NY, USA.- June 2002 .- P.84-95.

37. Maekawa M. Operating Systems, Advanced Concepts/ M. Maekawa, A.E. Oldehoeft, R.R. Oldehoeft//Benjamin-Cummings .— 1987.

38. Maymounkov P. Kademlia: A peer-to-peer information system based on the xor metric / P. Maymounkov and D. Mazi'eres // Proceedings of the IPTPS, Cambridge, MA, USA .- February 2002 .- P.53-65.

39. Mishra. S. Fault-tolerant mutual exclusion algorithms / S. Mishra., P. Srimani // Journal of Systems Software, Vol. 11. №. 2 .- Feb. 1990 .- P. 111-129.

40. Mizuno M. A Token based distributed mutual exclusion algorithm based on Quorum Agreements / M. Mizuno, M.L. Neilsen, R. Rao // 11th Intl. Conference on Distributed Computing Systems .- 20-24 may 1991 -P.361

41. Moosa Muhammad. Efficient Mutual Exclusion in Peer-To-Peer Systems/ Moosa Muhammad // University of Illinois at Urbana-Champaign .- 2005 .— P. 296-299.

42. Morpheus home page .— 1999 .- (www.moipheussoftware.net).

43. Mosberger D. Memory consistency models / D. Mosberger // Tech. rep., University of Arizona .— Nov., 1993.

44. Muhammad M. Efficient mutual exclusion in peer-to-peer systems. / M. Muhammad, A. S. Cheema // 6th IEEE ACM International Conference on Grid Computing 2005 .- P. 296-299.

45. Naimi M. How to detect a failure and regenerate the token in the log(n) distributed algorithm for mutual exclusion / M. Naimi, M. Trehel // Proc. of the Second Int. Workshop on Distributed Algorithms, Lecture Notes in CS .1987 .-P. 155-166.

46. Napster home page .- 2003 .- (http://www.napster.com).

47. Neilsen M.L. A DAG-based algorithm for distributed mutual exclusion / M. L. Neilsen, M. Mizuno// 11th Intl. Conference on Distributed Computing Systems .- 20 24, May ,1991 .- P. 354 - 360 (http://www.scipub.org/fiilltext/jcs/jcs55398-404.pdf).

48. Nejdl W. Design issues and challenges for RDF- and schema-based peer-to- peer systems / W. Nejdl, W. Siberski, M. Sintek // ACM SIGMOD Record, 32(3) September 2003 .-P.41-46.

49. Nejdl W. Edutella: a P2P networking infrastructure based on RDF/ W. Nejdl, B.Wolf, C. Qu , S. Decker, M. Sintek, A. Naeve , M. Nilsson , M. Palmer ,T. Risch // In Proc. of the Int. World Wide Web Conference (WWW) Honolulu,

50. Hawaii .-May 2002 .-P. 604-615.

51. Overnet Web site : eDonkey2000 Overnet .- 2000 .-(http://www.overnet.com/).

52. Malkhi D. Viceroy: a scalable and dynamic emulation of the butterfly / D. Malkhi, M. Naor , D. Ratajczak // Proc. 21st Ann. ACM Symp. Principlesof Distributed Computing (PODC) .- July 2002 P. 183-192.

53. Michael N. H. SkipNet: A Scalable Overlay Network with Practical Locality Properties / N. H. Michael, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman // .— 2003 .- (http://research.microsoft.eom/users/alecw//usits-2).

54. Raymond K. A distributed algorithm for multiple entries to a critical section / K. Raymond // Information Processing Letters, №. 30, Feb. 1989, pp. 189193.

55. Raymond K. A tree-based algorithm for distributed Mutual Exclusion / K. Raymond // ACM Transactions on Computer Systems, Vol. 7, №. 1 .— Feb. 1989 .-P. 61-77.

56. Raynal M. A simple taxonomy for distributed mutual exclusion algorithms / M. Raynal // Operating Systems Review, Vol. 25, №. 2, Apr. 1991, P. 47-49.

57. Raynal M. Prime numbers as a tool to design distributed algorithms// M. Raynal / Information Processing Letters, Vol. 33. №. 1 .- Oct. 1989 P. 53-58.

58. Ricart G. An optimal algorithm for mutual exclusion in computer networks / G. Ricart, A. Agrawala // Communications of the ACM, Vol. 24, №. 1, Jan. 1981 .-P. 9-17.

59. Ricart G. Author response to 'on mutual exclusion in computer networks' by Carvalho and Roucairol / G. Ricart, A. K. Agrawala // Communications of the ACM, Vol. 26, №. 2 .-Feb. 1983 .-P.147 148.

60. Saito Y. Optimistic replication/ Y. Saito, M. Shapiro// ACM Computing Surveys, 37 (1) .- March 2005 .- P.42-81 (http://citeseer.ist.psu.edu/saito03optimistic.html).

61. Sanders B. The information structure of distributed mutual exclusion algorithms / B. Sanders // ACM Transactions on Computer Systems, Vol. 5, №. 3 .-Aug. 1987,.— P.284-299.

62. Shiding L. A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems / L. Shiding , Qiao Lian, Ming Chen, Zheng Zhang // 3rd International Workshop on Peer-to-Peer Systems (IPTPS'04) .- San Diego, CA, USA .- Feb.2004 P. 1-10.

63. Silberschatz A. and Peterson, J.L. Operating System Concepts / A. Silberschatz, J.L. Peterson//Addison-Wesley .- Alternate edition .- 1988.

64. Singhal M. A dynamic information-structure mutual exclusion algorithm for distributed systems / M. Singhal // IEEE Transactions on Parallel and Distributed Systems, Vol. 3, №. 1 .-Jan. 1992 -P. 121-125.

65. Singhal M. A heuristically-aided algorithm for mutual exclusion in distributed systems / M. Singhal //IEEE Transactions on Computers, Vol. 38, №. 5 .-may 1989 .-P.651-662.

66. Srimani P. Another distributed algorithm for multiple entries to a critical section / P. Srimani, R. Reddy // Information Processing Letters .- Vol. 41, №. 1 .-Jan. 1992 .-P.51-57.

67. Stockinger Heinz. Defining the Grid: A Snapshot on the Current View / http: // www.gridclub .- 26.06 2006.

68. Stoica I. Chord: A scalable Peer- To-Peer lookup service for internet applications /1. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan //

69. Proceedings of the ACM SIGCOMM 2001 Conference. ACM Press-New York. 2001 .- P. 149-160.

70. Suzuki I. and Kasami T. A distributed mutual exclusion algorithm /1. Suzuki, T. Kasami // ACM Transactions on Computer Systems, Vol. 3. — №. 4 — Nov. 1985 .-P. 344-349.

71. The Gnutella protocol specification .— (http://dss.clip2.com/GnutellaProtocol04.pdf. 2000).

72. Thomas R. H. A majority consensus approach to concurrency control for multiple copy databases / R. H. Thomas // ACM Transactions on Database Systems, Vol. 4. №. 2 .- June 1979 .- P. 180-209.

73. Vidal M. Survey of data replication in P2P systems / M. Vidal, E. Pacitti, P. Valduriez 2006 .- (http://hal.inria.fr/inria-00122282/en).

74. Waldman M. Publius: a robust, tamper-evident, censorship-resistant, web publishing system / M. Waldman, R. AD, C. LF // In Proc. of the USENIX Security Symposium -Denver, Colorado August2000 -P. 59-72.

75. Mitchell B.WinMX .- 1999 (http://compnetworking.about.eom/b/2005/09/27/winmx-p2p-network-meetS" its-demise-almost.htm).

76. Yang B. Improving search in peer-to-peer networks / B. Yang, H. Garcia-Molina // In Proc. of the IEEE Int. Conf. on Distributed Computing Systems (ICDCS) Vienna, Austria.- July 2002 .- P. 5-14.

77. Zhao B. A Global-scale Overlay for Rapid Service Deployment/ B. Y. Zhao, L. Huang, S. C. Rhea, J. Stribling, A. D. Joseph, and J. D. Kubiatowicz// IEEE Journal on Selected Areas in communications (JSAC) .- 22(1),January 2004 .-P. 41-53.

78. Zhao B.Y. Tapestry: An infrastructure for fault-tolerant wide-area location and routing / B.Y Zhao, J. Kubiatowicz, A. D. Joseph // Technical Report UCB/CSD-01-1141, University of California.-Berkeley, California, USA.-2001.