Distributed computing



Download 0,86 Mb.
bet16/38
Sana24.04.2022
Hajmi0,86 Mb.
#578449
1   ...   12   13   14   15   16   17   18   19   ...   38
Bog'liq
distcomp

MINIMUM-HOP PATHS

  • The round by round approach takes a long time. Can you think of an asynchronous approach that takes less time?
  • How do you know when you’re done?
  • A
  • B
  • D
  • S
  • F
  • E
  • C
  • A
  • B
  • D
  • S
  • F
  • E
  • C
  • NETWORK

Group Protocol

  • All nodes start at distance infinity except S which is at distance 0.
  • S sends a message. All receivers of S’s message are at distance 1.
  • When a node receives a message that it is at distance k and k < that node’s current distance, the node sends k+1 to all its neighbors.

Group Protocol Termination

  • Invariant: If for all nodes n the neighbors of n have distance at least dist(n) – 1, then we’re done.

Anna’s Group Protocol Termination

Group Protocol Termination

CLUSTERING

  • K-means clustering:
  • Choose k centroids from the set of points at random.
  • Then assign each point to the cluster of the nearest centroid.
  • Then recompute the centroid of each cluster and start over.
  • Why does this converge?
  • A Lyapunov function is a function of the state of an algorithm that decreases whenever the state changes and that is bounded from below.
  • With sequential k-means the sum of the distances always decreases.
  • Can't get lower than zero.

Download 0,86 Mb.

Do'stlaringiz bilan baham:
1   ...   12   13   14   15   16   17   18   19   ...   38




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish