Простейший из возможных алгоритмов голосования/ синхронизации

StackOverflow https://stackoverflow.com/questions/991958

Вопрос

Какой простейший алгоритм мог бы использовать один или несколько человек, чтобы решить, кто из них должен выполнить какую-то задачу?Есть одна задача, которую нужно выполнить только один раз, и одному или нескольким людям.Люди могут разговаривать, то есть отправлять сообщения друг другу.Общение должно быть минимальным, и все люди должны использовать один и тот же алгоритм.

Одного человека, говорящего "Я делаю это", недостаточно, поскольку два человека могут сказать это одновременно.

Самое простое, что приходит мне в голову, - это то, что каждый человек произносит цифру и немного ждет.Если кто-то ответит за это время, человек с меньшим числом "выигрывает" и выполняет задание.Если никто не отвечает, человек говорит, что он это делает, и делает это.Когда она говорит, что делает это, все остальные отступают.Этого должно быть достаточно, чтобы два человека не выполняли задание одновременно (поскольку существует период ожидания / рукопожатия), но может потребоваться "второй раунд", если оба человека назовут одно и то же число.

Есть ли что-нибудь попроще?

Для тех, кому интересно, я пытаюсь синхронизировать несколько копий SecondLife LSL script, чтобы сделать что-то только один раз.

Это было полезно?

Решение 9

В конце концов, я пришел к решению, которое работает довольно хорошо.Я начал думать - почему бы не попытаться свести к минимуму столкновения (то есть попытаться привлечь только одного добровольца) вместо того, чтобы договариваться, кто выполняет задание?

Ключевыми принципами являются:

  • если доброволец - единственный доброволец, то он тот, кто это делает
  • если два (или более) человека хотят выполнить задачу одновременно, заставьте обоих подождать случайный промежуток времени, чтобы свести к минимуму столкновения

Алгоритм таков:

  1. если вы услышите "Готово!" в любой момент, даже во время ожидания, перезапустите
  2. подождите произвольное количество времени (от 30 до 1 часа 30 минут).
  3. ожидание в течение постоянного заданного промежутка времени (один цикл, 24 часа)
  4. если есть задача, которую нужно выполнить
    1. скажи: "Я жив!"
    2. подождите 5 секунд (при условии, что задача всегда выполняется менее чем за 5 секунд!)
    3. если вы услышите "Я жив!" в течение этого времени
      1. повторяйте: "Я жив!"
      2. переход 2
    4. остальное (если вы ничего не слышите)
      1. выполняйте задание
      2. скажи: "Готово!"
  5. перезапуск

По сути, это означает, что существует грамматика двух возможных сигналов / сообщений ("Я жив!" и "Готово!").

Допустим, n - это количество клиентов / человек.В идеальных условиях это также означает 2 сообщения за цикл при отсутствии коллизий для любого n.Когда происходят коллизии, это означает +2 сообщения за цикл на коллизию.Шансы на это невелики, но в худшем случае будет n сообщений плюс задача не будет выполнена в этом цикле.В худшем случае, когда задача действительно выполняется, появляется n + 1 сообщений.

Возможные упрощения

Поскольку я могу позволить себе пропустить цикл (задача не выполняется в этом цикле), но я не могу позволить себе выполнить другую задачу до следующего цикла, я заставляю всех ждать начала одного цикла.Если у вас нет требования "одна задача за цикл", вы можете пропустить шаг 3.По-прежнему нет гарантии, что задача будет выполнена за один цикл, но с большими значениями на шаге 2, малыми значениями на шаге 4.2 и небольшим количеством клиентов / людей у нас были бы довольно хорошие шансы.

Алгоритм может работать даже только с одним сигналом / сообщением.Мы могли бы пропустить шаг 1 и сказать "Я жив!" и в 4.4.2, но только в том случае, если 4.4.1 приведет к немедленному завершению проверки на шаге 4.

Другие советы

Это действительно зависит от того, какие примитивы общения у человека есть.Если есть общая память, сравнить и поменять местами это хороший и простой способ - каждый просто пытается заменить 0 на 1, и тот, кто преуспевает, выполняет задание.

Если все, что у вас есть, это отправка сообщений, возможно, вам придется реализовать Паксос протокол или что-то в этом роде.В этом случае будьте очень осторожны, чтобы доказать правильность вашего протокола, поскольку он более тонкий, чем кажется!

Редактировать:Поскольку вы говорите, что используете LSL, почему бы просто не попросить их запросить внешний сервер, используя ЛлHTTPRequest арбитражить?Если вы беспокоитесь о том, где разместить внешний сервер, вы можете использовать Механизм приложений или что-то достаточно легко.

В большинстве языков есть команда атомарного приращения.Инициализировать переменную значением 0.Все увеличивают переменную на 1.Затем поток может использовать свое личное возвращаемое значение приращения, чтобы определить, какое оно.Итак, если вам нужно выполнить только одно действие, возможно, его выполнит номер 0.

Весь порядок по-прежнему можно использовать для более сложных действий, например, когда половина ваших потоков делает одно, а половина другое и т. д.

Редактировать:вы говорите «люди», но я предполагаю, что вы имеете в виду потоки, поскольку в вашем последнем предложении говорится, что это делается с помощью сценариев.

Хорошо, это долгий путь.Возможно, это поможет сформулировать какой-то метод.

Предположения.

  • у вас есть способ общаться между машинами (экземплярами LSL)
  • у вас есть точка генерации задач, которая может публиковать задачу как задачу к выполнению во всех экземплярах

Выборы.

  • Если вы можете создать какой-то список, доступный для всех экземпляров
  • Генератор задач может создать экземпляр списка (или ввести в список запись требования).
  • Другие экземпляры обнаруживают список (или новую запись в нем)
  • Для требования существует тайм-аут, в течение которого экземпляры, желающие его получить, должны ответить.
  • экземпляры могут внести свой идентификатор в список, чтобы указать на свою заинтересованность в выполнении задачи.
  • после таймаута последним отвечает тот, кто выбран (или, в зависимости от вашей динамики, вы можете выбрать первого в списке);я предполагаю, что генератор опубликует подтверждение для этого экземпляра в это время
  • Если все экземпляры видят список, правый знает, когда выборы завершены.

Время реакции отдельных экземпляров и их доступность должны сделать вашу работу

Розыгрыш.

Каждый получает номер..это может быть номер места или номер корешка билета.

Положите цифры в шляпу, вытащите одну и попросите их встать.

Это также масштабируется, даже до огромных чисел, и работает быстрее.Слабость заключается в том, что ему требуется предварительный этап присвоения номера.

Я бы сказал, что ответ зависит от того, можете ли вы отправлять широковещательные сообщения или нет.

Если у вас есть возможность отправить широковещательную рассылку, вы просто ждете небольшой (10 мс) случайный период времени, отправляете широковещательную рассылку, ждете разумный период времени, чтобы учесть задержку в сети, а затем просите человека, отправившего самое раннее сообщение, сделать это. задание.

Если ваша сеть знает только своих соседей, вы делаете то же самое, но поэтапно;в каждом раунде вы устраняете несколько узлов, которые продолжают делать разные вещи.

На практике я советую вам использовать «самое раннее время», а не «наименьшее число» по той тривиальной причине, что быть первым должно коррелировать с более быстрой машиной/иметь хорошее сетевое соединение/холостой режим работы – это те качества, которые вам нужны. как для машины, выбранной для выполнения задачи.

Заставьте всех встать в очередь.Следующий человек в очереди получает работу.

Хорошо, поскольку в комнате находятся реальные люди, ответ становится простым, и это обычное решение.

Камень ножницы Бумага.

Все объединяются в пары и играют в RPS.Чтобы упростить задачу, разрешите по 2 и 3 игрока в группе (хотя это делает шансы не совсем равными).После каждого раунда победители объединяются в пары с победителями и повторяют действия, пока не останется один победитель.

На самом деле это прилично масштабируется!Однажды я был на дурацком ледоколе, посвященном тимбилдингу, и это сработало для большого конференц-зала, в котором собралось более 500 человек, в течение 5 минут.

Это реализация прототипа LSL (общественное достояние, хотя вам, вероятно, придется адаптировать ее для своего использования):

// user configuration parameters
integer CHANNEL = -635;

// ------------------------------------------------

// scripter configuration parameters (in seconds)
float POLL_PERIOD = 60.0;               // 1 minute
// minimum length of suspend period
float CORE_SUSPEND_PERIOD = 15.0;       // 15 seconds 
// maximum length added to core suspend period (minimum is 0)
float MAX_RANDOM_SUSPEND_PERIOD = 30.0; // 30 seconds
float LOCK_PERIOD = 5.0;                // 5 seconds

// variables
integer lock = FALSE;


// mock poll method, assumes there are always tasks
integer poll()
{
    llSay(0, "Polling for tasks...");
    return TRUE;
}

// mock work method
work()
{
    llSay(0, "*** Executing task... ***");
}

default
{
    state_entry()
    {
        llSay(0, "Entering default state.");
        lock = FALSE;
        llListen(CHANNEL, "", NULL_KEY, "");
        llSetTimerEvent(POLL_PERIOD);
    }

    timer()
    {
        if (lock)
        {
            // step 4 - do some work
            work();
            // step 5 - make everybody go into suspend state
            // to make sure run times are randomized AND not sooner
            // than POLL_PERIOD
            llRegionSay(CHANNEL, "suspend");
            lock = FALSE;
            state suspended;
        }
        else
        {
            if (poll())
            {
                // step 1 - acquire lock
                llRegionSay(CHANNEL, "lock");
                lock = TRUE;
                // step 2 - wait and listen for others
                llSetTimerEvent(LOCK_PERIOD);
            }
        }
    }

    listen(integer channel, string name, key id, string message) 
    {
        // step 3 - did someone reply?
        if (message == "lock" && lock)
        {
            // other script woke up at the same time - signal
            // that you're here and suspend until next round,
            // where there will hopefully be a winner
            llSay(0, "Collision!");
            llRegionSay(CHANNEL, "lock");
            state suspended;
        }
        else if (message == "suspend")
            state suspended;
    }
}

state suspended
{
    state_entry()
    {
        // this gives random number between 0 and MAX_RANDOM_SUSPEND_PERIOD
        float random = llFrand(MAX_RANDOM_SUSPEND_PERIOD);
        float total = CORE_SUSPEND_PERIOD + random;
        llSetTimerEvent(total);
        llSay(0, "Entering suspended state for " + (string) ((integer) total)
            + " seconds.");
    }

    timer()
    {
        state default;
    }
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top