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

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

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

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

В большинстве языков есть команда атомарного увеличения. Инициализируйте переменную равным 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;
    }
}

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

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

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

Алгоритм:

1. если вы услышите "Готово!" в любой момент, даже во время ожидания, перезапустить
2. подождите случайное количество времени (от 30 м до 1 ч 30 м)
3. ждать постоянное предопределенное количество времени (один цикл, 24 часа)
4. if there's a task to be done
   1. say "I'm alive!"
   2. подождите 5 секунд (при условии, что задача всегда выполняется менее чем за 5 секунд!)
   3. if you hear "I'm alive!" during that time
      1. repeat "I'm alive!"
      2. перейти 2
   4. else (if you don't hear anything)
      1. do the task
      2. сказать "Готово!"
5. начать сначала

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

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

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

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

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