Простой алгоритм.

[muzyka_sfer]

.
На сетке, портрет которой возник в 3х предыдущих заметках, можно организовать связь простейшими способами.
Вот пример самого простого алгоритма (который можно развивать дальше или заменять на более сложные для создания P2P (F2F, точнее) если работает система распределенных блогов

Comments

Та самая "глава". Это про Bouillon 2, см http://oc-co.org

[no_gritzko_here]

Бульон 2.

Почему это будет работать?

Вкратце: потому что мир тесен.
Принцип работы Бульона можно продемонстрировать кратким примером. Вспомним гипотезу six degrees of separation, которая предполагает, что любые два человека на Земле связаны цепочкой знакомств не длиннее шести шагов. Примем и другое, гораздо более очевидное предположение: Бульон позволяет без особого напряжения получать мнения от друзей друзей (два шага). В таком случае, для доставки кусочка от произвольного человека-автора к другому совершенно произвольному человеку-читателю может быть достаточно двух (6/2-1) промежуточных подтверждений. Два человека должны прочитать кусочек и нажать /!\. Понятно, что этот пример рассматривает в некотором смысле идеальный случай; в действительности есть множество других факторов. Например, плохо то, что участники на кратчайшем пути могут быть не заинтересованы в данной теме. Но с другой стороны, хорошо то, что люди с одинаковыми интересами с большей вероятностью имеют общих знакомых. И так далее, соображений тут много, а этот пример имеет целью лишь проиллюстрировать основной принцип работы Bouillon.

...

Трюк: степенной разлом

Помимо ответа на запрос, мнения о странице могут рассылаться и просто так, в порядке рекламы (как анонсы). Замечу: в этой части речь идёт только о коренных мнениях. Рассмотрим простейшую модель социального графа из N участников - случайный граф. Если предположить, что ответ находится у одного произвольного участника, а некоторый другой участник распространяет запросы на M узлов, то вероятность успеха, т.е. попадания запроса к имеющему ответ, следует оценить, как O(M/N). Если же имеющий ответ рекламирует своё мнение на P узлов, то вероятность встречи запроса и анонса имеет критический порядок: M/N*P/N*N~1 => MP~N. Если учесть, что затраты на передачу и хранение анонсов и запросов оцениваются в O(M+N), то мы получаем сублинейную сложность.
Безусловно, топология социальных графов имеет свои свойства, не рассмотренные в данной примитивной модели. В первую очередь это роль хабов. Тем не менее, это рассуждение характеризует порядок изменений в эффективности поиска, производимых одновременным применением анонсов и запросов. Этот эффект я назову степенным разломом, поскольку logM+logP~logN, т.е. N "разламывается" в геометрической пропорции на две части.
Правильное использование степенного разлома позволяет улучшить достижимость страниц в сети Бульон.
С точки зрения теории scale-free графов, для повышения эффективности сети хабы (узлы высокой степени) должны иметь существенно больше как пропускной способности (для запросов) так и дискового пространства (для хранения анонсов).