衝突回避
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/21 04:20 UTC 版)
「食事する暗号学者の問題」の記事における「衝突回避」の解説
同時に二人以上がメッセージを発信した場合、複数のメッセージがまじりあって排他的論理和が結果として得られる。これを衝突と呼ぶ。チャウムは、2つの衝突を回避する方法を示している(2.2節)。 1つは、メッセージの発信者が衝突を検知したら、無作為な時間だけ待ってから再送するという方法(CSMA/CD)である。 もう1つは、通信枠の予約(slot reservation)を使った回避方法である。この場合、mビットを1ブロックとしてまとめて送信するCD-netを使う。まず、情報発信する参加者は1からmの間の数iを無作為に選び、i番目のビットのみが1で、それ以外が0であるようなmビットのビット列(0 0 ... 1 ... 0 0)を決める。そして、最初のブロックの送信時には、この(0 0 ... 1 ... 0 0)を送信する。最初のブロックで衝突が起こらないことを確認したならば、次のブロックで、ブロックのi番目のビットに自分の送りたいメッセージを埋め込んで発信する。（それ以外のビットは0とする。）このようにすれば、同時に複数人が、異なるスロットを使ってメッセージを発信することができる。ただし、誕生日のパラドックスがあるため、衝突確率を一定以下に保つためには、ブロックのサイズmを参加者数の自乗に比例させる必要がある(2.5節)。
※この「衝突回避」の解説は、「食事する暗号学者の問題」の解説の一部です。
「衝突回避」を含む「食事する暗号学者の問題」の記事については、「食事する暗号学者の問題」の概要を参照ください。
ウィキペディア小見出し辞書の「衝突回避」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 衝突回避のページへのリンク
