Проект P2Pinet
Feb. 8th, 2014 11:45 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
codedotВ связи с идеей распределенных сетей взаимодействия, хотелось бы вернуться к проекту компилятора
Как модифицировать компилятор
P2P-сеть всегда основана на дублировании информации для случаев, когда одна из нод отключается от сети. Заметим, что стэк активных пар, используемый в проекте
В
Во-первых, правила могут быть приватными для группы нод. Во-вторых, правила могут иметь побочные действия, как в проекте
Следует подчеркнуть, что сами по себе сети взаимодействия неэффективны с вычислительной точки зрения - существующие процессоры справляются с вычислительными задачами несравнимо лучше. Но оптимальная редукция, вопреки названию, вообще не рассматривает вопрос о том, как проводить собственно редукцию и не предлагает никаких решений на этот счет. Вместо этого, она предлагает стратегию для объединения работы (optimal sharing). Последнее и можно было бы позаимствовать от систем взаимодействия для оптимального разделения работы и данных между частями распределенной вычислительной системы.
Конкретно эту задачу сети взаимодействия и решают на качественном уровне. Они служат своеобразным планировщиком задач, который уже, в свою очередь, управляет остальными процессорами как устройствами, чем-то похожим на OpenCL образом. Однако, в отличие от OpenCL (который тоже, в принципе, может быть использован в распределенной сети), сети взаимодействия позволили бы делать и само планирование децентрализованным, при этом избегая лишних обмена данных и дублирования работы.
Следующая схема иллюстрирует, как может быть представлена активная пара в распределенной децентрализованной сети взаимодействия (уникальные адреса и множество соединений вместо единого стека активных пар в случае компилятора
[{нода x} (доп. порты) = α1 - (гл. порт)] | {сеть} | [(гл. порт) - α2 = (доп. порты) {нода y}], где
x может совпадать с y;
агенты αi могут (и должны) быть продублированы (некоторыми) другими нодами;
все главные порты, которые не соединены с доп. портами должны быть доступны в сети с уникальным идентификатором;
связь между двумя дополнительными портами может быть представлена с помощью псевдо-агента
деревья с корнем в αi могут храниться локально вне сети пока сеть не редуцирует соответствующую активную пару.
В качестве базовой технологии можно было использовать приближающийся стандарт WebRTC, который уже, впрочем, работает в большинстве браузеров. Он был задумал для прямого видео/аудио-общения между пользователями без нагрузки на серверы, но также позволяет обмениваться произвольными данными между браузерами.
По астрономо-арифметическим соображениям, одного килобита на адрес хватает навсегда, а два килобита на уникальный идентификатор дают абсолютную гарантию отсутствия коллизий.
Такие длины идентификаторов напоминают характерные длины ключей RSA. Кстати, последний имеет гомоморфизм относительно умножения, а потому мог бы быть использован для приватных вычислений на основе той же самой распределенной вычислительной сети.
В принципе, сеть вообще могла бы функционировать редко или вовсе не взаимодействующими (под)сетями, идентификаторы агентов которых зашифрованы, к примеру, группами пользователей.
Формально на роль системы взаимодействия, на основе которой бы могла работать сеть, годятся, по крайней мере, следующие три варианта:
а) комбинаторы взаимодействия;
б) компактное представление λ-выражений;
в) универсум.
Последний предпочтительнее не только из-за неэффективности комбинаторов и функциональной чистоты λ-исчисления, но и из-за разных потребностей групп пользователей, а также возможности применить изоморфизм RSA-арифметику, используя, например, некоторые идентификаторы в качестве данных, что, в общем-то, логично, если учесть их сверх-избыточную длину.
Понятно, что система взаимодействия может иметь бесконечные сигнатуру (множество типов агентов) и множество правил взаимодействия. С помощью простого дизъюнктного объединения всех возможных систем взаимодействия мы можем получить единую универсальную систему взаимодействия, чья сигнатура содержит все возможные типы агентов, а множество правил - все возможные взаимодействия.
В обычной теории множеств это парадоксальная конструкция. Если ограничить множество систем взаимодействия только до тех, которые можно формализовать, то их становится счетное множество. А приняв во внимание астроно-арифметические соображения, то их вообще конечное множество с человеко-размерной длиной идентификаторов (килобит, в принципе, можно передать одним SMS).
Остается неясным как именно должно происходить применение правил взаимодействия и редукция сети. В частности, непонятно, можно ли, а если можно - то как именно производить проверку работу сети. Связанный вопрос возникает по поводу дублирования работы отстающими нодами: как держать их число на оптимальном уровне. Похоже, что требуется какой-то компромисс между числом дублирующих нод для надежности сети и неоптимальностью суммарной работы.
inet, который используется в MLC для механизма read-back. Приложение было реализовано уже после подготовки формального описания проекта и строго следуя проектной документации; имели место лишь мелкие уточнения и исправления по ходу работы.Как модифицировать компилятор
inet, чтобы получить вместо него распределенную универсальную P2P-сеть взаимодействия? Обозначим гипотетическую распределенную версию inet как p2pinet.P2P-сеть всегда основана на дублировании информации для случаев, когда одна из нод отключается от сети. Заметим, что стэк активных пар, используемый в проекте
inet, - это исчерпывающая информация о редуцируемой сети взаимодействия. Чаще всего (псевдо-)активная пара состоит не из двух агентов, а из агента и (псевдо-)агента wire, который служит для разыменования. Последнее в случае P2P-сети служило бы простым запросом на дублирование информации.В
p2pinet активные пары технически нигде не хранятся в явном виде, и ноды могут даже не знать, активна ли данная конкретная связь между одним идентификатором (портом) и каким-то другим в сети. Обмен информацией и (неявное) создание новых активных пар произходило бы в такой сети с помощью операции разыменования, а собственно применение правил взаимодействия - локально на нодах ввиду нескольких причин.Во-первых, правила могут быть приватными для группы нод. Во-вторых, правила могут иметь побочные действия, как в проекте
inet. В-третьих, набор правил может быть бесконечным и очень сложным. Наконец, одно из правил может быть вычислительно затратно, например вычисление n-ного простого числа.Следует подчеркнуть, что сами по себе сети взаимодействия неэффективны с вычислительной точки зрения - существующие процессоры справляются с вычислительными задачами несравнимо лучше. Но оптимальная редукция, вопреки названию, вообще не рассматривает вопрос о том, как проводить собственно редукцию и не предлагает никаких решений на этот счет. Вместо этого, она предлагает стратегию для объединения работы (optimal sharing). Последнее и можно было бы позаимствовать от систем взаимодействия для оптимального разделения работы и данных между частями распределенной вычислительной системы.
Конкретно эту задачу сети взаимодействия и решают на качественном уровне. Они служат своеобразным планировщиком задач, который уже, в свою очередь, управляет остальными процессорами как устройствами, чем-то похожим на OpenCL образом. Однако, в отличие от OpenCL (который тоже, в принципе, может быть использован в распределенной сети), сети взаимодействия позволили бы делать и само планирование децентрализованным, при этом избегая лишних обмена данных и дублирования работы.
Следующая схема иллюстрирует, как может быть представлена активная пара в распределенной децентрализованной сети взаимодействия (уникальные адреса и множество соединений вместо единого стека активных пар в случае компилятора
inet):[{нода x} (доп. порты) = α1 - (гл. порт)] | {сеть} | [(гл. порт) - α2 = (доп. порты) {нода y}], где
x может совпадать с y;
агенты αi могут (и должны) быть продублированы (некоторыми) другими нодами;
все главные порты, которые не соединены с доп. портами должны быть доступны в сети с уникальным идентификатором;
связь между двумя дополнительными портами может быть представлена с помощью псевдо-агента
wire из проекта inet;деревья с корнем в αi могут храниться локально вне сети пока сеть не редуцирует соответствующую активную пару.
В качестве базовой технологии можно было использовать приближающийся стандарт WebRTC, который уже, впрочем, работает в большинстве браузеров. Он был задумал для прямого видео/аудио-общения между пользователями без нагрузки на серверы, но также позволяет обмениваться произвольными данными между браузерами.
По астрономо-арифметическим соображениям, одного килобита на адрес хватает навсегда, а два килобита на уникальный идентификатор дают абсолютную гарантию отсутствия коллизий.
Такие длины идентификаторов напоминают характерные длины ключей RSA. Кстати, последний имеет гомоморфизм относительно умножения, а потому мог бы быть использован для приватных вычислений на основе той же самой распределенной вычислительной сети.
В принципе, сеть вообще могла бы функционировать редко или вовсе не взаимодействующими (под)сетями, идентификаторы агентов которых зашифрованы, к примеру, группами пользователей.
Формально на роль системы взаимодействия, на основе которой бы могла работать сеть, годятся, по крайней мере, следующие три варианта:
а) комбинаторы взаимодействия;
б) компактное представление λ-выражений;
в) универсум.
Последний предпочтительнее не только из-за неэффективности комбинаторов и функциональной чистоты λ-исчисления, но и из-за разных потребностей групп пользователей, а также возможности применить изоморфизм RSA-арифметику, используя, например, некоторые идентификаторы в качестве данных, что, в общем-то, логично, если учесть их сверх-избыточную длину.
Понятно, что система взаимодействия может иметь бесконечные сигнатуру (множество типов агентов) и множество правил взаимодействия. С помощью простого дизъюнктного объединения всех возможных систем взаимодействия мы можем получить единую универсальную систему взаимодействия, чья сигнатура содержит все возможные типы агентов, а множество правил - все возможные взаимодействия.
В обычной теории множеств это парадоксальная конструкция. Если ограничить множество систем взаимодействия только до тех, которые можно формализовать, то их становится счетное множество. А приняв во внимание астроно-арифметические соображения, то их вообще конечное множество с человеко-размерной длиной идентификаторов (килобит, в принципе, можно передать одним SMS).
Остается неясным как именно должно происходить применение правил взаимодействия и редукция сети. В частности, непонятно, можно ли, а если можно - то как именно производить проверку работу сети. Связанный вопрос возникает по поводу дублирования работы отстающими нодами: как держать их число на оптимальном уровне. Похоже, что требуется какой-то компромисс между числом дублирующих нод для надежности сети и неоптимальностью суммарной работы.
