伝言ゲームのアルゴリズム

1 ：02/10/21 〜 最終レス ：09/11/15

下記の条件でメンバーに漏れなく通達できるアルゴリズムで
なんかいいの無いですか？

１）メンバーは１から２５５までの任意の番号で最大６４人（重複なし）
２）一人４人ぐらいに転送で、最大４段ぐらい
３）送信先が存在するかどうかは送信エラーで確認できる
４）メッセージにIDを付け、受けたメッセージの内容が重複した場合は
　処理しなくてよい
５）メッセージに段数をつけて、次に送るときは１をひく。
　自分が４段目になったらおしまい。

P2P がらみで、相手をさがすアルゴリズムを、素数とか段数の階乗とか
を式にまぜるなど、色々考えて見たのですがいいのが思いつきません。
参考になる URL とかでもいいです。よろしくお願いします。
（一応あちこち見ましたが、重複や板違いなら申し訳ありません）

2 ：

>>1の提示する条件だと
1)
自分(メンバー場号(以下No)1)がNo2〜5に転送（1段目)
2)No2〜No5の人がそれぞれ「自分のNo*2+2〜自分のNo*2+5)」に転送
　　　　　　　　　　　　　　　　　　　　↑例えばNo2さんならこれでNo6〜No9さんに転送される
　　　　　　　　　　　　　　　　　　　　　　以下No3,4,5さんも同様にして、これにより
　　　　　　　　　　　　　　　　　　　　　　2段目でNo21さんまで行き渡る
3)以下面倒だが適当に式を探してくれ。
てか、もっとランダムなアルゴリズムが欲しいってことか？
そもそも
>P2P がらみで、相手をさがすアルゴリズム
ってので何をしたいのかわからないのでもう少し詳しく解説してくれ。
ちなみに今酔ってるので漏れの書いた香具師は寝言ということで（ｒｙ

3 ：

トリップ変だったしｗ　訂正

4 ：

レス、ありがとうございます。
あるサブネット中、ブロードキャストを使用できない状況で自分の情報を
メンバー全員に、上記の条件で発信する方法を考えてました。
パワーの問題から、常に一人で255発信を行わずに済む方法はないかという
ことで考え始めています。
上流に連続して２つ以上欠番があった場合その子にあたる番号に対して
連番で流してしまうと穴が開きそうです。
４人で４段やると、だいたい４００人受け取れるのでその割合がある程度
均一になるアルゴリズムは無いものかと考えております。

5 ：

>>4
あぁ、そういうことでしたか（＾＾；
そうですね、私の>>2のような駄レスですと
欠番があると全く成り立たなくなってしまうでわないかｗ
頭悪かったようです。
なかなか面白い事やろうと思いましたね・・・
どっかに参考文献ありそう。
ちょっと考えてみます。

6 ：

ユニキャストでの論知的にMany2Manyの通信をするということですか？
根本論だけど、どういう状況から必要になったか知りたい
NEWSみたいにマスタになるサーバを置く形が何故ダメなのか、
#セキュリティ的にP2Pの方がいいと考えた？
よくあるP2Pアプリのように、リストだけをサーバで管理するのが何故ダメなのか、
#これ自体がインターネットを前提としてるので、同一サブネット上では別の方法がると考えた?
何故、マルチキャスト/ブロードキャストが使えないのか
いずれにしても、ユニキャストを使う限り、
同一サブネットという縛りは何の意味もないと思うのですが

7 ：

>>6
漏れもそれは思ってた
>あるサブネット中、ブロードキャストを使用できない状況で
どんな状況なんですか・・・。
ブロードキャストできるようにすればいいのでは。

8 ：

>>1
わかった！
>>7書いた時点ではよく読んでなかった、ｽﾏｿ
>パワーの問題から、常に一人で255発信を行わずに済む方法はないかという
>ことで考え始めています。
要するに1さんはあれだろ？
「NEWSみたいにマスタになるサーバを置く形が何故ダメなのか、 」
とか
「よくあるP2Pアプリのように、リストだけをサーバで管理するのが何故ダメなのか、 」
との問いに対する答えになるかもしれんけど、
完全に負荷分散というかP2Pでそういうシステム出来ないかって言いたいのかな？
#だったらメンバーが最大64人てのもよくわからんが・・・
　64人だったら中央集権でいいじゃん・・。
>パワーの問題から、常に一人で255発信を行わずに済む方法はないかという
>ことで考え始めています。
たかが255発信でくたばるサーバーを現実に利用しているという事か・・・

9 ：

すみません。席はずしてました。
もうちょっと、何してるかを書く必要がありそうですので
ちょっとまとめてきます。

10 ：

どうでもいいけど1の名前萎え

11 ：

>>1
まとめマダ〜！？(; ;
結構待ってるのにぃ〜

12 ：

すみません、いつもはそんなのばっかりの板に生息しているもので、、、
まず最初に、私はネットワークに間して初心者です。
本業は計測機器の制御関係ソフトをやってます。
つまり、仕事上の悩み相談になります。
ルール違反になるのでしたら申し訳ありません。
ある制御範囲を持った機器がネットにぶら下がってたとします。
その機器には、ローカルに端末がぶら下がっています。
端末よりの処理要求がその機器の制御範囲の場合はローカルで
処理されますが、制御範囲を超える場合は同じネットにぶら下
がった、別の機器に対して直接処理要求を行います。
処理を行った機器はその結果をネットを通して、発信もとの
端末に返します。

13 ：

機器は、起動時自分の制御範囲を別の機器に宣言します。
（このときブロードキャストが必要）
この制御範囲は変更可能なので、変更があった場合は同様に
宣言を行います。
それぞれの機器は、内部の要求を宣言された制御範囲と
比較してその IP に対して通信します。
また、結果の返信に関しては、別のIPでモニターのみをしている
機器もいるため、送り元以外にも必要なのでこれもブロード
キャストします。
これらの通信は、基本的には１対１の通信ですが、相手は
その制御範囲によって変わります。
そのため今回は、UDPによる通信を行うことにしました。
（ここが根本的に間違ってると何なのですが、、、）
この機器のOS の　UDP を使用する場合、255 によるブロードキャスト
送信が使えません。（なんかエラーで帰ってきます）
コネクションによるストリーム方の場合は使えるみたいですが、
複数相手に対しての接続とか開放とかがちょっと、面倒なので
とりあえず今回はTCP/IPはおいておきます。
よって、１対１の送信である程度少ない送信行為ですべての機器に
情報が伝わる方法が何かないかと考え始めた次第です。

14 ：

ちなみに、サブネット内６４というのは、最小のモデルでこれを
うまく思いついたら、もっと拡大しようかと考えております。
これらの機器は、勝手に部屋ごと電源を落とされたりします。
そのため、どこかのサーバーに情報を集めてそこに随時聞きにいく
というのは、サーバーの電源が落ちているときは成り立たないので
すべての機器が情報を持つ形にしました。
パワーの話は、MIPS CPUなのですが、（R4000クラス）内部の制御に
忙しく、そのくせ外部への通信が多々発生します。
そのため、力技ではなくなんか工夫して分散させられないものかと
考えてみた次第です。
ただ、他人の負荷分散を押し付けられるということは、平均化すると
自分で、全員に通知するのと等価なのかなともちょっと思っています。

15 ：

以上で、上のレスの疑問に答えられたと思っているのですが
まだ説明が足りないようでしたら言ってください。
基本的に数学は得意ではないので、今日一日、自分の番号と
自分の段数を基にして発生できる適当な数をエクセルで検証
してたんですが、あまりいいのがありません。
なにかいい知恵があればご教授お願いします。

16 ：

>>15
要は、
・機器が複数あり、それぞれ制御範囲が決まっている
・機器につながっている端末は、その機器の制御範囲外のことも要求してくる
・制御範囲外の要求を受けた機器は、ネットワーク上の他の機器にふる
という条件下で、それぞれの機器が自分の制御範囲を
他の機器に知らせる方法がほしいということでしょうか？
伝言ゲーム形式(?）が絶対要件なら、これはもうアプリ屋さんが
仕様設計を考える世界で、ネットワーク屋の範疇じゃないと思う
これが絶対要件で無いなら、ネットワーク屋なら、
まず各機器の制御範囲のデータベースを管理するサーバを作ることを考えるはず
各機器はサーバと常にTCPでコネクションをはっておき、
自分に変更があった場合はサーバに通知、他所の変更はサーバから通知させる
サーバを設置できないなら、マルチキャストを使うのはダメ？
OSPFみたいなイメージで制御範囲のデータベースを常に同期すれば、
やりたいことはできるのではないかと思う
この場合はOSPFのDRみたいな、マスタ的な動作をする機器を作った方が
データベースの同期が安定すると思います。
作るとすれば、前者の方が大分簡単だろうね。
後者はかなり大掛かりかな?
伝言ゲームにこだわるなら、ム板の方がいい回答を得られると思いますよ

17 ：

>>1さん
そんな私もそれほどネトワークそれほど専門家ではないですよ。
しかし1さんの熱心なレスに非常に関心すると共に、
内容(と熱意??)に興味を持ちました。
すこーし印刷して考えてみますわ。
まーこのスレならすごい方もいらっしゃいます。

18 ：

16さん、スマートな要約ありがとうございます。
わたしが、こう書ければよかったのですが文書表現が
苦手でして、、、
みにちゃぶ さん、お付き合いくださってありがとうございます。
もともと伝言ゲーム形式自体は絶対ではありません。
内部の動作に関しては任されているので縛りはないのです。
ただ、今回のスケジュールに関して、多少余裕があったもので
なにか面白くできないかと思い、こんなことを考え始めた次第です。
時間の許す限り、さらにいろいろ調べたり考えたりしてみようと思います。
余談ですが、ここの板はなんというか非常にいいですね。
いつも「２げとずさ」とかそんなのばっかりの板にいるんで自分がスレたて
したらどんなになるのかちょっと怖かったのですが、杞憂でした。
今日はもう寝ます。ありがとうございました。またよろしくお願いします。

19 ：

もう寝たかもしれませんが、一応
同一サブネット限定で何らかのデータベースを共有したいということだと思うので、
ネットワーク屋なら、まずルーティングプロトコルの応用を考えると思います。
>>16の前者はBGP(リフレクタ使用）、後者はOSPFのアルゴリズムが応用できると思います。
さらに前者ならサブネットの制約もありませんし、
一派的なデータ共有のステレオタイプのモデルですから、作るのも比較的容易だと思います。
また、今後何らかの制約が発生した場合に備えて、
伝言ゲームのアルゴリズムを作っておくのもいいと思います。
スケジュールが許すということなら、全ての可能性を試して遊んでみるのも、
別案件への種になるかも知れないので、がんばってみてください。

20 ：

>>18=>>1
はダウソ板住人



・・・だろ？
もしくは葉鍵板？

とりあえず1はハッキリ汁

21 ：

>>20
お前こそ氏ねよ。
板に相応しくねぇぞ。
まぁ1がどこの住人なのかレス見てて謎深まるばかりだから
知りたいってのもあるけどさ。
アルゴリズムなんたらに関しては俺の専門外なのでパス。
#某弱小ISPで「管理者」というか「監視者」やってる者より（哀　　転職してぇ・・・

22 ：

>19さんはかなりの通でつね。
まぁ私も、ﾈﾄﾜｸ野郎ならまずそれを考えると思います。
さらに、時間が少しばかりあるようですので
みんなで何かしら面白い方向に考えていきませう。
私も寝ます。

23 ：

機能は日中は会議ばかりでほとんど仕事がはかどりませんでした。
ただ、その際にやはりデータベースサーバーを立て、送信先情報の
管理を別途し、機器間は個別送信もしくはマルチキャストがよさそう
という方針を出したところ、サーバーの２重化(DNS見たいな感じ)を
行う構成をとることと、運用方法の徹底のお願いをおこなうということで
そっちの線でもいいよ、という話に話になりつつあります。

24 ：

まあ、それとは別に夜さらに色々やってみましたが、なかなか難しそうです。
係数に素数を持ってきて、ある程度大きな値がでるようにし、それを255でわった
あまりの分布をみていると、重複も１０以下ぐらいでおさまり均一に分布するのですが
出てこない数字もかなり均一に分布してしまいます。
また、送信先を選んで失敗したときにその次の値を再度試すというルールにして
ある程度ランダムな値を64/255個選んで、実際に数値を当てはめると、いない数字の
次に偏りがちで、その後の数字が若干手薄になるというような傾向もあります。
抜けを確実に出さないという条件からするとやはり、数学的な何らかの理屈の裏づけが
必要で、試行錯誤は経験地を上げることはできても、解を得られることにはならない
ような気がして自分の頭の悪さを嘆いております。
スレ立てをしたものの責任として、検討を行ってる間はsageで一応報告だけはしていこう
かと思っております。

25 ：

>>23
昨日のまちがいです。
原文を変なフォントで書いているためみづらく、最近誤字が多くなっております。
（みかちゃんフォントは仕事には向かないですね）

26 ：

回覧板方式でどうよ？
送信試行した相手が、送信文をすでに持っていたときは、
受信者リストの交換のみをする。
収束が早くなると思うけど。

27 ：

（＾＾）

28 ：

（＾＾）

29 ：

30 ：

31 ：

32 ：

　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

33 ：

34 ：

何だこのスレ？最後にまともな書き込みがあったのが
02/11/07！！

35 ：

あぼーん

36 ：

あ

37 ：

下記の条件でメンバーに漏れなく通達できるアルゴリズムで
なんかいいの無いですか？
１）メンバーは１から２５５までの任意の番号で最大６４人（重複なし）
２）一人４人ぐらいに転送で、最大４段ぐらい
３）送信先が存在するかどうかは送信エラーで確認できる
４）メッセージにIDを付け、受けたメッセージの内容が重複した場合は
　処理しなくてよい
５）メッセージに段数をつけて、次に送るときは１をひく。
　自分が４段目になったらおしまい。
P2P がらみで、相手をさがすアルゴリズムを、素数とか段数の階乗とか
を式にまぜるなど、色々考えて見たのですがいいのが思いつきません。
参考になる URL とかでもいいです。よろしくお願いします。
（一応あちこち見ましたが、重複や板違いなら申し訳ありません）

38 ：

さ

39 ：

未だ残っていたのですね。
あの頃が懐かしいです。。。

40 ：09/11/15

へえ