Самый простой алгоритм голосования / синхронизации

Question

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

Один человек, говорящий «я делаю это», недостаточно хорош, поскольку два человека могут сказать это одновременно.

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

Есть что-то попроще?

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

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

лотерея.

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

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

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

Answer 4

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

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

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

Выборы.

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

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

Answer 5

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

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

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

Answer 6

Это реализация прототипа 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;
    }
}

Answer 7

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

Ключевые принципы:

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

Алгоритм:

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.

Answer 8

ОК, поскольку в комнате настоящие люди, ответ становится легким, и это общее решение.

Каменные ножницы.

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

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

Answer 9

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