衝突回避とは? わかりやすく解説

衝突回避

出典: フリー百科事典『ウィキペディア(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節)。

※この「衝突回避」の解説は、「食事する暗号学者の問題」の解説の一部です。
「衝突回避」を含む「食事する暗号学者の問題」の記事については、「食事する暗号学者の問題」の概要を参照ください。

ウィキペディア小見出し辞書の「衝突回避」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「衝突回避」の関連用語

衝突回避のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



衝突回避のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの食事する暗号学者の問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS