Jeden z mechanismů koordinace v distrbuovaných systémech

Princip

Proces musí explicitně požádat ostatní procesy o souhlas před vykonáním kritické akce. Pokračuje až po obdržení potvrzení od všech relevantních procesů.

Klíčová myšlenka:

Žádné centrální řízení, žádný token. Každý se ptá všech ostatních: “Můžu?”

Jak to funguje

Základní průběh

  1. REQUEST: Proces Pi chce do CS → rozešle REQUEST(timestamp) všem ostatním procesům
  2. Hlasování: Každý proces obdrží žádost a rozhodne se:
  3. Čekání: Pi čeká, až dostane GRANT od všech N-1 procesů
  4. Vstup: Teprve pak Pi vstoupí do kritické sekce
  5. RELEASE: Po opuštění CS pošle Pi všem procesům RELEASE, aby uvolnil jejich hlasy

    Rozhodování o prioritě (logický čas)

    if dostanu REQUEST(Tj) od Pj:
  if nechci_do_CS:
 pošli GRANT(Pj)
  elif chci_do_CS and (Ti < Tj or (Ti == Tj and i < j)):
 odlož_odpověď(Pj)  # Já mám přednost
  else:
 pošli GRANT(Pj)     # Pj má přednost

    Důležité: Porovnává se Lamportův timestamp (logický čas) + process ID jako tiebreaker.

Varianty

1. Ricart-Agrawala Algorithm (klasika)

Optimalizace oproti naivnímu přístupu:

Proces Pi chce do CS:
  Ti = Lamport_timestamp++
  pošli REQUEST(Ti) všem
  čekej na (N-1) GRANT
  vstup_do_CS()
  opusť_CS()
  pošli odložené GRANTy

2. Naivní Permission-based (3-fázový)

3. Maekawa’s algorithm (quorum, ne čistý permission)

Vlastnosti

Výhody

1. Plně distribuovaný

2. Férové uspořádání

3. Žádné ztracené tokeny

4. Dobrá pro malé systémy

Nevýhody

1. Vysoký počet zpráv

2. Všichni musí odpovědět

3. Nízká odolnost vůči výpadkům

4. Režie při nízké konkurenci

Použití v praxi

1. Mutual Exclusion

Ricart-Agrawala Algorithm:

class Process:
  def request_CS(self):
    self.timestamp = lamport_clock.tick()
    self.state = REQUESTING
    
    # Rozešli REQUEST všem
    for p in other_processes:
      send(p, REQUEST(self.id, self.timestamp))
    
    # Čekej na N-1 odpovědí
    wait_for_grants(N - 1)
    
    self.state = IN_CS
    enter_critical_section()
  
  def on_receive_request(self, sender, timestamp):
    lamport_clock.update(timestamp)
    
    if self.state == IN_CS or \
       (self.state == REQUESTING and self.timestamp < timestamp):
      # Odlož odpověď
      deferred_queue.append(sender)
    else:
      # Pošli GRANT okamžitě
      send(sender, GRANT(self.id))
  
  def release_CS(self):
    self.state = RELEASED
    
    # Pošli odložené GRANTy
    for p in deferred_queue:
      send(p, GRANT(self.id))
    deferred_queue.clear()

2. Distributed Consensus

Two-Phase Commit (2PC):

Problémy a řešení

Problém 1: Pád procesu

Problém: Pokud proces Pj spadne, všichni čekají navždy na jeho GRANT.

Řešení 1: Timeouts + Failure Detection

if not received_grant(Pj) and timeout_elapsed():
  if failure_detector.is_failed(Pj):
    # Považuj Pj za mrtvý, ignoruj jeho hlas
    continue_without(Pj)
  else:
    # Pošli znovu
    resend_request(Pj)

Řešení 2: Group Membership

Problém 2: Nekonečné čekání při souběžných žádostech

Příklad:

Řešení: logický čas + deterministické uspořádání

if T1 < T2:  P1 má přednost, P2 pošle GRANT
elif T1 > T2: P2 má přednost, P1 pošle GRANT
elif T1 == T2 and i < j: Pi má přednost (deterministické)

→ Vždy jeden dostane přednost → deadlock nemůže nastat

Problém 3: Vysoká latence

Problém: Čekání na všech N procesů = latence nejpomalejšího

Řešení: Použij quorum-based místo permission-based

Srovnání s ostatními mechanismy

Vlastnost Permission token-based koordinace quorum-based koordinace
Počet zpráv O(N) ❌ O(1) ✅ O(√N) 🟡
Odolnost vůči výpadkům 🟡 Nízká-střední ❌ Nízká ✅ Vysoká
Latence ❌ N × RTT 🟡 Závisí 🟡 √N × RTT
Férové uspořádání ✅ Lamport TS 🟡 Závisí ✅ Lamport TS
Složitost 🟡 Střední ✅ Nízká ❌ Vysoká
Centralizace ✅ Žádná ❌ Token je SPOF ✅ Žádná

Optimalizace

1. Implicitní GRANT (Ricart-Agrawala)

Místo:

REQUEST → GRANT → RELEASE

Použij:

REQUEST → (implicitní souhlas pokud nechci CS) → RELEASE

→ Ušetříš N zpráv

2. Broadcast místo unicast

Pokud máš reliable multicast:

# Místo N unicastů
for p in processes:
  send(p, REQUEST)

# Použij broadcast
broadcast(REQUEST)  # 1 zpráva místo N

3. Voting Sets (Maekawa’s algorithm)

Kdy použít Permission-based?

Dobré pro:

❌ Nepoužívej pro:

Příklady z praxe

1. Distributed Databases:

3. Distributed File Systems:

Vztah k logickému času

Permission-based algoritmy kriticky závisí na Lamportových timestampech:

  1. Totální uspořádání: (T, PID) vytváří úplné uspořádání událostí
  2. Férové rozhodování: Starší timestamp = vyšší priorita
  3. Deadlock prevence: Deterministické rozhodnutí při konfliktu

Bez logického času by permission-based nefungoval!

Související pojmy