WS
а если еще притащить византийских генералов - то таки нет)
Пока без них. Считаем, что канал связи между Алисой и Бобом надежен
Size: a a a
2020 May 27
WS
Если же это не так, то задача двух генералов будет. Но это о другом
N
еще вопрос - как часто измеряется значение величины и хранится ли история
ИК
Да, задача в той постановке некорректна (решения нет). Но, например, можно утверждать, что если Алиса может передать Бобу 1 бит, то консенсус достижим (конструктивно)
По-моему, это искусственные ограничения. Консенсус подразумевает коммуникацию, если взаимодействия нет, но система разделена, и о согласованности в любой момент не может быть и речи (см теорему CAP), если же коммуникация возможна, то не вижу причин ограничивать её 1 или несколькими битами. Такой лимит, во-первых нелогичен, во-вторых технически сложно реализуем, потому что накладные расходы значительно больше информативного сообщения
WS
еще вопрос - как часто измеряется значение величины и хранится ли история
Можно разные постановки делать. В базовой задаче всё один раз происходит...
WS
По-моему, это искусственные ограничения. Консенсус подразумевает коммуникацию, если взаимодействия нет, но система разделена, и о согласованности в любой момент не может быть и речи (см теорему CAP), если же коммуникация возможна, то не вижу причин ограничивать её 1 или несколькими битами. Такой лимит, во-первых нелогичен, во-вторых технически сложно реализуем, потому что накладные расходы значительно больше информативного сообщения
Это модельная задача. Но она из практики - канал может быть очень тонким, мы всегда хотим минимизировать передачу информации. Вот и вопрос, каков теоретический предел например. Вот утверждается, что бита достаточно
WS
Коммуникация посредством измерения общей величины - это тоже особый канал коммуникации фактически.
RS
Центральная предельная теорема? Только если t_a и t_b достаточно большие векторы, но получение одинакового результата без коммуникации не может быть гарантировано никогда
Define одинаковый
Можно одинаково оценить распределение неизвестной величины
Можно одинаково оценить распределение неизвестной величины
WS
Define одинаковый
Можно одинаково оценить распределение неизвестной величины
Можно одинаково оценить распределение неизвестной величины
Наверно можно сделать с контролируемой точностью (от числа измерений)? На практике наверно достаточно, но минус - большое кол-во измерений
ИК
Define одинаковый
Можно одинаково оценить распределение неизвестной величины
Можно одинаково оценить распределение неизвестной величины
Приблизительно
RS
Наверно можно сделать с контролируемой точностью (от числа измерений)? На практике наверно достаточно, но минус - большое кол-во измерений
Если шум нормально распределен, то на практике достаточно небольшого кол-ва измерений
https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
WS
Если шум нормально распределен, то на практике достаточно небольшого кол-ва измерений
https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
Ну, в жизни ситуация сложнее - величина вообще случайный процесс, с не особо известными свойствами. При этом оценки границ приемлемы грубые, но вот нарушение консенсуса (т.е. отличие оценок у сторон) - гораздо хуже, чем низкое качество этих оценок...
RS
Можно учитывать дисперсию оценок в использующей эти данные системе
RS
В первый раз слышу о консенсусе в контексте случайных величин
WS
Расскажу, как используется у меня. Алиса и Боб выбирают длительность временнОго слота для коммуникации друг с другом. Они измеряют время распространения сигнала. Размер слота должен быть тем больше, чем больше это время. Если они выберут разный размер слота, то будет происходить рассинхронизация. При этом Алиса и Боб сами движутся относительно друг друга по неизвестной траектории (в самолетах находятся, например). Ну вот собственно один из подходов - иметь консенсус оценки времени распространения сигнала на какой-то период времени. Другой подход - видимо подкручивать синхронизацию слотов с каждым пришедшим сигналом...
RS
Можно вместо фиксированных слотов иметь таймаут для текущего процесса коммуникации. После него любой из участников может начать договариваться о новых параметрах.
WS
Можно вместо фиксированных слотов иметь таймаут для текущего процесса коммуникации. После него любой из участников может начать договариваться о новых параметрах.
Это так и будет делаться плюс-минус. Вопрос в том, как именно договариваться. Можно каждому из них передать другому своё значение, взять среднее к примеру - и отложить полуинтервал (грубую оценку изменения среднего случайного процесса - например, по максимальной относительной скорости, за время таймаута) по краям. Ну а можно передать 1 бит и получить результат не хуже)
RS
Расскажу, как используется у меня. Алиса и Боб выбирают длительность временнОго слота для коммуникации друг с другом. Они измеряют время распространения сигнала. Размер слота должен быть тем больше, чем больше это время. Если они выберут разный размер слота, то будет происходить рассинхронизация. При этом Алиса и Боб сами движутся относительно друг друга по неизвестной траектории (в самолетах находятся, например). Ну вот собственно один из подходов - иметь консенсус оценки времени распространения сигнала на какой-то период времени. Другой подход - видимо подкручивать синхронизацию слотов с каждым пришедшим сигналом...
Канал может быть несимметричным, зачем договариваться? Каждый оценивает индивидуально.
WS
Канал может быть несимметричным, зачем договариваться? Каждый оценивает индивидуально.
Если они ничего не знают о стратегии поведения другого, то очень трудно сделать эффективные алгоритмы поиска (конкретно у меня здесь всё отягощено направленностью приемопередатчиков)