Distributed computing



Download 0,86 Mb.
bet11/38
Sana24.04.2022
Hajmi0,86 Mb.
#578449
1   ...   7   8   9   10   11   12   13   14   ...   38
Bog'liq
distcomp

USING THE RESOURCE

  • Process Pi starts using the resource when:
    • its own request on its local request queue has the earliest Lamport timestamp T (consistent with );
    • it has received a message (either an acknowledgement or some other message) from every other process with a timestamp larger than T.
    • iii. (Always) On receiving a release from pj, remove the request from pj.

CORRECTNESS

  • Theorem: Mutual exclusion and first-requested, first-served are achieved.
  • Proof
  • Suppose Pi and Pj are both using the resource at the same time and have timestamps Ti and Tj.
  • Suppose Ti < Tj. Then Pj must have received i’s request, since it has received at least one message with a timestamp greater than Tj from Pi and since messages arrive in the order they are sent. But then Pj would not execute its request. Contradiction.
  • First-requested, first-served. If Pi requests the resource before Pj (in the  sense), then Ti < Tj, so Pi will win.

CRITICISMS

  • Many messages. If only one process is using the resource, it still must send messages to many other processes.
  • If one process stops, then all processes hang (no wait freedom; could we achieve?)

Is there a Wait-Free Variant?

  • Modify resource locally and then send to everyone. If everyone accepts the new value, then new resource value is good.
  • Difficulty: what do you do if you don’t hear from someone? Could there be a partition of processes?
  • Is this even possible?

NEED FOR PHYSICAL CLOCKS

  • Time as a partial order is the most frequent assumption in distributed systems, however it is sometimes important to have a physical notion of time.
  • Example: Going outside the system. Person X starts a program A, then calls Y on the telephone, who then starts program B. We would like A  B.
  • But that may not be true for Lamport clocks, because they are sensitive only to inter computer messages. Physical clocks try to account for event ordering that are external to the system.
  • X
  • Y
  • starts A
  • Would like starts A  starts B
  • But this may not be true with
  •  as so far defined.
  • calls y
  • receives call
  • from x
  • starts B

Download 0,86 Mb.

Do'stlaringiz bilan baham:
1   ...   7   8   9   10   11   12   13   14   ...   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