HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

サンタクロースのパズルを解く

Solving Santa Claus Puzzle (wyounas.github.io)

6 pointsby simplegeek1 コメント

要約

この記事では、サンタクロースのパズルという並行処理の問題を、モデルチェッカーを用いて検証する方法を解説しています。筆者は、単純に見えるこの問題に潜む落とし穴を明らかにするため、意図的に誤ったモデルを3つ作成し、それぞれの失敗シナリオを分析しています。最終的に、Promela言語とSPINモデルチェッカーを用いて、制約を満たす正しいモデルを提示しています。

全文翻訳

モデルチェッカーでサンタクロースの並行処理パズルを解く方法

2026年1月10日

本を読むとき、私はしばしば同じ著者の他の作品を探します。Ben-Ari の本を読んでいたとき、彼の他の著作を探したところ、サンタクロースの並行処理パズルに関する論文1に出くわしました。パズルは次のように述べられています。

サンタクロースは北極で眠っており、9頭のトナカイすべて、または10人のエルフのうち3人のグループに起こされるまで目を覚ましません。彼は2つの不可分なアクションのいずれかを行います。

  • トナカイのグループに起こされた場合、サンタはそれらをそりに繋ぎ、おもちゃを届け、最後にトナカイを解放し、彼らは休暇に入ります。
  • エルフのグループに起こされた場合、サンタは彼らをオフィスに案内し、おもちゃの研究開発について相談し、最後に彼らを送り出し、彼らは仕事に戻って玩具を製造します。

待機中のトナカイのグループは、待機中のエルフのグループよりも先にサンタによって対応されなければなりません。サンタの時間は非常に貴重であるため、トナカイまたはエルフをグループに編成することはサンタが行ってはなりません。

このパズルは、複数のプロセスが調整する必要がある場合に発生する同期の課題を捉えています。私はモデルチェッカーを使用してその正しさを検証したいと思いました。これは簡単な問題だと予想していました。驚いたのは、間違いを犯すのがいかに簡単かということです。

また、解決策へのアプローチも異なりました。正しいモデルを書く前に、誤った設計がどのようなものになるかを探る時間を費やしました。失敗は教訓的だと考えています。なぜなら、それらは安全でない仮定を露呈し、正しい解決策が何を防止しなければならないかを明確にするからです。学習演習として、それぞれ異なる失敗シナリオを再現する3つの小さなモデルを作成し、正しさのプロパティを使用してバグを検出しました。これらの失敗について少し見ていきます。その後、正しいモデルを提示し、モデルチェッカーで検証します。

この分析を実行するために、SPINモデルチェッカーを使用し、モデルをSPINの仕様言語であるPromelaで記述しました。

自然な疑問は、PythonやGoでソリューションを単純に記述するのではなく、なぜモデルチェッカーを使用するのかということです。答えはカバレッジです。モデルチェッカーは、テストや実験では見落とされる可能性のあるインターリーブを探索し、正しさを証明するか、反例を生成します。

パズルの3つの重要な制約を見てみましょう。

  • サンタは自分でグループを編成してはならない。
  • トナカイとエルフの両方が待機している場合、サンタはまずトナカイに対応しなければならない(クリスマスの配達は重要です)。
  • サンタがグループに対応するとき、グループ全体が一緒に参加しなければなりません。つまり、配達には正確に9頭のトナカイ、または相談には正確に3人のエルフが必要です。例えば、サンタは7頭のトナカイで配達したり、2人のエルフと相談したりすることはできません。

最初は、問題は単純に見えます。9頭のトナカイまたは3人のエルフが到着するまで待ち、サンタを起こし、作業を行い、繰り返します。数個のカウンターやロックで十分だと考える誘惑に駆られます。難しさはインターリーブにあります。ステップバイステップで推論すると正しく見えるソリューションも、操作が予期しない方法でインターリーブされると失敗する可能性があります。

ここで、パズルを誤って解決する3つの失敗シナリオを検討します。

  • サンタが9頭未満のトナカイしか準備できていないのに、おもちゃを配達してしまう。
  • 微妙なインターリーブの下で、サンタは現実世界では不可能なことを行うことになります。つまり、おもちゃを配達しながらエルフと同時に相談することです。
  • サンタは、9頭のトナカイがすでに待機しており準備ができているにもかかわらず、エルフと相談することを選択します。

次に、これらの各失敗シナリオを見て、すべてのパズル制約を満たすソリューションに向けて作業します。その前に、Promelaで必要となる概念を簡単に紹介します。チャネル、オプション、ガードです。

プロセス間で通信するために、Promelaではチャネルを使用します。チャネルは、送信と受信の2つの操作をサポートするデータ型です。チャネルは、指定された型のメッセージを送信者から受信者に転送します。

SPINは2種類のチャネルをサポートします。レンデブーチャネルとバッファ付きチャネルです。レンデブーチャネルでは、送信と受信が同期します。つまり、受信者が準備できるまで送信者はブロックされ(逆も同様)、転送はアトミックなハンドシェイクとして発生します。バッファ付きチャネルは、まだ受信するプロセスが準備できていない場合でも、一時的にメッセージを保持できます。バッファ付きチャネルは、送信者が受信者より先に進むことを可能にし、レンデブーチャネルはそれらを一緒に動くことを強制します。

送信操作は、チャネル変数、感嘆符(!)、およびチャネルのメッセージ型と一致する必要がある式を順番に並べたもので構成されます。対照的に、受信操作は、チャネル変数、疑問符(?)、およびメッセージを受信する変数を順番に並べたもので構成されます。

例えば、byte 型のメッセージを転送する request という名前のレンデブーチャネルを次のように宣言できます(レンデブーチャネルは容量0です。[0] 構文で示されます)。

chan request = [0] of { byte };

このチャネルにデータを送信するには、次のようにします。

request ! 1

受信するには、次のようにします。

byte client;
request ? client

次に、オプションとガードについて少し説明します。Promelaのオプションは、コードで分岐を行うために使用できます。例えば、Promelaのif文は次のように記述できます。

if
:: (a < 50) -> printf("a < 50\n");
:: (a > 50) -> printf("a > 50\n");
fi

:: で始まる各行はオプションです。オプションは、ガードとアクションで構成されます。ガードは矢印(->)の前のブール式です。ガードが真と評価された場合、オプションは有効になります。

if文に到達したとき:

  • ちょうど1つのオプションが有効な場合、Promelaはそのオプションを選択します。
  • 複数のオプションが有効な場合、SPINはいずれかを選択できます(非決定的)。
  • オプションが有効でない場合、プロセスはその if でブロックされます。

ここで、サンタが9頭未満のトナカイしか準備できていないのに、おもちゃを配達してしまう最初の失敗シナリオを見てみましょう。失敗モデルでは、状態空間を小さく保つために、エルフの数を(例えば3人に)減らすことがあります。失敗のメカニズムは同じです。

以下は、最初の失敗シナリオをシミュレートするモデルからのコード抜粋です。

#define NUM_REINDEER 9
#define NUM_ELVES 3

// buffered channels
chan harnessed = [NUM_REINDEER] of { bit };
chan done_consulting = [NUM_ELVES] of { bit };

// Some code omitted for brevity

active [NUM_REINDEER] proctype Reindeer() 
{
    do
    ::
        r_arrive ! 1;
        harnessed ? 1;
        actually_harnessed++;
        actually_harnessed--;
    od
}

active proctype Santa()
{
    byte i = 0;
    byte e = 0;
    byte j;
    
    do
    :: (i < NUM_REINDEER) ->
        r_arrive ? 1;
        i++;
        if
        :: (i == NUM_REINDEER) -> reindeer_ready = true
        :: else -> skip
        fi
        
    
    :: (i == NUM_REINDEER) ->
        
        for (j : 1 .. NUM_REINDEER) {
            harnessed ! 1;
        }
        
        delivering = true;
        /*
            simulating delivering toys
        */
        delivering = false;
        reindeer_ready = false;
        i = 0;
    
    // Some code omitted for brevity - complete code linked below
}

// Correctness property 
ltl safety { [] (delivering -> actually_harnessed == NUM_REINDEER) }

このPromelaモデルは、サンタの問題の小さな「実行可能な仕様」です。完全なモデルと実行手順はリポジトリ2で入手できます。簡単にするために、主にサンタとトナカイのやり取りに焦点を当てます。エルフは、全体的な構造を類似させるためにのみ存在します。

active [N] proctype P(){…} という構文は、SPINに初期状態のプロセスPのN個の同時コピーを開始するように指示します。ここでは、9つのトナカイプロセス、3つのエルフプロセス、および1つのサンタプロセスが得られます。各トナカイは、r_arrive チャネルでレンデブー送信をループします。そのため、サンタが受信するまでブロックされ、その後 harnessed チャネルでハーネスメッセージを待ちます。サンタはループして、トナカイの到着を数えます。9頭すべてのトナカイが到着すると、彼はそれらを harnessed チャネルに9つのメッセージを送信して「ハーネス」し、おもちゃの配達を表すために delivering = true を短時間設定します。

[画像: Santa claus first buggy sequence]

バグは、harnessed がバッファ付きチャネルであるため、サンタは9つのハーネスメッセージすべてをエンキューしてすぐに続行できることです。トナカイが実際にそれらを受信したことを強制するものは何もありません。これは、サンタがグループ全体が一緒に参加して配達しなければならないというパズルの制約に違反します。この実装がパズルの制約を尊重しているかどうかを確認するために、線形時相論理(LTL)で正しさのプロパティを記述します。

簡単に言うと、LTLプロパティは、システムが実行されるにつれて時間とともに保持されなければならないルールを記述します。モデルチェッカーは、すべての到達可能な状態を列挙することによってシステムのステートスペースを構築します。各状態は、すべての変数とコード内の各プロセスの現在の位置のスナップショットであり、すべての可能なインターリーブの下で実行されます。このステートスペースをグラフとして考えることができます。各ノードは状態であり、各エッジはプログラムがプロセスをインターリーブしながら取ることができる単一のステップを表します。LTLプロパティは、このステートスペース全体に対してチェックされます。「常に」保持されるべき条件と言うとき、それはSPINが探索するすべての到達可能な状態において真であることを意味します。

LTLプロパティ ltl safety { [] (delivering -> actually_harnessed == NUM_REINDEER) } はその要件をエンコードします。ここでは [] は「常に」を意味するため、プロパティはすべての到達可能な状態において、delivering が真であれば、9頭すべてのトナカイがすでにハーネスされている必要があると述べています。

SPINがこのプロパティをチェックすると、サンタが9頭すべてのトナカイがハーネス信号を受信する前に delivering = true を設定する実行が見つかります。言い換えれば、サンタは一部のトナカイがまだハーネスされていない間に玩具の配達を開始します。プロパティは失敗し、SPINはこの実行がどのように発生するかを正確に示す反例を生成します。コードは、このモデルと、それを実行し、反例を含むトレースを表示するための手順を示しています。

次に、サンタが玩具を配達しながらエルフと同時に相談するという、一見不可能なことを行う可能性のある2番目の失敗シナリオを見てみましょう。この障害をシミュレートする完全なモデルはここに3あります。抜粋を以下に示します。

このバグを簡単にトリガーできるように、私は愚かなことをしました。サンタを2つに分割しました。1つはおもちゃの配達を担当し、もう1つは相談を担当します。各プロセスは独立して、それぞれのグループが形成されるのを待ち、対応するフラグ(delivering または consulting)を設定して作業が開始されたことを示します。これらの2つのプロセスは並行して実行され、相互排他性を共有しないため、両方のフラグが同時に真になるインターリーブが存在します。

[画像: Santa claus second buggy sequence]

コードはパズルのコア制約に違反しています。サンタは一度に1つの不可分なアクションしか実行できません。サンタが決して同時に配達も相談もしないことをアサートする assert ステートメントを追加することにより、SPINは、特定のインターリーブの下でこの不可能な状況がどのように発生するかを示す具体的な反例トレースを見つけることができます。

active proctype SantaConsulting()
{

 byte e = 0;
    byte j;
    end:
    do
    
    :: (e < NUM_ELVES) ->
        e_arrive ? 1;
        e++;
    :: (e == NUM_ELVES) ->

        consulting = true;
        
        assert !(consulting && delivering);
        // We release elves here
        consulting = false;
        e = 0;
    od 

}
active proctype SantaToyDelivery()
{
    byte i = 0;
    byte j=0;
    end:
    do
    :: (i < NUM_REINDEER) ->
        r_arrive ? 1;
        i++;
        
    :: (i == NUM_REINDEER) ->
        
        delivering = true;
        // We release the reindeer here
        delivering = false;
        
        i = 0;
        
    
    od
}

// correctness property

ltl reindeer_precedence {
    [] ( (r_count == NUM_REINDEER) -> ( (!consulting) U delivering ) )
}

次に、9頭のトナカイの完全なグループがすでに待機している場合でも、サンタがエルフと相談してしまう可能性のある、最後の失敗シナリオを調べます。この障害をシミュレートする完全なモデルはここに4あります。構造的には、前のモデルと非常に似ています。

このバージョンでは、サンタの相談ロジックは、完全なトナカイグループが準備できているかどうかを確認する前に続行します。その結果、9頭のトナカイすべてが到着し、3人のエルフのグループも準備ができているインターリーブが存在しますが、サンタはエルフとの相談を開始します。これはパズルの中心的な制約に違反します。両方のグループが待機している場合、トナカイはエルフよりも先に処理されなければなりません。

[画像: Santa claus third buggy sequence]

これまでのツールだけでは検出が難しいことがわかり、次にLTLで表現される優先順位プロパティを発見しました。非公式には、このプロパティは次のように述べています。9頭のトナカイの完全なグループが準備できたら、配達が開始される前に相談が発生してはなりません。これは、LTLの「until」演算子(「U」と表記)を使用してエンコードします。これにより、配達が発生するまで相談は偽のままでなければならないと述べることができます。SPINがこのプロパティをチェックすると、サンタが最初に相談する反例が見つかり、実装が必要な優先順位ルールに違反していることが示されます。

上記のすべてのモデルが破るもう1つのルールがあります。サンタは自分で編成作業を行ってはならないということです。上記のモデルでは、サンタは直接到着を数え、トナカイとエルフを解放しています。これにより、グループ形成と作業自体を混同しやすくなります。

修正策は、サンタに助けを与えることです。Ben-Ari1に従って、部屋を導入します。部屋の唯一の仕事は到着を収集し、完全なグループが準備できたときにサンタに知らせることです。サンタはもはや到着を数えず、単に「グループ準備完了」信号を待ち、作業を行います。

正しいモデルを構築するために、トナカイ用の部屋とエルフ用の部屋を1つずつ使用します。主なアイデアは、編成(部屋が処理)とサービス提供を分離することです。次に、イベントの変更されたシーケンスを見てみましょう。

[画像: Santa claus sequence]

9頭のトナカイのグループがトナカイ部屋に到着すると、部屋はサンタに信号を送ります。これが起こっている間、2人のエルフも到着します。サンタはおもちゃを配達し、トナカイを解放します。後で3人目のエルフが到着すると、エルフ部屋はサンタに信号を送ります。サンタはお elf と相談し、それから彼らを解放します。

この動作をSPINでモデル化するために、各コンポーネントは個別のプロセスとして表されます。SPINはこれらのプロセスのすべての可能なインターリーブを探索し、指定された正しさのプロパティがすべての到達可能な状態で保持されることをチェックします。

システムを次のプロセスでモデル化します。

トナカイ: 9つのトナカイプロセスを並行して実行します。各トナカイはトナカイ部屋に到着し、解放されるまでそこに待機します。
エルフ: 10個のエルフプロセスも並行して実行します。各エルフはエルフ部屋に到着し、解放されるまでそこに待機します。
トナカイ部屋: このプロセスの単一インスタンスを実行し、トナカイ部屋をシミュレートします。到着したトナカイを収集し、9頭の完全なグループが形成されたときにサンタに信号を送り、サンタが配達を完了した後、グループを解放します。
エルフ部屋: 同様に、このプロセスの単一インスタンスを実行してエルフ部屋をシミュレートします。到着したエルフを収集し、3人のグループが形成されたときにサンタに信号を送り、サンタが相談を完了した後、グループを解放します。
サンタ: 単一のサンタプロセスは、部屋からの「グループ準備完了」信号を待ちます。トナカイをエルフよりも優先して処理し、作業が完了したときに適切な部屋に通知します。

プロセス間で通信するために、次のレンデブーチャネルを使用します。それぞれがbit型のメッセージを転送します。

chan r_arrive  = [0] of { bit };
chan e_arrive  = [0] of { bit };
chan r_release = [0] of { bit };
chan e_release = [0] of { bit };
chan r_done    = [0] of { bit };
chan e_done    = [0] of { bit };

トナカイのデータを転送するチャネル名にはrを、エルフのデータにはeを付加します。以下は、主要なチャネルの役割です。

  • r_arrive / e_arrive: これらのレンデブーチャネルは、トナカイとエルフがそれぞれの部屋に入る方法を表します。トナカイはr_arriveで送信することによって部屋に入ろうとします。チャネルはレンデブーなので、部屋がそれを受け入れる準備ができるまでブロックされます。部屋がいっぱいになると、到着の受信を停止するため、追加のトナカイ(またはエルフ)は部屋が再オープンするまでブロックされます。
  • r_release / e_release: これらのチャネルは、部屋が完全なグループを解放する方法を表します。サンタが終了した後、部屋はグループメンバーごとにr_release(またはe_release)で送信します。チャネルはレンデブーであるため、部屋は「先行して解放」することはできません。各送信は、実際の待機中のトナカイ(またはエルフ)と同期します。
  • r_done / e_done: これらのチャネルは、サンタの「完了しました」という通知を部屋に表します。部屋は解放する前にこの信号を待ちます。例えば、サンタがおもちゃの配達を終えた後、r_doneで送信します。これがないと、部屋はトナカイを解放しても安全な時期を知ることができません。

次に、トナカイとエルフのプロセスを見てみましょう。これらは非常に似ています。まずトナカイプロセスから始めます。

active [9] proctype Reindeer()
{
    do
    :: r_arrive ! 1;     // enter the room
       r_release ? 1;    // wait to be released
    od
}

active [9] キーワードのため、SPINは初期システム状態で9つのトナカイプロセスを並行して実行します。r_arrive ! 1 ステートメントは、トナカイがr_arriveチャネルで送信することによってトナカイ部屋に入ろうとしていることを示します。r_arriveはレンデブーチャネルなので、トナカイは部屋がそれを受け入れる準備ができるまでブロックされます。部屋に入った後、トナカイはr_releaseチャネルでブロックすることによって解放を待ちます。

エルフプロセスのコードも同様です。

active [10] proctype Elf()
{
    do 
    :: e_arrive ! 1;
       e_release ? 1;
    od
}

部屋は編成と同期が行われる場所です。次にトナカイ部屋を見てみましょう。

active proctype RoomReindeer()
{
    byte waiting = 0;
    byte i = 0;

    do
    /* Collect reindeer until the group is complete (entrance open iff waiting < 9) */
    :: (waiting < NUM_REINDEER) ->
        atomic {
            r_arrive ? 1;
            waiting++;
            reindeer_waiting = waiting;
            if
            :: (waiting == NUM_REINDEER) -> r_request = 1
            :: else -> skip
            fi
        }

    /* Group complete: wait for Santa, then release all 9 and reset */
    :: (waiting == NUM_REINDEER) ->
        atomic { r_done ? 1; i = 0; }

        do
        :: (i < NUM_REINDEER) ->
            atomic { r_release ! 1; i++; }
        :: else -> break
        od;

        atomic {
            waiting = 0;
            reindeer_waiting = 0;
        }
    od
}

繰り返し構造には2つの代替手段があります。waitingがNUM_REINDEER未満の場合、部屋は到着したトナカイを受け入れ、カウンターを増やします。到着がグループを完成させた場合、部屋はr_request = 1を設定してサンタに通知します。

waitingがNUM_REINDEERに等しい場合、部屋は到着の受付を停止し、サンタがr_doneで完了をメッセージングするのを待ちます。このメッセージを受信した後、部屋はr_releaseを介してトナカイを解放し、状態をリセットして新しい到着を受け入れます。

エルフ部屋のロジックは同じパターンに従っており、簡潔さのために省略されています。

サンタプロセスは2種類のアクションをモデル化します。トナカイとの玩具配達とエルフとの相談です。そのメインループには、2つのガード付き代替手段が含まれています。

最初の代替手段では、r_requestによってガードされ、サンタは玩具配達アクションを実行し、r_requestをクリアし、r_doneで送信することによってトナカイ部屋に完了を通知します。対応するコードを以下に示します。

:: r_request ->
        atomic {
            delivering = true;
            r_request = 0;   /* claim the request */
        }

        /* Deliver toys (abstracted). */
        delivering = false;

        /* Notify the Room that delivery is complete; it can release the reindeer. */
        r_done ! 1;

2番目の代替手段は、!r_request && e_requestによってガードされています。このガードは優先順位ルールを強制します。サンタは、トナカイグループが待機しておらず、3人のエルフのグループが形成された場合にのみエルフと相談します。サンタはその後相談を実行し、e_doneで送信することによってエルフ部屋に完了を通知します。

:: (!r_request && e_request) ->
        atomic {
            consulting = true;
            e_request = 0;   /* claim the request */
        }

        /* Consult (abstracted). */
        consulting = false;

        /* Notify the Room that consultation is complete; it can release the elves. */
        e_done ! 1;

モデルが正しいことをどのように検証しますか?

2種類の正しさのプロパティを指定できます。安全性プロパティとライブネスプロパティです。それぞれを順に見ていきましょう。

安全性プロパティは、悪いことが決して起こらないことを主張します。このモデルでは3つの安全性プロパティを使用します。まず、サンタが常に正確に9頭のトナカイで玩具を配達することを保証します。つまり、部屋に9頭の完全なトナカイグループが存在しなければなりません。これを次のように指定します。

ltl safety_delivery { [] (delivering -> reindeer_waiting == 9) }

このプロパティは、常に、サンタが玩具を配達している場合、reindeer_waiting変数は9に等しくなければならないと述べています。

次に、サンタが常に正確に3人のエルフと相談することを保証します。これを次のように指定します。

ltl safety_consult { [] (consulting -> elf_waiting == 3) }

最後に、サンタが決して玩具を配達したり相談したりしないことを保証するための相互排他性プロパティを指定します。

ltl mutex_santa { [] !(delivering && consulting) }

なぜdeliveringとconsulting変数が短時間だけtrueに設定されているのか疑問に思うかもしれません。このモデルでは、配達と相談は詳細にはシミュレートされておらず、単一の抽象ステップとして表されています。ブールフラグは、サンタが配達または相談を開始した瞬間を示すだけなので、不正な重複を検出してチェックできます。それらの目的は時間の経過をモデル化することではなく、モデルチェッカーが不正な重複を可視化できるようにすることです。

次にライブネスプロパティに目を向けます。ライブネスプロパティは、良いことが最終的に起こることを主張します。指定するライブネスプロパティは次のとおりです。常に、リクエストが保留中であれば、最終的にサンタは玩具を配達するか、エルフと相談するかのいずれかを行います。これは、リクエストが永遠に保留されたままサンタが作業を行わない実行を排除します。

このプロパティを次のように指定します([] は「常に」、<> は「最終的に」を表します)。

ltl live_progress { [] ((r_request || e_request) -> <> (delivering || consulting))
}

ライブネスプロパティの重要な役割の1つは、空虚な正しさを回避することです。例えば、[] (delivering -> reindeer_waiting == 9) のような安全性プロパティは、delivering が決して真にならない場合でも保持される可能性があります(「->」は含意であり、論理学では含意「AならばB」は、Bが真か偽かに関わらず、Aが偽である場合に常に真と見なされます)。対照的に、このライブネスプロパティは、リクエストが保留されたままでサンタが配達または相談ステップを一度も実行しない実行を排除します。つまり、リクエストが保留中である限り、いつかサービスステップが発生することを確認します。

SPINでモデルを実行すると、すべての安全性およびライブネスプロパティがパスします。個別の実行では、SPINはsafety_deliveryとmutex_santaをチェックしながら約500万の状態を探索し、ライブネスプロパティをチェックしながら約700万の状態を探索し、反例は見つかりませんでした。同様の方法で、優先順位プロパティを指定してチェックすることもできます。

モデルとそれを実行するための手順は、リポジトリ5で入手できます。

これらの要素がどのように組み合わさるかを見るために、実行例を見てみましょう。

[画像: Santa claus sequence]

時間は上から下へ流れます。9頭目のトナカイが到着すると、トナカイ部屋はr_requestを設定し、さらなる到着のために部屋を閉じます。r_requestが真のままである間、エルフのブランチはガード!r_requestによって無効になっているため、サンタはエルフが到着してもトナカイを処理します。

サンタがr_doneで完了を信号した後、部屋はレンデブーを介して9頭すべてのトナカイを解放します。後で3人のエルフのグループが形成されると、モデルはe_requestを設定します。r_requestは現在偽なので、サンタはエルフを処理します。

このモデルをコンピュータプログラムに変換するために、Goで実装してみようと思いました。私はGoをあまりよく知らないので、AIと協力してPromelaデザインをシンプルでidiomaticなGo実装に翻訳しました。モデルに忠実であるためにコード6を確認しましたが、間違いがあれば私の責任です。

これは人間が書いたものであり、この投稿に誤りが含まれている可能性があることに注意してください。何かおかしな点に気づいたら、修正していただけると幸いです。お気軽にメールを送信してください。

Endnotes:

  1. Ben-Ari, M. How to Solve the Santa Claus Problem. Concurrency: Practice and Experience, 1998. ↩ ↩2

  2. 最初の失敗シナリオのソースコードへのリンク: https://github.com/wyounas/model-checking/blob/main/puzzles/santa_claus/santa_bug_deliver_without_full_group.pml ↩

  3. 2番目の失敗シナリオのソースコードへのリンク: https://github.com/wyounas/model-checking/blob/main/puzzles/santa_claus/santa_bug_deliver_and_consult_simultaneously.pml ↩

  4. 3番目の失敗シナリオのソースコードへのリンク: https://github.com/wyounas/model-checking/blob/main/puzzles/santa_claus/santa_bug_consult_before_delivery.pml ↩

  5. 部屋ベースのソリューションのソースコードへのリンク: https://github.com/wyounas/model-checking/blob/main/puzzles/santa_claus/santa_claus.pml ↩

  6. 部屋ベースのソリューションのGo実装へのリンク: https://github.com/wyounas/model-checking/blob/main/puzzles/santa_claus/santa_claus.go ↩


← すべての記事に戻る