Acknowledged Broadcasting and Gossiping in ad hoc radio networks Lecture 3-3: Networking Architecture, Routing Protocols and Algorithms Acknowledged Broadcasting and Gossiping in ad hoc radio networks Jiro Uchida (Nagoya Institute of Technology) Wei Chen (Tennessee State University) Koichi Wada (Nagoya Institute of Technology) International Conference on Principles of Distributed Systems, 2003.

Introduction Ad hoc radio network It provides the flexible communication without base stations and wired networks. It is studied as the network in scenarios such as battlefield, emergency disaster relief, and so on. Various arguments on the broadcasting algorithm in a radio network are presented. 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。））

Radio network v u w x u,v,w,x: devices Consists of the set of devices that can transmit and receive a message. v u w 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。）） x u,v,w,x: devices

Radio network v u w x u,v,w,x: devices Consists of the set of devices that can transmit and receive a message. v u w 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。）） x u,v,w,x: devices

Radio network v u w x u,v,w,x: devices Consists of the set of devices that can transmit and receive a message. v M u w M 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。）） x u,v,w,x: devices

Radio network v u w x u,v,w,x: devices Consists of the set of devices that can transmit and receive a message. v M u w M M 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。）） x u,v,w,x: devices collision

Reachability graph v v u u w w u,v,w: devices Each node represents a device Each directed edge uv represents that, a node u can transmit to a node v (We say that u is an in-neighbor of v and v is an out-neighbor of u) Then we can consider a radio network as a directed graph. v v u u 無線ネットワークについて説明します．無線でメッセージの送受信可能なデバイスの集合で構成されるネットワークのことを無線ネットワークとします．例えばこのようにデバイスがあったとします． 無線ですので各デバイスに送信範囲が存在し，その範囲内に存在するデバイスにメッセージを送信することができます． この場合，デバイスを節点，メッセージが送信可能な場合有向辺といったように無線ネットワークを有向グラフとして考えることができます． （（無線ですので必ず各節点に送信範囲が存在します．この赤丸を節点uの送信範囲としますと この中に存在する節点にデータを送信することができます。 この場合、節点を節点、データが送信可能な場合 有効辺といったように無線ネットワークをグラフとして考えることができます。 無線ネットワークについて説明します。無線でデータの送受信可能なデバイスのことを節点としますと、 その節点の集合で構成されるネットワークのことを無線ネットワークとします。例えばこのように 節点があったとします。）） w w u,v,w: devices

Problems Radio Broadcasting (RB) Acknowledged RB (ARB) Disseminating a message from a source node to all other nodes Acknowledged RB (ARB) Not only RB but also informing a source node of the completion of RB. Radio Gossiping (RG) Disseminating messages from each node to all other nodes 無線ネットワークでの問題として，・・・，・・・，・・・，があげられます． 本研究では完了確認付きブロードキャストARBを考えます． Acknowledged RG (ARG) Not only RB but also informing each node of the completion of RG.

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available 本研究のモデルについて説明します．

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available Round: Discrete time step of the global clock 全デバイス共通の時計によって定まる単位時間をラウンドといい，各デバイスはラウンド単位で同期して動作します． Actions per round: transmission or reception process before and after communication

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available 初期状態では各デバイスは自身のIDのみ知っており，IDは全て異なるものとします．ネットワークの全節点数や隣接している節点の情報は知りません． The number of nodes in the network Information about neighbors unknown IDs are distinct integers between 1 and O(n)

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available 二つ以上のメッセージを同じラウンドで受信できません．このように（図）一つのメッセージが送信されたときのみそのメッセージを受信することができ，二つ以上同時に送信された場合衝突が起こりメッセージを受信できません． receivable unreceivable(collision)

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available Collision detection 衝突検出はできないものとします．衝突検出機能とは，メッセージを受信しなかったときに，衝突が起きたのか，ひとつもメッセージが送られてこなかったのかを区別できる機能のことです．（衝突検出できるモデルでの研究もされていますが），（スライド）本研究では衝突検出できないモデルを考えます． distinguishable collision

Model Each node works per round synchronized by a global clock (like GPS). The initial information of each node ID of itself Whether it is source or not (RB and ARB) Each node cannot receive two or more messages in one round Collision detection is not available We consider tht model without collision detection 衝突検出はできないものとします．衝突検出機能とは，メッセージを受信しなかったときに，衝突が起きたのか，ひとつもメッセージが送られてこなかったのかを区別できる機能のことです．（衝突検出できるモデルでの研究もされていますが），（スライド）本研究では衝突検出できないモデルを考えます． distinguishable collision

Classes of graphs we consider Strongly connected and Bidirectional graph Strongly connected graph また，扱うグラフは，任意の2節点間でパスがある強連結グラフと，全節点の送信範囲が等しい場合の対称有向グラフを考えます． （対称有向グラフは無向グラフとして考えることができます．）

Previous results Problem Collision detection Graph Completion time RB Without Bidirectional O(n) Arbitrary O(n log2n) RG Strongly connected O(n3/2) ARB Unsolvable With O(r+ecc) O(n・ecc) 従来の結果としましてこのような結果があり(表)，衝突検出機能が無い場合，（対称有向グラフでさえ），ARBアルゴリズムが存在しないとされていました．しかしこの結果は，グラフがソースのみの時ソースは常に何もメッセージを受信せず，それが隣接節点が存在しないためなのか衝突が起こっているためなのかを判断できないということに依存しています．そこで本研究では，節点数が2以上の場合は，衝突検出ができなくてもARB（・ARG）が可能であることを示します． n: number of nodes, r: length of message, ecc: largest distance from the source

Previous and our results Problem Collision detection Graph Completion time ARB Without Bidirectional Unsolvable Bidirectional (n≥2) O(n) Strongly connected (n≥2) O(n3/2) ARG O(n log3n) 従来の結果としましてこのような結果があり(表)，衝突検出機能が無い場合，（対称有向グラフでさえ），ARBアルゴリズムが存在しないとされていました．しかしこの結果は，グラフがソースのみの時ソースは常に何もメッセージを受信せず，それが隣接節点が存在しないためなのか衝突が起こっているためなのかを判断できないということに依存しています．そこで本研究では，節点数が2以上の場合は，衝突検出ができなくてもARB（・ARG）が可能であることを示します． Our results n: number of nodes

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. 10 12 11 7 2 8 全節点数を知らないため，従来のアルゴリズムの多くは，フェーズというステップにわけて動作する節点の数を増やしていく，というものでした． 4 1 5

Conventional algorithm (Round Robin) phase 1 phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 1 segment 1 10 12 11 round 1 round 2 Phase 1 7 2 segment 2 8 ID≤21 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． round 1 round 2 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase 2 phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 2 segment 1 10 12 11 round 1 round 2 round 3 round 4 Phase 2 7 2 8 ID≤22 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 2 segment 1 10 12 11 round 1 round 2 round 3 round 4 Phase 2 7 2 8 ID≤22 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 2 segment 2 10 12 11 round 1 round 2 round 3 round 4 Phase 2 7 2 8 ID≤22 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 2 segment 4 10 12 11 round 1 round 2 round 3 round 4 Phase 2 7 2 8 ID≤22 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase 3 phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 3 segment 1 10 12 11 round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 Phase 3 7 2 8 ID≤23 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 3 segment 1 10 12 11 round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 Phase 3 7 2 8 ID≤23 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 3 segment 1 10 12 11 round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 Phase 3 7 2 8 ID≤23 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase 4 phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 4 Phase 4 segment 1 10 12 11 round 1 round 2 round 3 round 4 round 5 round 6 round 7 round 8 7 ID≤24 2 8 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 4 Phase 4 segment 1 10 12 11 round 9 round 10 round 11 round 12 round 13 round 14 round 15 round 16 7 ID≤24 2 8 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 4 Phase 4 segment 16 10 12 11 round 9 round 10 round 11 round 12 round 13 round 14 round 15 round 16 7 ID≤24 2 8 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 : node which received a message : transmitter

Conventional algorithm (Round Robin) phase k ( 2k segments, 1 segment = 2k rounds ) 　　The node with ID i acts as a transmitter in round i. phase 4 Phase 4 segment 16 10 12 11 round 9 round 10 round 11 round 12 round 13 round 14 round 15 round 16 7 ID≤24 2 8 例えばこの図ですと，フェーズ1ではIDが21以下の節点1,2が動作します． 4 1 5 Any node cannot know when RB finishes

Impossibility of ARB a b s s ARB is not solvable in general (i) only source (ii) a and b perform the same action A source node receives no message そこで，提案するARBアルゴリズムのフェーズ k では，各節点がIDが2kより大きな隣接節点があるかどうかを判断できるようにします．（スライド）これにより，ソースがブロードキャストの完了を確認することができます． 以下ARBアルゴリズムの詳細を説明します． A source node cannot distinguish (i) and (ii) ARB is not solvable in general

Each node recognizes all its neighbors accordingly. Our ARB algorithm phase k Each node knows whether there exists the node with ID>2k. Each node recognizes all its neighbors accordingly. A source node can confirm the completion of RB by being informed of it. そこで，提案するARBアルゴリズムのフェーズ k では，各節点がIDが2kより大きな隣接節点があるかどうかを判断できるようにします．（スライド）これにより，ソースがブロードキャストの完了を確認することができます． 以下ARBアルゴリズムの詳細を説明します．

ARB algorithm (bidirectional) phase k (nodes with ID<2k act mainly) (total 9･2k-1 rounds) 　　stage A : (knowing the neighbors) Each node sends own ID. 　　stage B : (transmitting the minimum ID) Each node sends the minimum ID of its neighbors’s IDs. 　　stage C : (judging the recognition of all neighbors) The nodes with minimum ID (in Stage B) and ID>2k send their IDs. (at least one node in neighbors act as a transmitter) 　　stage D : (confirming the completion) A source node transmits the source message and collects the information in Stage C. (2k-1 rounds) (2k rounds) (2k rounds) （提案する）対称有向グラフでのARBアルゴリズムは，フェーズを4つのステージA,B,C,Dにわけます． ステージC以外では従来のアルゴリズムと同じく ID≤2k の節点が動作します． ステージAでは，各節点が自身のIDを送信することで，隣接節点を知り， ステージBでは，その隣接節点の中で最小のIDを送信します． ステージCでは，ステージBで送信された最小IDをもとに，隣接節点の中で最小のIDの節点と ID>2k の節点が送信します．このステージで全隣接節点を知っているかどうかを判断します． ステージDでは，ソースメッセージを伝達し，また，全隣接節点を知っているかどうかというステージCでの情報もソースに集めます． (2･2k rounds)

ARB algorithm (bidirectional) Stage A ARB algorithm (bidirectional) 2,4 10 11 4 1,4 7 2 phase k-1 (k = 3) 8 4 4 フェーズk-1の終わりでは，各節点は ID が 2k-1 以下の隣接節点の ID を知っています．吹き出しがそれにあたります． （ソースメッセージも受信済みであることを言うか？） 1 5 2 2 ID :IDs of neighbors

ARB algorithm (bidirectional) stage A (knowing the neighbors) Node with 2k-1<ID≤2k sends own ID i in i-th round (2k-1 rounds) 2,4 10 11 4 1,4 7 2 phase k (k = 3) 8 4 4 フェーズkのステージAでは，ID が 2k-1 より大きく 2k 以下の節点が自身の ID を送信します． この例では節点 5,7,8 が自身のIDを送信します． 1 phase k-1 5 2 2 ID :IDs of neighbors

ARB algorithm (bidirectional) stage A (knowing the neighbors) Node with 2k-1<ID≤2k sends own ID i in i-th round (2k-1 rounds) round 5 2,4 10 11 4,5 1,4 7 2 8 phase k 4 4 1 phase k-1 5 2,5 2 :transmitter ID :IDs of neighbors

ARB algorithm (bidirectional) stage A (knowing the neighbors) Node with 2k-1<ID≤2k sends own ID i in i-th round (2k-1 rounds) round 7 2,4,7 7 10 11 4,5 1,4 7 2 8 phase k 4,7 4 1 phase k-1 5 2,5,7 2 :transmitter ID :IDs of neighbors

ARB algorithm (bidirectional) stage A (knowing the neighbors) Node with 2k-1<ID≤2k sends own ID i in i-th round (2k-1 rounds) round 8 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 1 phase k-1 5 2,5,7 2 :transmitter ID :IDs of neighbors

ARB algorithm (bidirectional) Stage B ARB algorithm (bidirectional) stage B (transmission of the minimum ID) Nodes with ID≤2k send the min ID of their neighbors’s IDs (2k rounds) 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 次に，ID が 2k 以下の節点が，（自身のIDと一致するラウンドで），自身の隣接節点の中の最小IDを送信します． （これには， 2k ラウンド必要です｜かかります．） 1 5 2,5,7 2 :transmitter ID :IDs of neighbors

ARB algorithm (bidirectional) stage B (transmission of the minimum ID) Nodes with ID≤2k send the min ID of their neighbors’s IDs (2k rounds) 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 次に，ID が 2k 以下の節点が，（自身のIDと一致するラウンドで），自身の隣接節点の中の最小IDを送信します． （これには， 2k ラウンド必要です｜かかります．） 1 5 2,5,7 2 :transmitter ID :IDs of neighbors

ARB algorithm (bidirectional) stage B (transmission of the minimum ID) Nodes with ID≤2k send the min ID of their neighbors’s IDs (2k rounds) round 2 2,4,7 7,8 10 11 1 4,5 1,4 7 2 1 8 phase k 4,7 1 4 次に節点2が最小ID1を送信します．全隣接節点に送信されますが，自身のIDでなければその情報は捨てます． 1 5 2,5,7 2 ID :IDs of neighbors

ARB algorithm (bidirectional) stage B (transmission of the minimum ID) Nodes with ID≤2k send the min ID of their neighbors’s IDs (2k rounds) round 5 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4 4,7 4 同様に，節点4,節点5,節点7，と最小IDを送信します． 1 5 2,5,7 2 ID :IDs of neighbors

ARB algorithm (bidirectional) Stage C ARB algorithm (bidirectional) stage C (judging the recognition of all neighbors) The nodes with min ID (in Stage B) and ID>2k send their ID. (2k rounds) 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 ステージCでは，隣接節点の最小IDの節点と，IDが2kより大きい節点が送信します． 1 5 2,5,7 2 ID :IDs of neighbors

ARB algorithm (bidirectional) stage C (judging the recognition of all neighbors) The nodes with min ID (in Stage B) and ID>2k send their ID. (2k rounds) round 2 2,4,7 7,8 10 11 4,5 1,4 10 7 2 1 8 phase k 4,7 4 ラウンド2では，節点2の隣接節点の中で最小のIDである1が送信しますが，節点10も自身のIDが2kより大きいので送信し，衝突が起こります． このように自身の隣接節点を全て知らない節点では衝突が起こるようにし，隣接節点を全て知らないという情報を保持しておきます．これを灰色の吹き出し？であらわします． 1 5 2,5,7 2 ID :IDs of neighbors

ARB algorithm (bidirectional) stage C (judging the recognition of all neighbors) The nodes with min ID (in Stage B) and ID>2k send their ID. (2k rounds) Not receive (recognize not knowing all its neighbors) round 2 2,4,7 7,8 10 11 4,5 1,4 10 7 2 1 8 phase k 4,7 4 ラウンド2では，節点2の隣接節点の中で最小のIDである1が送信しますが，節点10も自身のIDが2kより大きいので送信し，衝突が起こります． このように自身の隣接節点を全て知らない節点では衝突が起こるようにし，隣接節点を全て知らないという情報を保持しておきます．これを灰色の吹き出し？であらわします． 1 5 2,5,7 2 :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) stage C (judging the recognition of all neighbors) The nodes with min ID (in Stage B) and ID>2k send their ID. (2k rounds) round 5 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4 4,7 4 ラウンド5では，節点5は全ての隣接節点を知っているので，衝突しません． 1 5 receive (know all its neighbors) 2,5,7 2 :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 ステージDでは，IDが2k以下の節点でソースメッセージを伝達し，またその過程で，各節点のステージCでの状態を知ります． 今，ソースが節点5であるとします． 1 5 2,5,7 2 :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 ステージDでは，IDが2k以下の節点でソースメッセージを伝達し，またその過程で，各節点のステージCでの状態を知ります． 今，ソースが節点5であるとします． 1 5 2,5,7 2 leader :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 ignore 2 8 phase k M 4 4,7 4 まず最初にソースが，ソースメッセージMと送信先の節点のID（この場合は4）を送信します． 1 5 2,5,7 2 :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k 4,7 4 メッセージを受信した節点は，全隣接節点を知らなければ，その情報をメッセージに付加して送信します． M 2 1 5 2,5,7 2 Attach no reception min ID :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k M 5 4,7 4 （1：衝突情報が付加された状態で送信，自身も灰色．） このようにして，ソースを含む連結成分にメッセージを伝達していきます． ステージDの最後で，ソースが受信したメッセージに衝突情報が付加されていれば，ブロードキャストは完了していないとわかります． 1 5 2,5,7 2 :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) Stage D (confirming the completion) Nodes with ID≤2k send the source message. Know conditions in Stage C. 2,4,7 7,8 10 11 4,5 1,4 7 2 8 phase k M 5 4,7 4 （1：衝突情報が付加された状態で送信，自身も灰色．） このようにして，ソースを含む連結成分にメッセージを伝達していきます． ステージDの最後で，ソースが受信したメッセージに衝突情報が付加されていれば，ブロードキャストは完了していないとわかります． 1 5 2,5,7 2 Not complete yet :no reception min ID ID :IDs of neighbors

ARB algorithm (bidirectional) 2,4,7 7,8 10 11 4,5 1,4 phase k+1 7 2 8 4,7 4 次にフェーズが k+1 になり，ステージAを実行します．（この図のときは，）このフェーズで全ての隣接節点を知ることができるので，ステージCで衝突が起こる節点はなく，よってステージDでソースはブロードキャストが完了したとわかります． 1 5 2,5,7 2 ID :IDs of neighbors

ARB algorithm (bidirectional) Completion time 　let k be 2k-1< n ≤ 2k . Message size 　the maximum length of the message sent each time is at most O(r + log n) bits ( r : the size of the source message )

ARB algorithm (bidirectional) Theorem Our ARB algorithm solves an ARB in time O(n), for any n-node bidirectional graphs with n  2. Maximum length of the message transmitted each time is O(r + log n) bits, where r is the size of the source message.

Extension of our ARB algorithm We can extend our ARB algorithm for bidirectional graphs to following three algorithms based on it. ARG algorithm for bidirectional graphs ARB algorithm for strongly connected graphs ARG algorithm for strongly connected graphs

ARG algorithm (bidirectional) Since in ARB algorithm the source is leader, it can be extended to ARG algorithm by electing the leader.

ARG algorithm (bidirectional) Since in ARB algorithm the source is leader, it can be extended to ARG algorithm by electing the leader. 　　stage D : transmit the source message. Source collects no reception min ID. 　　stage D : elect a leader. transmit the message each node has. Each node collects no reception min ID.

ARB algorithm (strongly connected) ARB algorithm (bidirectional) phase k 　　stage A : Each node sends own ID. 　　stage B : Each node sends the minimum ID its neighbors’s IDs. 　　stage C : The node with minimum ID (in Stage B) and ID>2k send its ID. 　　stage D : A source node transmits the source message and collects no reception min ID. 先ほどの対称有向グラフでのARBアルゴリズムは， フェーズkでは，主に ID≤2k の節点が， ステージAでは，自身のIDを送信し， ステージBでは，隣接節点の最小IDを送信します． ステージCでは，隣接節点の最小IDの節点と ID>2k の節点が送信し， ステージDでは，ソースメッセージを伝達し，かつ，ステージCでの情報も集めました．

v v Bidirectional graph in-neighbors of v = out-neighbors of v また，扱うグラフは，任意の2節点間でパスがある強連結グラフと，全節点の送信範囲が等しい場合の対称有向グラフを考えます． （対称有向グラフは無向グラフとして考えることができます．） in-neighbors of v  out-neighbors of v Strongly connected graph

ARB algorithm (strongly connected) ARB algorithm (bidirectional) phase k 　　stage A : Each node sends own ID. 　　stage B : Each node sends the minimum ID its neighbors’s IDs. 　　stage C : The node with minimum ID (in Stage B) and ID>2k send its ID. 　　stage D : A source node transmits the source message and collects no reception min ID. 先ほどの対称有向グラフでのARBアルゴリズムは， フェーズkでは，主に ID≤2k の節点が， ステージAでは，自身のIDを送信し， ステージBでは，隣接節点の最小IDを送信します． ステージCでは，隣接節点の最小IDの節点と ID>2k の節点が送信し， ステージDでは，ソースメッセージを伝達し，かつ，ステージCでの情報も集めました．

ARB algorithm (strongly connected) phase k 　　stage A : Each node sends own ID. 　　stage B : Each node gossips own ID and the minimum ID of its neighbors’s IDs. 　　stage C : The node with minimum ID (in Stage B) and ID>2k send its ID. 　　stage D : Each node broadcasts no reception min ID. A source node broadcasts the source message.(2・RB(2k)rounds) (RG(2k) rounds) これを変更して，強連結グラフでのARBアルゴリズムを得ることができます． 変更部分は，対称有向グラフでは隣接節点の最小IDは1ラウンドで隣接節点に送信できますが，強連結グラフではゴシップをすることになります． また，ステージDでは，各節点のステージCでの情報をソースに知らせるため，ゴシップをする必要があります．

ARB algorithm (strongly connected) phase k 　　stage A : Each node sends own ID. 　　stage B : Each node gossips own ID and the minimum ID of its neighbors’s IDs. 　　stage C : The node with minimum ID (in Stage B) and ID>2k send its ID. 　　stage D : Each node broadcasts no reception min ID. A source node broadcasts the source message.(2・RB(2k)rounds) Existing algorithm RG(n) = O(n3/2) (RG(2k) rounds) これを変更して，強連結グラフでのARBアルゴリズムを得ることができます． 変更部分は，対称有向グラフでは隣接節点の最小IDは1ラウンドで隣接節点に送信できますが，強連結グラフではゴシップをすることになります． また，ステージDでは，各節点のステージCでの情報をソースに知らせるため，ゴシップをする必要があります． Existing algorithm RB(n) = O(n log2n)

Strongly connected (n≥2) Conclusion 　 We show ARB・ARG can be solved without collision detection for graph with n≥2. Problem Graph Completion time ARB Bidirectional Unsolvable Bidirectional (n≥2) O(n) Strongly connected (n≥2) O(n3/2) ARG O(n log3n) 衝突検出機能が無い場合，ARBアルゴリズムが存在しないのは節点数が1の時のみで，節点数が2以上の場合は，（衝突検出ができなくても）ARBが可能であることを示しました．

Open problems faster ARB algorithm for strongly connected graphs without RG ARB algorithm with collision detection for strongly connected graphs efficient leader election algorithm for bidirectional graph 衝突検出機能が無い場合，ARBアルゴリズムが存在しないのは節点数が1の時のみで，節点数が2以上の場合は，（衝突検出ができなくても）ARBが可能であることを示しました． efficient leader election algorithm for bidirectional graph are enumerated.