|
Проект OGR (Optimal Golomb Rulers, Оптимальные линейки Голомба)
- Что такое Оптимальные линейки Голомба?
Отличное объяснение того, что это такое, дано на сайте Марка Гарри (Mark Garry): http://members.aol.com/golomb20/intro.htm. На самом деле, базовое OGR-ядро клиента представляет собой адаптацию работы Марка.
[Примечание переводчика. Вкратце задача формулируется следующим образом. Рассматривается линейка с фиксированным количеством делений. Расстояния между делениями, кратные некоторому минимальному значению, соответствуют неотрицательным целым числам, причем расстояние между любой парой делений должно быть уникальным. Пример простейшей линейки с тремя делениями - 0,1,3 - расстояния между делениями - 1, 2, 3. Общее количество пар делений для линейки с N делениями равно числу сочетаний из N по 2, т.е. N*(N-1)/2. Оптимальной линейкой Голомба называется линейка с минимальными расстояниями между делениями. Приведенная в качестве примера линейка с тремя делениями является одновременно и оптимальной. Для большого количества делений объем вычислений, необходимых для проверки оптимальности, резко возрастает.]
- Где могут пригодиться найденные OGR?
OGR имеют много практически приложений, такие как расположение сенсоров в рентгеноскопической кристаллографии, радиоастрономия и т.м. Они также играют важную роль в комбинаторике, теории кодирования и коммуникация. Доктор Голомб одним из первых проанализировал их использование в этих областях. На этой странице перечислены некоторые документы, демонстрирующие применимость линеек Голомба в теории информации и коммуникациях.
lists some papers that show how Golomb rulers can be useful in the fields of information theory and communications.
- Зачем мы этим занимаемся, если известы линейки Голомба длиной до 150 единиц?
Существует ряд справочников, перечисляющих наиболее известные линейки, например,
список Джеймса Ширера (James B. Shearer)? содержащий список линеек вплоть до 150 отметок. Однако, следует отметить, что для большинства из перечисленных там линеек (т.е. практически все, большие 23), вовсе не была доказана их оптимальность. Так что вполне вероятно, что можно найти и более удачные решения.
- Сущeствует ли приз за победу в OGR?
Не в денежном виде. В отличие от RC5 и других криптоконкурсов, в которых принимает участие distributed.net, никто не устанавливал приз за нахождение новой, более короткой линейки Голомба.
Но это дает вам возможность поучаствовать в увеличении суммарных знаний человечества, и, может быть, даже будете упомянуты где-нибудь в сноске в како-нибудь непонятном математическом журнале.
И это улучшит вашу карму.
Поправка:
На самом деле, уже появился и приз. Джона Шульте (Jonah Schulte) предлагает победителю 20 долларов США :) Если обнаружится более одного "победителя" OGR, Джона выберет одного из них случайным образом.
Поскольку OGR имеет больше отношения к "истощению всех возможностей", в отличии от конкурса по нахождению корректного ключа, Алекс Хейтон (Alex "froggie" Heighton) предлагает один английский шиллинг тому, кто отправит последний блок.
NukeEmUp@ThePentagon.com предложил победителю 50 USD.
neil@whatUseek.com также отправит вам чек на 50 USD в случае вашей победы. Он считает это небольшой платой за то, что вы уменьшаете свои шансы выиграть RC5 и увеличиваете его :)
Hit1Hard предложил отправить победителю 25 флоринов, "поскольку у нас, голландцев, самые красивые деньги в мире".
- Какие версии клиентов и прокси необходимы для работы с OGR?
Прокси: Версия 311 и выше. Однако, из-за множества проблем с сетью в версии 311, лучше обновить ее до версии 313 и выше.
Клиент: Требуется v2.8009.460 и выше. Существует ряд более ранних версий, способных обрабатывать OGR, но из-за проблем с верификацией все, что будет рассчитано этими версиями, будет игнорироваться серверами. (Замечание: OGR может быть автоматически запрещен в операционных системах с кооперативной многозадачностью на слабых компьютерах. Подробности описаны здесь: Почему OGR запрещен на моей машине?).
- Счетчик персонального прокси неравномерно скачет при получении готовых блоков (stubs).
Далее следует пример протокола при последовательной отправке OGR-блоков на персональный прокси:
[2000-02-14 23:56:33] ogr r=16/16, d=3/3, 63.3 Mnodes/sec, tot=19
[2000-02-14 23:57:37] ogr r=16/16, d=4/3, 75.1 Mnodes/sec, tot=22
[2000-02-14 23:58:35] ogr r=16/16, d=5/3, 91.2 Mnodes/sec, tot=26
Счетчик totalNotify для OGR отображает старшее 32-битное слово общего числа завершенных OGR-узлов.
В нашем случае в каждом OGR-блоке было 13.52 миллиардов узлов (13.52 Gnodes, 13.52*10^9). Старшее 32-битное слово этого числа - (13.52*10^9)/2^32=3.178, что и является причиной того, что счетчик в нашем случае увелчивается на тройку.
На самом деле прокси хранит полное 64-битное слово с общим числом проверенных узлов, но в поле "tot=" выводятся только старшие 32 бита.
- Каково общее число блоков в OGR-24?
В OGR-24 задано примерно 6 миллионов блоков на каждый проход (планируется провести два полных прохода в целях верификации). Все эти блоки содержат различное число узлов, примерно от 900 тысяч до 150 миллиардов. Трехмерные графики на этой странице показывают диапазон и оценку числа узлов в любом блоке. Горизонтальные оси соответствуют первым двум числам в распределенных блоках (т.е. "x" и "y" в "25/x-y-?-?-?"), а высота графика соответствует числу узлов в обработанном блоке.
Учтите, что число узлов в данном блоке не имеет абсолютно никакого отношения к длине или оптимальности линейки. Это число просто показывает количество возможных линеек Голомба, которые были проверены в пределах префикса данного узла, причем каждая из которых может оказаться "оптимальнее" существующей.
- Почему OGR запрещен на моей машине?
OGR может быть автоматически запрещен в операционных системах с кооперативной многозадачностью, которые запущены на относительно слабых компьютерах.
Далее приведен список комбинаций ОС и процессоров, где в настоящее время действует этот запрет:
- RISC OS/ARM: (если клиент не был запущен в вытесняющем режиме)
все процессоры
- MacOS/68k
все процессоры 680x0
- MacOS/PPC:
PPC601
- Windows16/x86:
процессоры класса i386, i486, i586 (включая Cx6x86 и K5)
- NetWare/x86:
все процессоры
В системах с кооперативной многозадачностью клиент сам управляет своим исполнением: делает паузу, далее выполняет расчет определенного чила ключей/узлов (timeslice), делает паузу, считает и т.п.
Размер порции для непрерывного расчета определяется динамически в процессе работы и обычно определяется из следующей формулы: скорость_расчета/частота_пауз (*), где частота_пауз - полустатичное значение, означающее, сколько раз в секунду клиент должен передавать управление системе, чтобы она сохранила свою управляемость, а скорость_расчета постоянно обновляется.
Для OGR, который имеет значительные накладные расходы, чем больше порция, тем эффективнее ядро. Другими словами: в случае небольших порций, каковые должны быть на медленных машинах, ядро большую часть времени будет заниматься запуском/остановкой, а не сообственно расчетом.
Более того, невозможно определить точный размер порции, и в некоторых случаях ядро OGR может просчитать на несколько сотен тысяч блоков больше, чем ему было сказано. В менее критичных окружениях, такие как Win16 и MacOS подобные "замирания" системы могут быть терпимыми, и мы оставили пользователю возможность самому решать, разрешить ли такое поведение. Но в критичных системах, таких как серверы NetWare, любые "замирания" системы могут иметь катастрофические последствия, так что для NetWare OGR полностью запрещен.
*: Для всех практических целей упомянутой формулы должно быть достаточно, но здесь есть пара нюансов:
Продолжительность пауз. Если другие задачи выполняются в течение значительного времени, или операционная система навязывает максимальную частоту переключения задач по избежание слишком частого переключения на одну и ту же задачу, то эта "продолжительность пауз" может повлиять на скорость расчета, фигурирующую в этой формуле, тем самым снизив размер порции.
Точность таймера. Минимальный квант времени (как расчета, так и паузы) равен разрешению системных часов. Используя длинные временные интервалы и усредняя результаты, можно повысить точность вычислений, но она в любом случае не может быть выше половины периода системного таймера. Это означает, что если разрешение таймера равно, например, 100 миллисекундам, то клиент сможет в лучшем случае, делать паузу только каждые 50 миллисекунд.
- Какая наиболее оптимальная линейка была найдена dnet?
Клиент не пытается дать оценку оптимальности рассматриваемых линеек. Вместо этого он только пытается проверить, является ли данная линейка лучше, чем лучшая линейка, известная математикам. Как только он определяет, что линейка (узел) не лучше, чем лучшая из известных, обработка этого узла прекращается и осуществляется переход к следующему. Таким образом, клиент передает только информацию об успехах, когда он нашел нечто лучшее, чем все, что было раньше.
Существует определенный научный, и даже потенциально финансовый интерес к поиску альтернативных линеек, которые имеют такую же длину, как уже известные, но отличаются от них. Кроме того, они позволяют контролировать ход процесса.
- Почему ни на одной веб-странице не показан общий процент проделанной работы?
Процесс определения точного текущего процента завершенности работы требует значительно больших расчетов, чем это было в случае наших криптографических проектов, поэтому оказалось довольно затруднительно проводить этот расчет регулярно.
Эта оценка зависит от повторного сравнения всех просчитанных блоков, учета распределения блоков, которые ушли на второй верификационный проход, и таким образом требует полной обработки нескольких сотен мегабайт сжатых данных. Мы намерены сообщать о периодических обновлениях этой оценки на информационной странице организаторов проектастранице: http://n0cgi.distributed.net/cgi/dnet-finger.cgi.
- Почему некоторые блоки рассчитываются быстрее других? Мой блок остановился на 1 или 2 процентах.
По своей природе блоки OGR сильно варьируются по числу узлов, которые должны быть проверены клиентом. Следовательно, некоторые блоки могут быть боработаны гораздо быстрее других. Кроме того, иногда может казаться, что нет никакого прогресса в обработке данного блока, даже после нескольких минут или часов работы, хотя на самом деле он просто не может быть выражен в единицах процентов. Медленная обработка части блока вовсе не обязательно соответствует скорости обработки всего блока.
В целом, блоки, имеющие метки большего размера, оказываются "проще", чем состоящие целиком из небольших меток. Кроме того, число узлов в блоке обычно довольно предсказуемо на основе значений первых двух меток блока. На http://www.distributed.net/statistics/ogr/ приведены графики распределений числа узлов в зависимости от этих значений для OGR-24, на http://www.hewgill.com/golomb/ - аналогичные графики для старого проекта OGR-21.
К сожалению, при оценке блоков существует довольно значительная неопределенность. При обработке клиент может обнаружить, что нет необходимости обрабатывать часть блока, после чего просто ее пропустить. Это весьма затрудняет задачу создания индикатора, отображающего процесс работы, и работающего по линейному закону.
Отметим также, что при продвижении через блок проценты начинают "бежать быстрее". В целом, первые 10 процентов могут занять большую часть времени.
Не тревожьтесь, если блок рассчитывается 40 и более часов на машине класса PIII-500. Это не оценка сложности, а всего лишь размер единицы обработки. Не забывайте, что в других математических проектах, таких как, например расчет чисел Мерсенна, единица обработки может обсчитываться несколько недель. Очень небольшой размер блоков в предыдущих проектах RC5 "испортил" психологию многих участников, ожидающих теперь, что новые порции данных будут обрабатываться за сравнимое время, т.е. за считанные минуты/часы.
- Почему я получаю слишком маленькие/большие OGR-блоки?
При переходе от OGR-24 к OGR-25 в тестовых целях было роздано небольшое число блоков переменного размера для публичной оценки времени их расчета. Для OGR-25 мы остановились на распределении так называемых "шестерных блоков" (6-stubs), т.е. блоках, в которых 6 первых отметок задаются нашими серверами. Подобные блоки отображаются клиентами как "25/1-2-3-4-5-6". Блоки, имеющие более чем 6 отметок, обрабатываются значительно быстрее, с меньшим числом - значительно медленнее.
Хотя мы обычно пытались вкрапливать эти экспериментальные блоки OGR-25 в раздаваемые блоки OGR-24 для минимизации числа таких блоков, попадающих одному человеку, мы обнаружили, что это не всегда удавалось.
В любом случае, поскольку это нашего преднамеренное тестирование уже завершено, вы можете с чистой совестью удалять свой файл buff-in.ogr, если увидите, что ваш клиент обрабатывает блоки OGR-25, в которых не указано после слеша ровно 6 чисел - если вы слишком нетерпеливы и желаете обрабатывать блоки нормального размера (при этом вы можете выкинуть и часть блоков нормального размера, но они в любом случае будут отданы на обработку повторно, так что особой проблемы в этом нет, хотя обычно так делать и не стоит).
Хотя в статистике учитываются только блоки OGR-25 с 6 отметками, при обработке этих тестовых блоков большего и меньшего размера все равно происходит корректная проверка части пространства блоков, и эта обработка так же продвигает нас к завершению проекта, как и эквивалентное число блоков стандартного размера. Результаты обработки этих нестандартных блоков будут также полезны на втором верификационном проходе.
- Почему я не всегда могу получить OGR-блоки?
Возможно, ваш случай объяснен на этой странице.
|
подробно о проекте
Анализ криптографических сетевых...
