Size: a a a

Scalability Camp — чат про распределенные системы (и про HPC)

2020 May 27

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Nikolay
а если еще притащить византийских генералов - то таки нет)
Пока без них. Считаем, что канал связи между Алисой и Бобом надежен
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Если же это не так, то задача двух генералов будет. Но это о другом
источник

N

Nikolay in Scalability Camp — чат про распределенные системы (и про HPC)
еще вопрос - как часто измеряется значение величины и хранится ли история
источник

ИК

Иван Калининский... in Scalability Camp — чат про распределенные системы (и про HPC)
Wire Snark
Да, задача в той постановке некорректна (решения нет). Но, например, можно утверждать, что если Алиса может передать Бобу 1 бит, то консенсус достижим (конструктивно)
По-моему, это искусственные ограничения. Консенсус подразумевает коммуникацию, если взаимодействия нет, но система разделена, и о согласованности в любой момент не может быть и речи (см теорему CAP), если же коммуникация возможна, то не вижу причин ограничивать её 1 или несколькими битами. Такой лимит, во-первых нелогичен, во-вторых технически сложно реализуем, потому что накладные расходы значительно больше информативного сообщения
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Nikolay
еще вопрос - как часто измеряется значение величины и хранится ли история
Можно разные постановки делать. В базовой задаче всё один раз происходит...
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Иван Калининский
По-моему, это искусственные ограничения. Консенсус подразумевает коммуникацию, если взаимодействия нет, но система разделена, и о согласованности в любой момент не может быть и речи (см теорему CAP), если же коммуникация возможна, то не вижу причин ограничивать её 1 или несколькими битами. Такой лимит, во-первых нелогичен, во-вторых технически сложно реализуем, потому что накладные расходы значительно больше информативного сообщения
Это модельная задача. Но она из практики - канал может быть очень тонким, мы всегда хотим минимизировать передачу информации. Вот и вопрос, каков теоретический предел например. Вот утверждается, что бита достаточно
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Коммуникация посредством измерения общей величины - это тоже особый канал коммуникации фактически.
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Иван Калининский
Центральная предельная теорема? Только если t_a и t_b достаточно большие векторы, но получение одинакового результата без коммуникации не может быть гарантировано никогда
Define одинаковый

Можно одинаково оценить распределение неизвестной величины
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Rinat Shigapov
Define одинаковый

Можно одинаково оценить распределение неизвестной величины
Наверно можно сделать с контролируемой точностью (от числа измерений)? На практике наверно достаточно, но минус - большое кол-во измерений
источник

ИК

Иван Калининский... in Scalability Camp — чат про распределенные системы (и про HPC)
Rinat Shigapov
Define одинаковый

Можно одинаково оценить распределение неизвестной величины
Приблизительно
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Wire Snark
Наверно можно сделать с контролируемой точностью (от числа измерений)? На практике наверно достаточно, но минус - большое кол-во измерений
Если шум нормально распределен, то на практике достаточно небольшого кол-ва измерений

https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Rinat Shigapov
Если шум нормально распределен, то на практике достаточно небольшого кол-ва измерений

https://habrastorage.org/webt/kk/yw/cv/kkywcvxe2mo141hjofwmnbu8nzq.png
Ну, в жизни ситуация сложнее - величина вообще случайный процесс, с не особо известными свойствами. При этом оценки границ приемлемы грубые, но вот нарушение консенсуса (т.е. отличие оценок у сторон) - гораздо хуже, чем низкое качество этих оценок...
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Можно учитывать дисперсию оценок в использующей эти данные системе
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
В первый раз слышу о консенсусе в контексте случайных величин
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Расскажу, как используется у меня. Алиса и Боб выбирают длительность временнОго слота для коммуникации друг с другом. Они измеряют время распространения сигнала. Размер слота должен быть тем больше, чем больше это время. Если они выберут разный размер слота, то будет происходить рассинхронизация. При этом Алиса и Боб сами движутся относительно друг друга по неизвестной траектории (в самолетах находятся, например). Ну вот собственно один из подходов - иметь консенсус оценки времени распространения сигнала на какой-то период времени. Другой подход - видимо подкручивать синхронизацию слотов с каждым пришедшим сигналом...
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Можно вместо фиксированных слотов иметь таймаут для текущего процесса коммуникации. После него любой из участников может начать договариваться о новых параметрах.
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Rinat Shigapov
Можно вместо фиксированных слотов иметь таймаут для текущего процесса коммуникации. После него любой из участников может начать договариваться о новых параметрах.
Это так и будет делаться плюс-минус. Вопрос в том, как именно договариваться. Можно каждому из них передать другому своё значение, взять среднее к примеру - и отложить полуинтервал (грубую оценку изменения среднего случайного процесса - например, по максимальной относительной скорости, за время таймаута) по краям. Ну а можно передать 1 бит и получить результат не хуже)
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Wire Snark
Расскажу, как используется у меня. Алиса и Боб выбирают длительность временнОго слота для коммуникации друг с другом. Они измеряют время распространения сигнала. Размер слота должен быть тем больше, чем больше это время. Если они выберут разный размер слота, то будет происходить рассинхронизация. При этом Алиса и Боб сами движутся относительно друг друга по неизвестной траектории (в самолетах находятся, например). Ну вот собственно один из подходов - иметь консенсус оценки времени распространения сигнала на какой-то период времени. Другой подход - видимо подкручивать синхронизацию слотов с каждым пришедшим сигналом...
Канал может быть несимметричным, зачем договариваться? Каждый оценивает индивидуально.
источник

WS

Wire Snark in Scalability Camp — чат про распределенные системы (и про HPC)
Rinat Shigapov
Канал может быть несимметричным, зачем договариваться? Каждый оценивает индивидуально.
Если они ничего не знают о стратегии поведения другого, то очень трудно сделать эффективные алгоритмы поиска (конкретно у меня здесь всё отягощено направленностью приемопередатчиков)
источник

RS

Rinat Shigapov in Scalability Camp — чат про распределенные системы (и про HPC)
Поиска чего?
источник