Обновил до версии 0.1.4, добавил свой вариант решения. Не ахти что по оверхеду — в среднем 520% для больших данных. Однако целостность поддерживается надежно, BER примерно 3e-7.
Десять раз слать бит с повторением — это, извините, тупо. Плюс не решает проблемы с пропущенным битом (вы ждете получения 10).
Б-же упаси, этот пример здесь только как аналог сортировки пузырьком — показать, что задачу выполняет, но максимально неэффективным способом.
И проблем со считыванием нет — this.read возвращает весь накопленный буфер, если его длина меньше запрашиваемой. А на стороне передающей машины стоит ограничитель интенсивности отправки, чтобы кадры не слеплялись.
В целом, да, позитивные/негативные подтверждения с таймаутами, это путь к успеху.
Ну здорово же, особо не напрягаясь, уменьшили избыточность, использовав запрос о переотправке команды :)
Если вы не против, добавлю этот вариант в примеры кода, с указанием авторства в комментариях.
Теоретически возможно даже полное исчезновение сообщения
Для этого и дан нам двусторонний канал. Подтверждения о получении данных. Подтверждение о получении подтверждения. Подтверждение о получении подтверждения подтверждения, и тд. Плюс есть отсчет таймаутов на получение подтверждений, для последующей переотправки.
О двух генералах — в точку. Однако, мы можем решить задачу с некоторой, устраивающей нас степенью надежности. Выше в комментариях DistortNeo говорит об этом.
Суть статьи в том, чтобы дать потеоретизировать (и попрактиковаться онлайн) над задачами, обычно лежащими вне области прикладного программирования. Ну соревнуются же люди в написании "змейки" за 50 строк. Разумеется, не всем это будет интересно.
Выслушивать комментаторов тоже интересно. Вам несложно чуть развить мысль, как использовать коды Грея для пропущенных бит?
Я забыл упомянуть, как генерируются ошибки, там всё примитивно — два независимых случайных события для каждого бита, 5% потерять, 5% сломать.
Вообще, кажется, это и вправду слишком много. Надо было в исходной задаче сделать 1% и 1%. Хотя можно и самому регулировать эти значения на интерфейсе.
Напишете с оверхедом 500%, возьмут в Яндекс без собеседований, будет уже круто :)
Ночью создавал решение, выходило где-то на 600%, но не дооформил до конца, ушел спать.
Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.
Так сделать его достаточно длинным, чтобы сделать подбор экономически нецелесообразным?
Да, и, если не ошибаюсь, проще подобрать два ключа по 60 бит, чем один по 120.
Я правильно понимаю, что SIGNATURE_KEY попадает заранее на обе машины, притом по некоему безопасному каналу? А почему бы тогда не использовать его как постоянный ключ для симметричного шифра?
Это всё пережитки прошлой эпохи, до введения read&comment учеток. В ту пору Хабр выгодно отличался от того же ЛОРа тем, что читая комментарии, не нужно было прогонять каждый из них через ментальный детектор троллинга и трешовости.
Теперь читаешь все эти сотни комментариев к статьям о вакцинах, астрологии, ГМО, религиях, и не знаешь, то ли плакать, то ли смеяться, то ли просто /facepalm делать.
К сожалению, это не генетический алгоритм. Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных (в Вашем случае — игрового поля со случайным состоянием ячеек). Вы же ищете решение для конкретного поля перебором с эволюционной эвристикой. Скромно рекомендую для ознакомления эту статью.
Обновил до версии 0.1.4, добавил свой вариант решения. Не ахти что по оверхеду — в среднем 520% для больших данных. Однако целостность поддерживается надежно, BER примерно 3e-7.
Подскази для "правильных" решений, могут быть например, здесь: https://habrahabr.ru/post/332134/#comment_10295162 Я могу лишь показать "своё", и то, не раньше чем вернусь домой и допишу :)
Б-же упаси, этот пример здесь только как аналог сортировки пузырьком — показать, что задачу выполняет, но максимально неэффективным способом.
И проблем со считыванием нет —
this.readвозвращает весь накопленный буфер, если его длина меньше запрашиваемой. А на стороне передающей машины стоит ограничитель интенсивности отправки, чтобы кадры не слеплялись.В целом, да, позитивные/негативные подтверждения с таймаутами, это путь к успеху.
Добавлено, с исправлением.
Ну здорово же, особо не напрягаясь, уменьшили избыточность, использовав запрос о переотправке команды :)
Если вы не против, добавлю этот вариант в примеры кода, с указанием авторства в комментариях.
Для этого и дан нам двусторонний канал. Подтверждения о получении данных. Подтверждение о получении подтверждения. Подтверждение о получении подтверждения подтверждения, и тд. Плюс есть отсчет таймаутов на получение подтверждений, для последующей переотправки.
О двух генералах — в точку. Однако, мы можем решить задачу с некоторой, устраивающей нас степенью надежности. Выше в комментариях DistortNeo говорит об этом.
Суть статьи в том, чтобы дать потеоретизировать (и попрактиковаться онлайн) над задачами, обычно лежащими вне области прикладного программирования. Ну соревнуются же люди в написании "змейки" за 50 строк. Разумеется, не всем это будет интересно.
Выслушивать комментаторов тоже интересно. Вам несложно чуть развить мысль, как использовать коды Грея для пропущенных бит?
Я забыл упомянуть, как генерируются ошибки, там всё примитивно — два независимых случайных события для каждого бита, 5% потерять, 5% сломать.
Вообще, кажется, это и вправду слишком много. Надо было в исходной задаче сделать 1% и 1%. Хотя можно и самому регулировать эти значения на интерфейсе.
Напишете с оверхедом 500%,
возьмут в Яндекс без собеседований, будет уже круто :)Ночью создавал решение, выходило где-то на 600%, но не дооформил до конца, ушел спать.
Спасибо за развернутый анализ! По моим прикидкам тоже получается, что оверхед ниже 400-500% при таком канале обеспечить не получится.
Тут можно поподробнее, каким способом это достигается?
Манчестерское кодирование решает задачи физического уровня, а у нас тут, скорее, с канальным уровнем вопросы.
Совершенно верно! Сейчас уточню это в описании.
Поправьте меня, если это не так, но, вроде бы, коды Рида — Соломона, а также алгоритмы лежащие в основе RAID, решают только проблему искаженных данных, остающихся равными по длине исходным. Когда в среде передачи происходит в том числе и их произвольная потеря, всё становится гора-а-аздо интересней.
Так сделать его достаточно длинным, чтобы сделать подбор экономически нецелесообразным?
Да, и, если не ошибаюсь, проще подобрать два ключа по 60 бит, чем один по 120.
Я правильно понимаю, что SIGNATURE_KEY попадает заранее на обе машины, притом по некоему безопасному каналу? А почему бы тогда не использовать его как постоянный ключ для симметричного шифра?
Вот этот ученый много экспериментов ставил.
upd. Не вставляется ссылка, смотрите wiki: Мишель Сифр
(ц)почти Уинстон ЧерчилльТеперь читаешь все эти сотни комментариев к статьям о вакцинах, астрологии, ГМО, религиях, и не знаешь, то ли плакать, то ли смеяться, то ли просто /facepalm делать.
К сожалению, это не генетический алгоритм. Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных (в Вашем случае — игрового поля со случайным состоянием ячеек). Вы же ищете решение для конкретного поля перебором с эволюционной эвристикой. Скромно рекомендую для ознакомления эту статью.
Хорошая статья, единственное замечание: