授業資料 - 慶應義塾大学徳田研究室

ADC Systems
～ Protocols and Distributed Algorithms ～
慶應義塾大学環境情報学部
徳田英幸
© H.Tokuda 2008
課題 I について。。。
プロセス間通信: Direct IPC

The communication is done between two processes without
using any communication entity.
Bsend(process_id, message, size)
Nsend(process_id, message, size)
Brec(process_id, buffer, size)
Nrec(process_id, buffer, size)
process_id = Brecany(buffer, size)
process_id = Nrecany(buffer, size)
Request(process_id, message, sizeof(message),
buffer, sizeof(buf)
Reply(process_id, message, size)
© H.Tokuda 2008
並行プロセスの挙動
Pipeline（2）
Process P1
{
…
Nsend(p2, …);
…
}
p1
p2
Process P2
{
…
Nsend(p3, …);
…
}
P3
© H.Tokuda 2008
…
pk
並行プロセスの挙動
Dynamic Worker Model
Server S1
{
…
ci=Brecany(msg,…)
create_worker(ci,...)
…
}
Process w1
{
…
do_service(msg,…)
reply(ci,…)
}
w1
c1
s1
.
.
.
wk
© H.Tokuda 2008
並行プロセスの挙動
Static Worker Model
Server S1
{
…
ci=Brecany(msg,…)
if(ci is worker)
assign_task(ci, …)
else
enque(ci, task)
…
}
c1
(未完成）
Process w1
{
…
request(s1, ...)
do_service(msg,…)
reply(ci,…)
}
s1
w1
.
.
.
wk
© H.Tokuda 2006
自律分散協調システム
プロトコルと分散アルゴリズム
慶應義塾大学環境情報学部
徳田英幸
© H.Tokuda 2008
自律分散協調システムとは？
もう一度復習。。。
What is an Autonomous Distributed Cooperative
System (ADC System)？
 No supervisor which can
control/manage the entire system
システム内にシステム全体を制御／統治するスパーバイザは存在しない。
 The system consists of autonomous,
distributed and cooperative subsystems
各サブシステムは、自律、分散した構成要素からなる。
 The system functions are realized by
cooperations among subsystems
全体のシステムの機能は、サブシステム間の協調作業によって遂行される。
© H.Tokuda 2008
What is autonomy?
 Social Systems

Governance Model ガバナンスモデル
 電子政府モデル
 地方自治体モデル

Education, ITS, Safety Systems
教育、交通、安全システム
 Roundaout 環状交差点問題
 ADC Model
 Emergence

創発とは？
Waveは、どう起るか？蟻
 Robot Alignment Problem
ロボット自動整列問題
 ロボットよ、コンパスを持って協調せよ！
 Cleaning Robot Problem
掃除ロボット問題
 どのようなアルゴリズムが良いか？
© H.Tokuda 2008
Cooperation Mechanisms
 Cooperation mechanisms
 Cooperation Protocols
 Cooperation Patterns? どのような協調パターンがあるのか？
 Definition & Description? どのように定義・記述するのか？

Why Cooperation?
なぜ協調するのか？
 Biological Protocols
 Biological Systems
生物システム
 ICT Protocols





Client-Server
Ethernet’s MAC Layer
Auction protocol
Circulation Protocol 回覧板プロトコル
Other protocols
© H.Tokuda 2006
DARPA Urban Challenge
～事例1 ～
Urban Challenge
2007/11/3
© H.Tokuda 2008
DARPA Urban Challenge (1)
© H.Tokuda 2007
Autonomous Ground Vehicles
(AGV)11
 Car Crash1
 Car Crash2
 Cornell and MIT
© H.Tokuda 2007
DARPA Urban Challenge (2007)
 Stanford Team
© H.Tokuda 2007
DARPA Urban Challenge (2007)
 CMU Test
© H.Tokuda 2007
DARPA Urban Challenge (2007)
 CMU Team
© H.Tokuda 2007
Network Robot
～事例2 ～
Network Robots?
© H.Tokuda 2006
Robotic Service Experiment Field
at Universal Citywalk Osaka by N. Hagita
Noisy BGM for Robots
Camera
Dark
Bright
Laser Range Finder
21
ユニバーサルシティウォーク大阪（１）
ユニバーサルシティウォーク大阪（２）
ユニバーサルシティウォーク大阪（3）
Wireless Sensor Networks
～事例3 ～
Sensor Network Models
 Sink-node Model




Habitat sensing
Seismic monitoring
Structuring instrumentation
Soil conditioning
Sink
Node
 P2P Model





Smart Kindergarten
Smart Objects, Smart Toys
Smart Surroundings
Lovegety
Navigety
© H.Tokuda 2006
Smart Nodes
P2p models: Lovegety & Navigety
The Original p2p
goods: Lovegety
Navigety
© H.Tokuda 2006
A Group Tour Keeper
 Smart Sensor with LED lights +
button
１２
© H.Tokuda 2006
１３
自律分散協調システム
プロトコルと分散アルゴリズム
慶應義塾大学環境情報学部
徳田英幸
© H.Tokuda 2008
プロトコルとは？
～協調動作の記述～
プロトコルとは？
 外交上の儀礼
 通信の送信側と受信側で取り決めた約束事
 通信手段
pro･to･col
1 Ｕ(外交上の)儀礼，典礼.
2 Ｃ条約原案; 議定書，プロトコル.
3 Ｃ (国家間の)協定.→＃
4 Ｃ《米》 (実験･治療の)実施要綱[計画].
5 Ｃ【電算】プロトコル《データ通信の手順》.
[株式会社研究社新英和・和英中辞典]
© H.Tokuda 2008
プロトコルの記述
 プロトコルの記述は、通信上の約束事すべてを定
義する。
 通信メッセージのフォーマット（書式）の詳細
(format) -> (syntax)
 メッセージを交換する際の手順 (procedure) ->
(grammer)
 正しいメッセージが表わしている意味、語彙
(correctness) -> (semantics)
 Completeな記述 vs. Incompleteな記述
© H.Tokuda 2008
何のためにプロトコルが必要か？




データ転送に必要な初期化や終了
送信者と受信者との同期（条件）
転送エラーの検出や訂正
データの書式や符合化を行う
© H.Tokuda 2007
Protocolの記述




自然言語
Time-space chart
状態遷移図
擬似Prog. Languages
State Transition Diagram状態遷移図
Sender
Receiver
RTS
RTR
-msg
+msg
Wait
Wait
+ACK
-ACK
© H.Tokuda 2008
Time-Space Chart
Sender
Receiver
msg
ACK
© H.Tokuda 2008
Concurrent Programming Language
Pr ocess Sender ( )
{
while( TRUE) {
pr epar e_ mess age( buf f er ) ;
f r ame.dat a = buf f er ;
send_ t o_ net wor k( f r ame) ;
}
Pr ocess Receiver ( )
{
while( TRUE) {
wait _ f or _ f r am e( buf f er ) ;
r eceive_ f r om _ net wor k( f r am e) ;
buf f er = f r am e.dat a;
}
© H.Tokuda 2008
Stop-and-Wait Protocol
Pr ocess Sender ( )
Pr ocess Receiv er ( )
{
{
while ( TRUE) {
while ( TRUE) {
pr epar e_ message( buf f er ) ;
wait _ f or _ f r ame( buf f er ) ;
f r ame.d at a = buf f er ;
r eceiv e_ f r om_ net wor k( f r ame) ;
send_ t o_ net wor k( f r ame) ;
buf f er = f r ame.d a t a;
wait _ f or _ f r ame( ack) ;
pr epar e_ message( ack) ;
...
f r ame.d at a = ack;
}
send_ t o_ net wor k( f r ame) ;
}
© H.Tokuda 2008
いくつかの例題
 入札プロトコル
 回覧板プロトコル
 逆オークションプロトコル
© H.Tokuda 2008
入札プロトコル（１）
S１
S２
m（p1）
S３
S４
Q: 終了条件は？
winnerへの通知は？
Q：タイムアウトは？
全員がいつもタイムリーに返信？
m（p2）
Note: S１からのグループキャスト
は、ユニキャストと区別するために
各受信者のところで矢印マークを入
れる
© H.Tokuda 2008
回覧板プロトコル（１）
© H.Tokuda 2008
回覧板プロトコル(2)
© H.Tokuda 2007
分散アルゴリズム
分散アルゴリズム(1)






Distributed Mutual Exclusion
Election Algorithm
Distributed Deadlock
Clock Synchronization
Byzantine consensus problem
。。。
© H.Tokuda 2008
直感的な例
Pj
Pi
Pk
req
reply
reply
IN_USE
reply
© H.Tokuda 2009
課題-2
 以下のプロトコルをtime-space chartを使っ
て記述せよ。参加しているプロセスは、s1か
らs4の４プロセスとする。
 A) 入札プロトコル
 B) 回覧板プロトコル
 Due: 5/11/2009
© H.Tokuda 200９
Note: S１からのグループキャスト
は、ユニキャストと区別するために
各受信者のところで矢印マークを入
れる
S1
S2
S3
S4

Download Report