Диссертация (1137145), страница 6
Текст из файла (страница 6)
Чтобы гарантировать подлинность записей, они снабжаютсяцифровой подписью обладателя.Однако, несмотря на многие преимущества систем основанных на DHTпо сравнению с традиционной DNS, они так и не заменили DNS.1.2Алгоритмыраспределенныхсистемхранениясвозможностью поиска ближайшего соседа в векторныхпространствахОписание построений P2P сетей в первой части данной главыпроисходило, через описание структуры и принципов построения таблицмаршрутизации. С этого момента и более будет использоватьсятерминология графов.
Будем считать, что узлам сети соответствуютмножество вершин графа , . Наличие записи об узле в таблицемаршрутизации узла , соответствует существованию ребра (, ) в графе т.е. , ∈ .32Пространство ключей будем обозначать (domain). Предполагается что,логическая сеть строится на конечном множестве ⊆ . Чтобы иметьвозможность эффективно организовать поиск в пространстве ключей, надним вводят функцию расстояния : × → !1.2.1 Модель навигационного тесного мира КлайнбергаГрафы, чья топология позволяет децентрализованному алгоритмуобнаружить искомую вершину за полилогарифмическое число шагов отобщего числа вершин, в литературе называют графами с навигационнымисвойствами тесного мира или, просто, навигационными тесными мирами1.Свидетельство о существовании в реальном мире сетей обладающихсвойством навигационного тесного мира впервые было получено Трверсоми Мильграмом в эксперименте проведенном 1967 году [J.
Travers, S.Milgram]. Эксперимент Мильграма показал, что сеть знакомств способнаэффективно направлять информацию используя только локальное знание оструктуре сети.Ранние модели [P. Erdesh, A. Rényi, 1960], [B. Bollobás, O. M. Riordan,2003], [R. Albert, A.L. Barabási, 2002], [D. J. Watts, S.H. Strogatz, 1998]позволяют строить графы имеющие малый диаметром, однако ихструктура не позволяет децентрализованному алгоритму быстрее, чем заполиномиальное время прийти в искомую вершину [J. Klainberg, 2000].Позднеепоявилисьмоделистроящиеструктурысэффективнойнавигацией. Так в 2001 году Джоном Клайнбергом был предложена модельслучайного графа, чья структура поддерживает эффективный поиск т.е.1В литературе часто упускают слово «навигация» и используют слово сочетание «со свойствамитесного мира», что создаёт путаницу т.к.
«термин тесный мир» имеет более значение – граф в которомсредняя длина кратчайшего пути между любыми двумя вершинами пропорциональна логарифму отчисла общего вершин. Однако существование короткого пути, вообще, не достаточно длянавигационных свойств т.к.
этот короткий путь ещё надо найти, используя только локальнуюинформацию)33позволяетдецентрализованному«жадному»алгоритмуобнаружитьискомую вершину за полилогарифмическое время.Модельформулируетсяследующимобразом.двумерная целочисленная решётка размером ×,Рассматривается, : ∈ 1,2, … , , ∈1,2, … , .
В качестве функции расстояния между узлами , и , используется расстояние «Манхетана» , , , = − + | − |Модель имеет три параметра: ∈ ≥ 1, ∈ ≥ 0, ∈ ≥ 0. Каждыйузел соединяется рёбрами со всеми узами на расстоянии не больше (локальные связи). Так же для каждого узла строится дальних связейиспользуя независимые испытания. Так i-ое ориентированное ребро из в строится с вероятностью−r( )P((u,v) ∈ E) =∑ d (u,v )d u,v−rvВ модели Клайнберга, цель поиска - начиная с произвольной вершиныобнаружить вершину с заданными координатами.
Предполагается, чтопроисходит посредством передачи поискового сообщения содержащегозначение координат искомой вершины, от одной вершине к другой.Решение о том, какому следующему узлу передать поисковое сообщение,принимается на основании «жадной» стратегии.Узел получившийсообщение о поиске вершины , передаёт поисковое сообщение узлу ,которыйизегососедейрасполагаетсяближевсегок т.е.v = arg min (d(x,t) : (u, x) ∈ E) .xЭта модель имеет интуитивную «географическую» интерпретацию.Каждый индивид знает своих непосредственных соседей, а так же имеетдальние знакомства.Основной результат, полученный Клайнбергом для этой модели,заключен в следующей теореме.34Теорема (Клайнбер 2000)Для параметров = 2 и = = 1 ∃ независящая от , такое чтоматематическое ожидание число шагов алгоритма поиска GreedyWalk непревосходит (log )!1.2.2 VoroNetVoroNet–этосовокупностьалгоритмовдляобъединенияводноранговую сеть (peer-to-peer) множества объектов идентифицируемыхточками евклидового пространства.
То есть в качестве множества выступают точки плоскости, точнее, точки квадрата 0; 1 × 0; 1 . Вкачестве функции расстояния ∙,∙ используются расстояние Евклида.В основе VoroNet лежит главным образом две идеи. Первая – дляобеспечения корректности поиска система строит и поддерживает графаДелоне, который однозначно строится на основе диаграммы Вороного(Рисунок 10). Вторая идея – строить дальние связи (длинные рёбра) поаналогии с моделью Клайнбера.В VoroNet каждый объект ∈ является узлом сети и поддерживаетчетыре множества. Первое множество – множество соседей Вороного{ } т.е., множество объектов, чьи ассоциированные области Вороногоимеют общую границу с областью Вороного точки (в совокупностимножества соседей Вороного всех узлов составляют граф Делоне).
Второемножество 1 – множество дальних соседей ! (). Множество дальнихсоседей формируется аналогично модели Клайнберга. Также каждыйобъект множество ближайших соседей = { ! ∈ : (, ′) ≤!"# }, где !"# число зависящее от максимального количества объектов всети.
В дополнении, каждый объект хранит множество ! () множество обратных дальних связей;1В оригинальной статье это множество включает в себя только один элемент35Рис. 10. Пример окрестности у объекта в системе VoroNet1.2.2.1 Алгоритм добавленияПроцесс добавление нового объекта в VoroNet происходит в четыреэтапа.1. Начиная от произвольного объекта , который уже находится в сети,производится поиск объекта ′, чья ассоциированная область Вороногосодержит т.е. ∈ (′).2. Объект ′ является ответственным за вычисление новой областиВороного () объекта , вычисление его окрестности и множествасоседей Вороного { } . Кроме того ′ модифицирует собственныемножества ( ! ) , ′и { ′ } иопределяетдолжналиответственность за поддержание обратной дальней связи ! (′) бытьпередана .3.
Узел вычисляет множество ближайших соседей 4. выбираетслучайнуюточкуизединичногоквадратасраспределением обратно пропорциональным квадрату расстояния согласно36модели Клайнберга и отыскивает ближайший объект к этой точке, темсамым формируя дальнюю связь ! ().1.2.2.2 Удаление элементовВ оригинальной статье процесс удаления элемента описываетсяпредполагая, что «удаляемый» элемент покидает сеть не внезапно. Чтобысохранить структура графа Делоне, который обеспечивает корректностьпоиска жадным алгоритмом, удаляемый элемент( ! ) , ′множестваи { ′ } модифицируетдля каждого своего соседаВороного ′.
Так же для каждого элемента из множества ! (), корректирует множество длинных связей ! () используя множествоближайших соседей .1.2.2.3 Сложность поиска и необходимый объём памятиСложность поиска складывается из размера окрестностей элементоввходящих в путь проделанный алгоритмом. Теоретически размер областиВороногоограничентолькообщимчисломточек .Однакомногочисленные эксперименты показывают, что для часто встречаемыхраспределений случайной величины, включая равномерное и сильноразряженноераспределение,числососедейВороногосильносконцентрировано около значения 6. Это даёт основание говорить, о том,что размер окрестности есть функция (1).Экспериментальныеданныетакжеподтверждаютгипотезуополилогарифмической зависимости средней длины пути проходимого«жадным» алгоритмом во время процесса поиска. Таким образом, общаявычислительная сложность поиска тоже является полилогарифмической,точнее, (log ()! ).
Стоит отметить, что в оригинально статье авторамиприводятся экспериментальные данные только для равномерного иразряженного распределения (Sparse Distribution) c тремя различнымизначениями параметрами альфа ( = 1; = 2; = 5;), однако из этого не37следует, что данная полилогарифмическая зависимость сохранится вдругихраспределениях,например,всильнонеравномерныераспределениях (англ. highly skewed distributions).1.2.3 RayNet1.2.3.1 Общее описаниеRayNet – более поздняя работа[Beaumont O., и др., 2007] тех жеавторов, что и VoroNet. RayNet – может рассматриваться в качествеобобщения VoroNet.
Аналогично VoroNet логическая сеть строится науровне данных, но в отличии от VoroNet, RayNet позволяет эффективнопроизводитьпоискближайшегососедав -мерномЕвклидовомпространстве. То есть в качестве объектов – ключей в RayNet выступаютточки -мерного Евклидового пространства. Главной особенностью RayNetявляется то, что на каждом объекте поддерживается не точное множествососедейобластиВороного,амножествососедейеёнекоторойаппроксимации.
Для нахождения некоторой “хорошей” аппроксимацииобласти Вороного в RayNet используется алгоритм основанный на методеМонтекарло.Для построения и поддержания сети логических связей RayNetиспользует подход основанный на идеи распространения слухов (gossipbased approach). Через определённый интервал времени, называемыйциклом, периодически узлы сети обмениваются информацией друг сдругом. На каждом цикле узел выбирает из множества известных емуузлов . узел ! .
Среди множества . ∪ ! . используя нижеприведённый алгоритм выбирает элементов, которые являютсянаилучшей аппроксимации множества соседей Вороного . С этой целью перебирает все возможные сочетания из элементов среди множества. ∪ ! . и вычисляет объём области Вороного элемента вразбиении ∪ . Множество при котором объём области Вороного38минимален, выбирается в качестве нового множества . (см. рисунок11. )1.2.3.2 Вычисление объёма области Вороного c помощью методаМонте-КарлоРис.
11. Вычисление объёма области Вороного c помощью метода Монтекарло.Создаётся множество лучей1 с началом в точке . Направление лучейвыбираетсяслучайноравномерно.Дляэтогоиспользуетсяметодописанный в [Knuth D. E., 1981], позволяющий выбрать случайно точки нагипер-сфере единичного радиуса с равномерным распределением. Далеена каждом луче ищется точка пересечения лучом области Вороного ().Это пересечение происходит в точке !"# на границе с областью Вороногообъекта ! .
Для нахождение точки !"# используется тот факт, что !"#равноудалена от точки и точки ! т.е. = !"# , = !"# , ! и приэтом для ! это расстояние минимально среди всех остальных объектовмножества . Каждый луч ассоциируется с шаром радиуса ! , с объёмомвычисляемым как ×(! )! , где – объём единичного шара впространстве размерности . Аппроксимированный объём областиВороного для конфигурации , вычисляется как среднее значения объёмовшаров радиуса !∈! . Усреднённый объём сходится к объёму области1Лучи в переводе на английский - rays. От этого и берёт свое название RayNet39Вороного при числе лучей стремящимся к бесконечности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
