Пусть класс BPNC (комбинация и ) будет параллельным алгоритмом глубины логарифма с ограниченной вероятностью ошибки и доступом к случайному источнику (я не уверен, что у него другое имя). Определите класс DBPNC аналогичным образом, за исключением того, что все процессы имеют произвольный доступ к случайному потоку битов, зафиксированному при запуске алгоритма.Н С
Другими словами, каждый процесс в BPNC имеет доступ к отдельному случайному источнику, в то время как алгоритмы DBPNC имеют общий генератор режимов случайных счетчиков.
Знаем ли мы, что BPNC = DBPNC?
Ответы:
Они одинаковы: BPNC = DBPNC.
Скажем, машина BPNC задается в качестве входной программы DBPNC для моделирования. Выполните программу в шаге блокировки. Сначала предположим, что индексы между различными шагами различны, так что нам не нужно запоминать старые случайные биты. На каждом этапе каждый процессор запрашивает случайный бит по определенному индексу в общем потоке. Вычислить и распределить случайные биты следующим образом:
Чтобы процессоры могли запрашивать старые индексы, каждый процессор должен помнить (результаты) всех предыдущих периодов сортировки. Чтобы проверить, произошли ли новые запрошенные индексы в данную предыдущую эпоху, выполните
источник