[Cloud computing] 9. Global States

Reference

1. Thomas Erl_ Zaigham Mahmood_ Ricardo Puttini - Cloud Computing_ Concepts, Technology & Architecture-Prentice Hall,

2. Cloud Computing class by Professor Heonchang-Yu of the Department of Computer Science and Engineering at Korea University

 

Global states

Distributed garbage collection

• DS 내에서 더 이상 아무 곳에서도 참조되지 않으면 garbage
• garbage check → 시스템 내에서 해당 개체에대한 참조가 없는지, process 사이에서의 참조 확인

Distributed deadlock detection

• wait-for graph 내에서 cycle이 있는지 검사

Distributed termination detection

• 각 process가 중지되었는지 검사

Consistent cuts

• event : process 내부 액션 또는 메시지 송수신
• cut : global history의 subset
  • S (global state) = (s1, s2, …., sn) <- local state의 집합
  • local state들의 집합을 취하여 global state를 형성한다.
  • p2 에서 메시지 m1의 수신이 포함되지만, p1 에서는 그렇지 않다면 inconsistent 하다.
    • 예를 들어 sending이 없는데 receiving이 있으면 inconsistent
• Consistent cut : 포함된 각 event에 대해 해당 event 이전에 발생한 모든 event도 포함하는 cut
  • for all events e∈C, f →e ⇒ f ∈C
• Inconsistent cut : orphan message를 포함하는 cut
• consistent global state는 consistent cut에 해당한다.

Snapshot Algorithm

가정

1. failure X
2. lost X
3. 단방향 채널
4. strongly connected → 모두가 1대1로 연결
5. any process, any time, snapshot을 찍을 수 있다.
6. snapshot 찎는 중 normal message를 주고 받을 수 있다.

2가지 규칙

1. Marker receiving rule

• 상태를 기록하지 않은 process에게 기록하는 것을 의무화한다.
• 이미 상태를 기록한 process가 marker 를 수신하면, 해당 채널 상태는 저장된 후 수신한 메시지 세트로 기록된다.

1. Marker sending rule

• 프로세스가 상태를 기록한 후 다른 메시지를 보내기 전에 marker 를 전송해야 한다.

Snapshot algorithm Example