1

一个或多个人可以用来决定他们中的谁应该执行某项任务的最简单算法是什么？有一个任务，只需要完成一次，一个或多个人。人们可以说话，也就是互相发送消息。沟通必须最少，所有人都使用完全相同的算法。

一个人说“我在做”是不够的，因为可能有两个人同时说。

我想到的最简单的事情是每个人都说一个数字然后稍等片刻。如果有人在那段时间内做出回应，则数字较低的人“获胜”并完成任务。如果没有人回应，人们会说她正在做并且做。当她说她这样做时，其他人都退缩了。这应该足以避免两个人同时执行任务（因为有等待/握手期），但如果两个人说相同的数字，则可能需要“第二轮”。

有没有更简单的？

对于那些好奇的人，我正在尝试同步多个 SecondLife LSL 脚本副本，以便只执行一次。

4

9 回答 9

2

这实际上取决于一个人拥有什么通信原语。如果有共享内存，比较和交换是一种很好、简单的方法——每个人都只是尝试用 1 替换 0，然后谁成功就完成了任务。

如果您只有消息发送，您可能需要实现Paxos协议或类似的东西。在这种情况下，要非常小心，您可以证明您的协议的正确性，因为它比看起来更微妙！

编辑：既然您说您使用的是 LSL，为什么不让他们使用LlHTTPRequest查询外部服务器进行仲裁？如果您担心在哪里托管外部服务器，您可以使用App Engine或其他很容易的东西。

于 2009-06-14T02:12:46.873 回答
1

大多数语言都有一个原子增量命令。将变量初始化为 0。每个人都将变量递增 1。然后线程可以使用它的个人增量返回值来查找它是哪一个。所以如果你只有一个动作要执行，也许数字 0 可以做到。

整个排序仍然可用于更复杂的操作，例如让一半的线程做一件事，另一半做另一件事，等等。

编辑：您说“人”，但我认为您的意思是线程，因为您的最后一句话说这是由脚本完成的。

于 2009-06-14T02:06:06.263 回答
1

好的，这是一个长镜头。也许，这将有助于制定一些方法。

假设。

  • 您可以在机器之间进行通信（LSL 实例）
  • 您有一个任务生成点，可以将任务发布为所有实例的待完成任务

选举。

  • 如果您可以创建可用于所有实例的某种列表
  • 任务生成器可以创建一个列表实例（或在列表中输入需求条目）
  • 其他实例检测到列表（或其中的新条目）
  • 要求有一个超时时间，在该要求内想要获取它的实例必须响应
  • 实例可以将他们的 id 放在列表中，以表明他们有兴趣完成任务
  • 超时后，最后一个回答是选择的（或者，根据您的动态，您可以选择列表中的第一个）；我假设生成器此时发布了对 theat 实例的接受
  • 如果所有实例都可以看到列表，则正确的人知道选举何时完成

单个实例的反应时间及其可用性应该可以完成您的工作

于 2009-06-14T02:40:40.223 回答
1

抽奖。

每个人都有一个号码。可能是座位号，也可能是票根号码。

把数字放在帽子里，拿出一个，让他们站起来。

这也可以扩展，甚至可以扩展到巨大的数字，并且速度更快。缺点是它确实需要数字分配前置步骤。

于 2009-06-14T16:03:08.530 回答
1

我会说答案取决于您是否能够发送广播消息。

如果您有发送广播的能力，您只需等待一小段（10ms）随机时间，发送广播，等待一段合理的时间以允许网络延迟，然后让最早发送消息的人做任务。

如果你的网络只知道它的邻居，你也可以做同样的事情，但要轮流进行；在每一轮中，您都会消除一些继续进行不同细化的节点。

实际上，我建议您使用“最早的时间”而不是“最小的数字”，因为第一个应该与更快的机器/具有良好的网络连接/空闲相关，这就是你想要的品质就像选择执行任务的机器一样。

于 2009-06-28T07:09:51.080 回答
0

让大家排队。排队的下一个人得到这份工作。

于 2009-06-14T01:59:12.520 回答
0

好的，因为这些是房间里的真实人物，所以答案变得很容易，这是一个常见的解决方案。

剪刀石头布。

每个人都配对并玩RPS。为方便起见，每组允许 2 和 3 名玩家（即使这使得赔率不完全相等）。在每一轮之后，获胜者与获胜者配对并重复，直到你只有一个获胜者。

这实际上可以很好地扩展！我曾经在一个愚蠢的团队建设破冰船中，这对一个有 500 多人的大型会议室在 5 分钟内起作用。

于 2009-06-14T16:00:48.520 回答
0

最后，我想出了一个效果很好的解决方案。我开始思考——为什么不尽量减少冲突（即尝试只有一名志愿者）而不是协商谁来完成任务？

关键原则是：

  • 如果志愿者是唯一的志愿者，他就是做这件事的人
  • 如果两个（或更多）人想同时做这个任务，让两个人都等待一个随机的时间，以尽量减少冲突

算法是：

  1. 如果您听到“完成！” 随时，即使在等待中，重新启动
  2. 等待随机时间（30m 到 1h 30m 之间）
  3. 等待恒定的预定义时间量（一个周期，24 小时）
  4. 如果有任务要完成
    1. 说“我还活着！”
    2. 等待 5 秒（假设任务总是在 5 秒内完成！）
    3. 如果你听到“我还活着！” 在那段时间内
      1. 重复“我还活着！”
      2. 转到 2
    4. 其他（如果你什么都没听到）
      1. 做任务
      2. 说“完成！”
  5. 重新开始

这基本上意味着有两个可能的信号/消息的语法（“我还活着！”和“完成！”）。

说n是客户/人的数量。在理想条件下，这也意味着当任何 n 都没有冲突时，每个周期有 2 条消息。当存在冲突时，这意味着每次冲突每个周期 +2 条消息。它的可能性很小，但在最坏的情况下，有 n 条消息加上任务在此循环中没有完成。在任务完成的最坏情况下，有 n+1 条消息。

可能的简化

因为我可以跳过一个循环（任务在这个循环中没有完成），但是我不能在下一个循环之前完成另一个任务，所以我让每个人在开始时等待一个循环。如果你没有“一个周期一个任务”的要求，你可以跳过步骤 3。仍然不能保证任务会在一个周期内完成，但是步骤 2 中的值大，步骤 4.2 中的值小，并且少数客户/人我们会有很好的机会。

即使只有一个信号/消息，算法也可以工作。我们可以跳过第 1 步并说“我还活着！” 在 4.4.2 中也是如此，但前提是 4.4.1 会使步骤 4 中的检查立即失败。

于 2009-06-16T22:42:13.950 回答
0

这是 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;
    }
}
于 2009-06-21T17:09:30.860 回答