Интернет без серверов (Или все наоборот)

[Ism]

Когда сделаете такую с качеством результатов, сравнимым с гуглом, яндексом и бингом, дайте знать.

Уже есть, рутрекер называется На самом деле все решаемо, это будет распределенная структурированная база данных, одна проблема, время отклика, но гугл както решил ее

[watashiwa_daredeska]

Уже есть, рутрекер называется

А, ну-ну. Если это всё, что Вам надо искать, то велком.

[watashiwa_daredeska]

это будет распределенная структурированная база данных, одна проблема, время отклика,

Всего одна проблема? Как просто-то. А я и не знал.

гугл както решил ее

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

[Crazy]

Нет , с точки зрения строения мозга интернет сейчас страдает тяжелой шизофренией (раздвоением личности). Гугл, микрософт, apple и другие пытаются обособить узлы в свою экостстему, что только разрушает интернет. А всегото надо сделать распределенную поисковую систему по принципу торрентов , но , правда это означает гибель нынешних поисковых систем , они будут биться до последнего

Любая сеть передачи данных или вычислительная сеть это распределенная система.
Огромные дата центры гугла так же являются распределенными системами.

[drBatty]

Значит она лежит на другом сервере. Что уже противоречит теме Интернет без серверов

формально - да. Однако из поста ясно, что ТС имел ввиду сеть не без серверов вообще, а без всяких googl'ов, фконтактах, и прочих UFO :)
т.е. в качестве сервера будут выступать клиентские системы, возможно организованные в облако.

о.О даже в златоглавой 100Мб/сек не то что не нижний тариф, а у многих провайдеров вообще отсутствует как класс.

на смом деле 17Мбит/сек. Входящая. Исходящий трафик никто не режет, вот он и получается 100Мбит.

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

это серьёзная проблема, и она не решится, если котент поделить между клиентами. Хранить всё своё у себя - пока ещё технологии до этого не доросли.

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

Kademlia как-то работает, со своими 1 500 000 компьютерами. ЧТО должно произойти, что-бы все они выключились?

[watashiwa_daredeska]

Kademlia как-то работает

Не смешно. Вы еще скажите, что grep работает, и это то же самое, что гугл, только на одной машине.

[drBatty]

Не смешно. Вы еще скажите, что grep работает, и это то же самое, что гугл, только на одной машине.

действительно, 1 300 000 000 файлов - мелочи какие...

[watashiwa_daredeska]

действительно, 1 300 000 000 файлов - мелочи какие...

А, ну да, ведь гугл — просто весь интернет выкачал и поиск родился сам собой от жары, влажности и плесени в датацентрах.

[drBatty]

А, ну да, ведь гугл — просто весь интернет выкачал и поиск родился сам собой от жары, влажности и плесени в датацентрах.

странно сравнивать коммерческую организацию Google с Kademlia. Да и зачем, если и так понятно, что google == коммерческая сеть серверов и гуглоботов. В отличие от неё Kademlia намного ближе к теме ТСа - никаких выделенных серверов там нет и в помине, да и вообще сервер один, и тот - виртуальный.

[sash-kan]

сеть … без … прочих UFO

но-но-но! без ufo сеть не взлетит!

[drBatty]

без ufo сеть не взлетит!

ладно, UFO оставим.

[watashiwa_daredeska]

В отличие от неё Kademlia намного ближе к теме ТСа

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

Filename searches are implemented using keywords. The filename is divided into its constituent words. Each of these keywords is hashed and stored in the network, together with the corresponding filename and file hash. A search involves choosing one of the keywords, contacting the node with an ID closest to that keyword hash, and retrieving the list of filenames that contain the keyword. Since every filename in the list has its hash attached, the chosen file can then be obtained in the normal way.

Более того, Kademlia — это даже не сеть, это некий алгоритм. Реализаций существует несколько — у torrent своя, у edonkey своя.

странно сравнивать коммерческую организацию Google с Kademlia.

Простите, но это не я влез с гуглом в обсуждение Kademlia, а ровно наоборот. Так что эту претензию не Вы мне должны предъявлять, а ровно наоборот.

[drBatty]

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

1. а это часто и не нужно никому. Ну например - поиск картинок, как их гугл не умел искать, так и не умеет (пробовал). Остаётся только поиск по имени...
2. никто не мешает вывернуть текстовый файл наизнанку, в точности так же, как это делается с именем. Единственная проблема - нечёткий поиск, но и эта проблема в принципе решаема.
В итоге, Kademlia вполне годна как поисковая система, хотя в её нынешней реализации искать можно только по имени файла (и ещё по дополнительной информации, которая также ЕМНИП индексируется. Речь про разнообразные EXIF'ы, и прочую метаинформацию, которую можно выдернуть из мультимедийных файлов)
Ну а то, что Kademlia Открытая и Свободная, дык это вроде совсем и не минус, только это позволяет ей не зависеть не от кого, в отличие от Googl, которому приходится резать и подтасовывать результаты поиска.

Более того, Kademlia — это даже не сеть, это некий алгоритм. Реализаций существует несколько — у torrent своя, у edonkey своя.

нет. Немного не так: алгоритм это распределённая хеш таблица (DHT) http://en.wikipedia.org/wiki/Distributed_hash_table
Реализация в amule/emule это Kademlia, к edonkey она не имеет никакого отношения, этот ваш edonkey уже давно и успешно похоронили. В torrent'ах имеется своя недоделанная реализация DHT, которая имеет два существенных минуса:
1. нет поиска по имени, потому эта реализация несамостоятельна, и не самодостаточна. Ей тоже нужен треккер.
2. она раздроблена, множество нод не участвуют в обмене DHT, а для такой сети это смерти подобно, в итоге эффектность такой сети близка к нулю. В итоге, оно годится разве что для закачки CP, доступ к которой на треккере закрыли админы, да и то...

странно сравнивать коммерческую организацию Google с Kademlia.

Простите, но это не я влез с гуглом в обсуждение Kademlia, а ровно наоборот. Так что эту претензию не Вы мне должны предъявлять, а ровно наоборот.

ИМХО в вашем контексте странно. Вы априори полагаете, что "медленные клиенты это ненадёжно", но это не так, если этих клиентов больше миллиона. Это мало того, что чрезвычайно надёжно, но ещё и очень быстро, ибо скорость поиска и получения файла в Kademlia ограничивается разве что скоростью ISP на вашем тарифе, сравнится может разве что локальные треккеры/DC++, но они локальные, да и доступны не у всех ISP.

[watashiwa_daredeska]

Это мало того, что чрезвычайно надёжно, но ещё и очень быстро, ибо скорость поиска и получения файла в Kademlia ограничивается разве что скоростью ISP на вашем тарифе

Неправда. Пропускная способность канала — это совсем не то же самое, что задержка. Они даже связаны не очень-то прямой зависимостью. Kedemlia предполагает при поиске установление большого количества соединений с разными нодами. По очереди. Поэтому поиск в eDonkey идет несколько секунд. По сравнению с долями секунды у классических поисковиков это вечность. По статистике большинство пользователей не готовы ждать более 4 сек.

2. никто не мешает вывернуть текстовый файл наизнанку

Вы хоть прочитайте алгоритм и попробуйте его осмыслить. Вывернуть его ничто не мешает, но объем передаваемых данных при поиске в Kademlia это O(n), где n — это объем данных. Сравните объем данных «1.5G имен файлов» и «весь текст в интернетах». А теперь прикиньте, какой объем получится при поиске по контенту всех файлов в интернете.

Вообще, я понимаю, если б Вы вылезли с предложением какого-нибудь YaCy, но Kademlia… Не позорьтесь, чесслово.

[watashiwa_daredeska]

Реализация в amule/emule это Kademlia,

Kad Network — developed originally by the eMule

http://en.wikipedia.org/wiki/Kademlia#Networks

Не Kademlia, а Kad — одна из реализаций.

к edonkey она не имеет никакого отношения, этот ваш edonkey уже давно и успешно похоронили.

Ok. Ошибся.

В torrent'ах имеется своя недоделанная реализация DHT

BitTorrent Uses a DHT based on an implementation of the Kademlia algorithm, for trackerless torrents.

http://en.wikipedia.org/wiki/Kademlia#Networks

[drBatty]

Неправда. Пропускная способность канала — это совсем не то же самое, что задержка. Они даже связаны не очень-то прямой зависимостью.

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

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

нет. там UDP, который и не предполагает никаких "соединений", пакеты забрасываются в сеть, и там блуждают как хотят. А "по очереди" это совсем другой процесс, который с поиском прямо не связан, каждая из ~1000 соседних нод действительно опрашивается по очереди, для исключения сбойных нод. Время цикла действительно очень большое, и составляет десятки минут, но это совсем не поиск, при поиске датаграмма _сразу_ отправляется в нужном направлении, на нужную ноду, и поиск занимает обычно 1..2 сек, или иногда 2..4 сек (если по дороге встретилась мёртвая нода)

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

ну дык сеть и была создана для закачки файлов, и какгбэ время поиска для такой системы нормальное. К тому же, Kademlia сложно внедрялась в массы, она ведь жрёт память/cpu/трафик, разработчикам пришлось так подобрать число запросов, что всё это было терпимо даже на компьютерах прошлого века и на dialup'е, очевидно, скорость от такого не повысилась...

Вы хоть прочитайте алгоритм и попробуйте его осмыслить. Вывернуть его ничто не мешает, но объем передаваемых данных при поиске в Kademlia это O(n), где n — это объем данных. Сравните объем данных «1.5G имен файлов» и «весь текст в интернетах». А теперь прикиньте, какой объем получится при поиске по контенту всех файлов в интернете.

небольшой на самом деле. Учитывая количество копипасты, да и вообще, вы вот пишете те же самые слова, что и я, новых нам не придумать...

[watashiwa_daredeska]

да и вообще, вы вот пишете те же самые слова, что и я, новых нам не придумать...

Понимаете ли, мне не интересно по слову «kademlia» найти слово «kademlia». Мне интересно найти полезный документ про «kademlia». Так что,

небольшой на самом деле

«ха» гугол раз. И нафига гуглу столько серверов? Слов-то не много. Да блин, при том количестве слов, которые есть, весь интернет на пару винчестеров из ближайшего магазина влезет.

В общем, мне не интересно общаться на таком уровне. Можете заблуждаться дальше. Можете засчитывать слив, я не обидчивый.

[Ism]

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

[watashiwa_daredeska]

Следующий шаг - система -подобная нейросети, которая хранит только то, что в нее положили в жестко структурированном виде

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

Всегото нужен стандарт хранения структурированной информации для текста.

А еще законодательно установленная смертная казнь для спамеров и технические средства их отслеживания на всей территории планеты. Ой… это же слежка за пользователями.

[drBatty]

Понимаете ли, мне не интересно по слову «kademlia» найти слово «kademlia». Мне интересно найти полезный документ про «kademlia». Так что,

нет таких документов. извините. единственная достоверная информация в сырцах. есть ещё труды математиков, но их довольно мало, и на практике они не очень полезны (там очень простая и небольшая теоретическая база).

«ха» гугол раз. И нафига гуглу столько серверов? Слов-то не много. Да блин, при том количестве слов, которые есть, весь интернет на пару винчестеров из ближайшего магазина влезет.

ну на пару винтов не влезет, а вот на 1 500 000 должно влезть. Ну если не весь, то значительная часть. Вы как-то упустили из виду, что гугл большой конечно, но и Kademlia тоже не на 3.5 юзеров (в отличие от других подобных сетей), ИЧСХ, пока есть порно, будет и Kademlia.

http://en.wikipedia.org/wiki/Kademlia#Networks
Не Kademlia, а Kad — одна из реализаций.

давайте без отсылки на вику, область новая, терминология ещё не устоялась. Авторитетных источников нет, и вика тут тоже не истина в последней инстанции. Даже en (ну а ru вообще без смеха читать невозможно). Kad просто сокращение от Kademlia, если я правильно понял самих разработчиков.

BitTorrent Uses a DHT based on an implementation of the Kademlia algorithm, for trackerless torrents.

то, что оно куда-то там включена ни о чём не говорит. я что-то не вижу пиров IRL. В саму Kademlia тоже Over9000 фич заряжено, из которых 95% НЕ работает. Такие дела. Основная помеха - наличие старых нод, на которых дополнительная информация просто срезается, потому и получается, что новые фичи на работают - путь запроса проходит через десяток узлов, и если хоть один клиент устарел, новая инфа будет потеряна. И это в emule, там по большому счёту всего один клиент, а в торрентах BitTorrent составляет лишь малую часть, потому Kademlia там в принципе не работает. Просто DHT работать в принципе могло-бы, но на практике толку от него чуть - большинство пиров не входят в DHT, со всеми вытекающими.

Не секрет , что бОльшая часть информации в гугле и любом поисковике - никому не нужный мусор

не надо на зеркало пенять, коли рожа крива. Большинство инфы в Сети - мусор. Большинство сайтов и файлов - порнография. Что вы хотите от поисковика?

Всегото нужен стандарт хранения структурированной информации для текста.

кому нужен? всем пофиг.

[Ism]

не надо на зеркало пенять, коли рожа крива. Большинство инфы в Сети - мусор. Большинство сайтов и файлов - порнография. Что вы хотите от поисковика?

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

[drBatty]

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

заметил. но я знаю только один способ - писать хорошие мануалы...

[watashiwa_daredeska]

ИЧСХ, пока есть порно, будет и Kademlia.

Для порно.

я что-то не вижу пиров IRL.

Я что-то не вижу поисковой системы на Kademlia IRL.

давайте без отсылки на вику

Отлично. Опишите алгоритм поиска документа в Kademlia. Подробно, по шагам. Кто куда что посылает, что получает в ответ. Чтобы был предмет обсуждения.

Авторитетных источников нет

единственная достоверная информация в сырцах.

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

Вы как-то забываете, что к моменту появления гугла уже вполне существовали «grep'ы всея интернета» и то, что сделало гугл настолько популярным, совершенно не относится к «найти страницу, на которой есть слова А и Б». А за время существования гугла интернет настолько изменился, что алгоритм, изобретенный гуглом, уже не работает. И Kademlia ну совершенно никаким боком не относится к решению той проблемы, которую решает сейчас гугл.

[drBatty]

ИЧСХ, пока есть порно, будет и Kademlia.

Для порно.

я ждал этого. А вы будете спорить с тем фактом, что весь ваш интернет по большому счёту для порно?

Я что-то не вижу поисковой системы на Kademlia IRL.

www.amule.org и наблюдайте.

Отлично. Опишите алгоритм поиска документа в Kademlia. Подробно, по шагам. Кто куда что посылает, что получает в ответ. Чтобы был предмет обсуждения.

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

Таким образом, запросы поиска встречаются с запросами на публикацию. Важно отметить, что ключевые ноды не имеют никакого отношения к файлам и ключевым словам. У меня вот много мультиков на китайском, причём совсем не хентай, а просто какой-то бред для девочек лет 7и. Никогда не качал ничего подобного.

Что-бы запросы действительно встретились, важно найти 1000 ближайших нод. Они действительно ближайшие по метрике. Ротация нод происходит постоянно, многие отваливаются (достаточно 1 раз не ответить), их место занимают новые, из нашей очереди и из других мест. Точнее, через другие ноды мы ищем наш хеш, таким образом находим ближайшие по метрике ноды.

Метрика считается очень просто - это число 1 в сумме по модулю два двух хешей.

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

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

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

И Kademlia ну совершенно никаким боком не относится к решению той проблемы, которую решает сейчас гугл.

гуглу сейчас не до алгоритмов собственно поиска/выдачи/индексации. Насколько я знаю, им сейчас сложно удерживать на плаву всю эту огромную махину. ИМХО постепенно они всё равно придут к схеме, похожей на Kademlia, другого пути нет.

[watashiwa_daredeska]

Ладно, повторю:
1. вычисляется хеш ключевого слова (если ищем по имени)
2. отправляется запрос одной (или нескольким) ближайшим (по метрике) нодам, они транслируют запрос далее, пока не упрутся в ту ноду, которая знает про этот файл(ы). Последняя нода(ы) отдаёт список источников, которые заинтересованны в данном файле(ах).

Это никакой не алгоритм. Это мутный поток слов, из которого невозможно понять, сколько запросов реально шлется по сети, какого объема и в каком порядке.

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

Если же ноды все-таки транслируют чужие запросы, то также рассчитайте, пожалуйста, общее число запросов в сети, которое будет сгенерировано на один исходный поисковый запрос.

ключевые ноды

А этого в Вашем описании алгоритма вообще нет.

Что-бы запросы действительно встретились

Запросы? Встретились? Где они должны встречаться? Или не должны?

Метрика считается очень просто - это число 1 в сумме по модулю два двух хешей.

Число единиц в сумме по модулю 2 всегда либо 0, либо 1. Это факт.

[drBatty]

это _описание_ када, не спецификация, и не статистика. Хотите статистики - запустите emule, и будет вам статистика с запросами и картинками. Порядок запросов неопределен, а число запросов не играет роли.

[watashiwa_daredeska]

www.amule.org и наблюдайте.

Когда он сможет найти http://superpeer1.das2.ewi.tudelft.nl/trac...ts/Kademlia.pdf по запросу «Kademlia: A Peer-to-peer Information System Based on the XOR Metric», тогда и понаблюдаю. Пока же, это УГ для порно и онеме.

Насколько я знаю, им сейчас сложно удерживать на плаву всю эту огромную махину.

Да ладно, какая там махина-то? Вы уже почти на коленке собрали поисковик. У них там всё проще.

это _описание_ када

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

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

при поиске датаграмма _сразу_ отправляется в нужном направлении, на нужную ноду

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

Хотите статистики

Не хочу. Я хочу услышать алгоритм, чтобы можно было сделать теоретические оценки сложности поиска в той системе p2p, которую вы предлагаете.

Статистику я и так вижу:
1. Объем данных ~100–200GiB (1.5G имен файлов)
2. Количество узлов ~1.5M
3. Время поиска ~10сек и больше.

Поисковик по всему интернету:
1. Объем данных ~100PiB (больше на ~6 порядков).
2. Количество узлов должно быть больше, значит время элементарой операции поиска (объекта по ключу) еще возрастет.
3. Время поиска?

[Ism]

Это никакой не алгоритм.

После этой фразы с watashiwa_daredeska бессмысленно спорить

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

Вообще тема распределенного взаимодействия очень не развита, поэтому мало кто знает, что действительно работает, а что нет

[drBatty]

Когда он сможет найти http://superpeer1.das2.ewi.tudelft.nl/trac...ts/Kademlia.pdf по запросу «Kademlia: A Peer-to-peer Information System Based on the XOR Metric», тогда и понаблюдаю. Пока же, это УГ для порно и онеме.

вы свои знания про Kademlia почерпнули из этого документа? Зря. Это концепт. Он имеет отношение к IRL такое же, как первые описания алгоритма BWT: хороший алгоритм, вот только имеет он смысл на блоках не меньших 1Мб, при этом требует 1000Гб ОЗУ, что и в 1994, и сейчас несколько многовато. А как вы думаете работает bzip2? На практике реальные алгоритмы несколько отличаются от концептов... Причём очень сильно.

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

в вашем описании не хватает вполне конкретных деталей:
1. что такое "следующий эл-т"
2. какое условие завершения этой процедуры, в предположении, что её надо повторять циклически?
Естественные ответы "1: след. в смысле на 1 больше, 2: пока не отсортируем" даёт нам пузырьковую сортировку, сложность которой как известно O(N^2) в среднем и в худшем, и O(N) в лучшем(когда уже отсортировано).
Каких деталей не хватает в моём описании? Вы спрашивайте, я попытаюсь ответить... Пока я вижу только такие вопросы:

>Если же ноды все-таки транслируют чужие запросы, то также рассчитайте, пожалуйста, общее число запросов в сети, которое будет сгенерировано на один исходный поисковый запрос.

зачем мне это рассчитывать, если есть emule(работает в wine, если что), который покажет вам и запросы, и картинки с их прохождением по сети, в _вашем_ конкретном случае? Дело в том, что в самом запросе есть и путь запроса, потому ваш узел может предоставить об этом информацию без каких-то дополнительных усилий. Если вас интересуют конкретные цифры, то запросов получается около 2х десятков, но число их вообще говоря может сильно меняться в зависимости от фазы луны, и погоды на Марсе. Такой ответ вас устраивает?

А этого в Вашем описании алгоритма вообще нет.

я думал вы догадаетесь. И в ответе это есть. Хорошо, "ключевыми" нодами я называю те узлы, хеш которых ближе всего к хешу запроса. Хеш ноды задаётся случайным числом в момент инсталяции ноды, хеш запроса считается как криптостойкая односторонняя хеш-сумма от самого запроса (используется md4 128бит), расстояние считается как число разных битов на одинаковых позициях в 128и битных хешах. Расстояние между одинаковыми хешами ==0, расстояние между хешами, в которых отличается только 1 бит ==1.

Запросы? Встретились? Где они должны встречаться? Или не должны?

должны встретится на тех самых ключевых нодах. Информация сохраняется на всех узлах по пути, но только на ключевых нодах все пути сходятся в точку. Графически это можно представить как путь шарика на неровной поверхности, который скатывается к локальному минимуму. Причём из совершенно случайной точки. В этом-то минимуме все шарики и встречаются, что очевидно. Если все ноды связаны друг с другом (не обязательно напрямую), то минимум является ещё и глобальным, достигается это тем, что нода сама находит своё место в этом 128и мерном пространстве, подбирая своих соседок так, что-бы они были похожи на неё. Я думаю понятно, почему в этом случае пространство получается искривлённым должным образом (что-бы все шарики скатывались хоть и разными путями, но в одну точку). IRL это конечно не точка, а некое плато, из нескольких нод. Так получается потому, что число доступных хешей намного больше числа узлов, и потому вероятность точного совпадения равна IRL нулю. За то мы имеем несколько наилучших неточных совпадений, в которых и аккумулируется информация. Эти ноды резервируют друг друга, причём динамически.

Число единиц в сумме по модулю 2 всегда либо 0, либо 1. Это факт.

0110 ⊻ 1011 == 1101
имеем 3 единицы. Расстояние равно 3.

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

при поиске датаграмма _сразу_ отправляется в нужном направлении, на нужную ноду

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

это не утверждения. Это подробности единственной _рабочей_ реализации. То, что они не совпадают с найденном вами концептом - проблема концепта. Математики вообще имеют странные понятия про вычисляемость алгоритмов - если задача разрешена за конечное число действий, то она разрешена. Проблемы IRL (1Т оперативной памяти, или там канал связи на 100Гбит в сек) их абсолютно НЕ волнуют. Потому алгоритмы и приходится переделывать так, что-бы они работали IRL. И если по вашему

Вывернуть его ничто не мешает, но объем передаваемых данных при поиске в Kademlia это O(n), где n — это объем данных.

то IRL достаточно передать пару десятков запросов, каждый из которых в несколько К.

Не хочу. Я хочу услышать алгоритм, чтобы можно было сделать теоретические оценки сложности поиска в той системе p2p, которую вы предлагаете.

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

Поисковик по всему интернету:
1. Объем данных ~100PiB (больше на ~6 порядков).

ну и сколько из этого проиндексированно гуглом? К тому же вы таки нечестно считаете - большинство информации - порно картинки/порно видео, которое совсем не текстовое, и совсем непроиндексировано. Вот если вы посчитаете, сколько _текстовой_ информации (пригодной для индексации) в интернете, это будет интереснее.

PS: кстати, по запросу Kademlia в этой самой Kademlia менее чем за 10сек находится около сотни любопытных документов, в частности вот: ed2k://|file|eMule%20-%20Kademlia%20(Kad)%20A%20Peer-to-peer%20Information%20System%20Based%20on%20the%20XOR%20Metric.pdf|81047|B96817E90CDD4CCC4CD56E5FDC3899E7|/

[watashiwa_daredeska]

в вашем описании не хватает вполне конкретных деталей:
1. что такое "следующий эл-т"

Вот, похоже, Вы начинаете понимать. В вашем описании тоже нет конкретного описания выбора ближайших узлов. Так что, количество запросов может варьироваться от O(1) до O(n). Точно так же, как под приведенное мной описание подходит как пузырьковая сортировка, так и quicksort.

Информация сохраняется на всех узлах по пути, но только на ключевых нодах все пути сходятся в точку. Графически это можно представить как путь шарика на неровной поверхности, который скатывается к локальному минимуму. Причём из совершенно случайной точки. В этом-то минимуме все шарики и встречаются, что очевидно.

Не надо опускаться до детсадовских аналогий. Лучше наоборот, поднимитесь до нормального уровня обсуждения.

вы свои знания про Kademlia почерпнули из этого документа? Зря. Это концепт.

Раз Вы говорите, что реализация отличается, так и быть — проверил в исходниках aMule. Существенных отличий от «концепта» не увидел. Из того, что увидел:

они транслируют запрос далее

Неверно. Не транслируют.

Информация сохраняется на всех узлах по пути

Неверно. Не сохраняется никакой информации кроме {IP, Port, ID} пира с целью добавить в список «соседей».

подбирая своих соседок так, что-бы они были похожи на неё

Неверно. Одна из основных идей для быстрого поиска — подобрать соседей, которые максимально непохожи. Иначе при поиске получится обход сети маленькими шажками, O(n).

Расстояние между одинаковыми хешами ==0, расстояние между хешами, в которых отличается только 1 бит ==1.

Неверно. Расстояние — это просто побитовый XOR. Т.е. 0000 «ближе» к 0011, чем к 0100, хотя 0011 отличается двумя битами, а 0100 — одним.

Это подробности единственной _рабочей_ реализации.

Какой? Покажите мне ее.