1. Basic Concepts

1-1. Dependability

Dependable system (신뢰할 수 있는 시스템)

Properties

Availability: 지금 바로 사용할 수 있는 확률, 이 순간에 문제 없이 동작될 확률 (%)

Reliability: 문제 없이 연속적으로 사용될 수 있는 시간 (time)

• Mean Time To Failure(MTTF): 하드디스크의 성능을 나타낼 때 많이 사용되는데, 구성 요소가 fail이 날 때 까지의 평균 시간이다. 
• Availability vs Reliability
  
  • 매 시간당 1ms 씩 시스템이 다운된다. (availability: 99.999%, reliability: under 1 hour)
  • 시스템은 일 년에 한 번씩 36일간 다운된다. (availability: low, reliability: high)

Safty: low probability of catastrophes

• fail이 일어나도 재앙이 안 일어나게 한다.
• ex) 원자력 발전소

Maintainability: 얼마나 쉽게 수리/복구 할 수있는지

• high maintainable = high degree of availability 

1-2. Failure Models

1. Crash failures: 서버가 멈췄는데(halt), 멈추기 전에는 정상적으로 동작함
2. Omission fialures: 서버에 어떠한 request가 도착했는데 적절한 응답을 보내지 못하는 상태

• Receive omission: 메시지 받기 실패 - 클라이언트의 요청에 응답 실패
• Send omission 메시지 보내기 실패 - 리퀘스트를 받고 작업도 했지만 어떤 이유에서 응답을 못함.

3. Timing failures: 서버의 output은 맞지만, 주어진 제한 시간 안에 수행하지 못하는 상태

• ex) 스트리밍 비디오 데이터가 제 시간에 도착하지 않음

4. Response failures: 서버의 응답이 요구에 맞지 않음 (incorrect)

• Value failure: 맞지 않은 값이 나옴
  • ex) 웹서치 키워드를 입력했을 때 엉뚱한 결과가 나옴
• State transition failure: 서버는 리퀘스트가 오면 규칙에 따른 응답이 있는데 엉뚱한 리퀘스트가 와서 exception이 발생해 엉뚱한 결과로 빠지는 경우

5. Aribitrary (Byzantine) failures: 서버가 연산에 대한 답을 구했는데 엉뚱한 답이 나오는 경우, 의도적으로 잘못된 결과를 보내는 경우, 원인을 매우 찾기 어렵다.

• ex) 서버는 절대 나올 수 없는 결과를 냈지만 틀렸다는 것을 감지하기 어렵다.
• ex) 결함이 있는 서버는 의도적으로 잘못된 답을 도출하기 위해 악의적으로 같이 작업한다.

참고: Crash failures (least severe) to arbitrary failrues (worst)

1-3. Fault Tolerance를 얻기 위해 failure에 대처하는 방법

Failure가 났다는 사실을 숨긴다. (redundancy)

• Information redundancy
  • FEC(Forward Error Correction): 전송하는 데이터의 패킷 에러를 복구하기 위한 코드
• Time redundancy
  • 다시 수행: retransmission
  • epecially helpful for transient or intermittent faults.
• Physical redundancy
  • Software (프로세스 복제), Hardware

• Triple modular redundancy(TMR)

Q1. A2가 fail 되면?

A1. V1은 A1, A3의 맞는 답을 받았기 때문에 정상적으로 동작한다.

Q2. A2, B1 그리고 C1이 fail 되면?

A2. 각 component에서 하나씩 fail이 나는 것은 상관 없고 정상적으로 동작한다.

Q3. V1이 fail 나면?

A3. V1의 fail은 B1의 fail과 같기 때문에, 상관없이 정상적으로 동작한다.

Q4. V1과 B2가 fail 나면?

A4. 잘못된 값을 얻는다.

Q5. 2개가 오류나도 괜찮으려면?

A5. 5개의 component가 있으면 된다.

2. Process Resilience

failure를 방지하기 위해 프로세스를 복제하여 그룹으로 만들자.

2-1. Process Group

1. 똑같은(identical) 프로세스를 여러 개 두는 것이다.
2. 그룹 내 하나의 프로세스가 fail 되면 다른 것들로 대체 가능하다.
3. 그룹 내 프로세스는 동적이다 : 프로세스는 시스템이 작동하는 동안 그룹에 참여하거나 떠나는 것이 가능하다.
4. 그룹으로 보내진 메시지는 모든 그룹 맴버들이 받는다.
5. 하나의 그룹은 하나의 프로세스(single logical process)로 보여진다.

2-2. Group Organization

1. Flat groups
   • fault tolerance에 좋다: 그룹 맴버들 간의 정보 교환이 즉시 이루어진다.
   • 통제가 완전히 분산되기 때문에 더 많은 오버헤드가 부과될 수 있다.
   • ex) 분산 시스템 에서의 mutual exclusion 
2. Hierarchical groups
   • 모든 대화는 하나의 coordinator를 통한다. (효율적임)
   • fault tolerant, scalable 하지 않지만(coordinator가 fail되면 더 이상 동작하지 않음) 구현이 쉽다.
   • ex) centralized algorithm for mutual exclusion

2-3. Process Replication

그룹 내 프로세스 맴버들은 consistency를 유지해야하기 떄문에 동일한 일을 해야한다.

1. Primary-based protocol
   • heirarchical 구성의 그룹 (초기의 coordinator가 write 작업을 관리한다.)
   • primary 가 붕괴되면 election algorithm을 통해 새로운 primary가 선택된다. (Election by Bullying)
2. Quorum-based protocol
   •  동일한 프로세스의 집합인 flat 그룹
   • no single point of failure

2-4. Groups and Failure Masking

k-fault tolerant 그룹은 k concurrent member failures를 숨기는 것(mask)이 가능하다. (k: degree of fault dolerance)

• 문제점: k-fault tolerant 그룹은 어느 정도의 규모를 필요로 하는가?
  • crash failure semantics: k개의 failure을 견디기 위해서는 총 k+1 맴버가 필요하다.(k개의 프로세스가 망가진다면, 남은 하나가 사용된다.)
  • arbitrary failure semantics, 결과가 클라이언트의 투표로 결정되는 경우 : k개의 failure을 견디기 위해 총 3k+1 맴버가 필요하다.

Byzantine General's Problem

2-5. Failure Detection

• 프로세스 failure 찾기
  • "너 살아있니?" 하고 물어보고 답을 기다린다. (active pinging)
  • 혹은 alive message를 패시브하게 기다린다.
• timeout 매커니즘을 통해 찾기
  • timeout을 적절하게 정하는 것은 어렵고 애플리케이션에 따라 다르다.
  • False positive: network failure과 process failure를 구별하는 것은 쉽지않다.
  • Solution: Gossiping/active probing: 그룹 내 이웃끼리 정기적으로 정보를 주고받는다. "나 살아있어~" "너 살아있니~?"

3. Reliable Client-Server Communication

3-1. Reliable Communication

• Error detection
  • bit 에러를 찾아낼 수 있도록 패킷의 구조를 구성하며 checksum (e.g. CRC)을 이용한다.
  • frame numbering (프레임에 번호를 붙임)을 하여 packet lost를 감지
• Error correction
  • redundancy bits를 추가하여 패킷의 손상을 자동으로 고침 (네트워크 상에서는 bit error가 발생할 확률이 높다. error correction code를 이용해 복구 가능하게 한다.)
  • 잃어버린 패킷의 retransmission을 요청한다.

3-2. Reliable RPC

Remote Procedure Call (RPC): remote procedure call을 숨겨서 로컬에서 작동하는 것 처럼 보이게 한다. (client stub/server stub)

에러가 발생하면 local과 remote call의 다른점을 숨기기가 항상 쉬운 일만은 아니다.

발생 가능 문제

1. Client cannot locate server
   
   • 모든 서버가 다운되었거나 업그레이드 되었을 때
2. Client request is lost
   • OS 혹은 클라이언트 stub이 요청을 보내면서 타이머를 시작
   • 응답이 오기 전에 타이머 만료되면 요청을 재전송(retransmit) : TCP 단계에서 retransmission과 다른 것임
   • 너무 많은 요청을 잃어버리면 클라이언트는 포기함..
3. Server crashes
   
   • 
   • (a) normal case, (b) Crash after execution, (c) Crash before execution
   • 서버 크래쉬는 서버가 일을 실행시킨 후 발생했는지 전인지 알기 힘들다.
   • 문제점: 서버가 기대하는 상황을 정할 필요가 있다.
     • At-least-once-semantics: The server guarantees it will carry out an operation at least once, no matter what. 적어도 한 번은 실행시켜야하므로 리퀘스트를 보내야한다. 두 번 실행되도 괜찮기 때문.
     • At-most-once-semantics: The server guarantees it will carry out an operation at most once, but possibly none at all. 최대 한 번만 수행해야하므로 리퀘스트를 보내지 않는다.
   • Example
     • Printing Server
     • Assumption
     • Server strategy
     • Client strategy
     • 설명 추가 필요
4. Server response is lost
   • 클라이언트 입장에서는 리퀘스트를 잃어버린건지 서버에 문제가 있는 것인지 알 수 없다. Time out으로 밖에 찾아낼 수 없음
   • sequence number로 해결 가능
5. Client crashes 
   • orphan process: RPC가 이중, 삼중으로 겹칠 수 있는데 리소스를 lock한 상태라면 다른 프로세스도 쓰지 못함
   • 클라이언트가 reboot되어서 새로운 메시지를 보내면 기존의 orphan process는 종료
   • Time out을 둔다. 일정 시간동안 응답이 없으면 죽임.

4. Reliable Group Communication

그룹 내 프로세스는 synchronization, replication 등등의 작업을 할 것이다. 이들 사이의 reliable한 통신이 가능하게 하려면?

Unicast vs Multicast vs Broadcast

4-1. Reliable Multicast

부연 설명 필요

ACK을 사용할 때 문제점: ACK implosion
NACK만 사용하는 것으로 해결 (scalability)
NACK을 사용할 때 문제점: 언제까지 데이터 패킷을 가지고 있어야하는지 알 수 없다, NACK implosion이 발생할 수 있다.
SRM으로 해결 (random delay만큼 기다려서 NACK을 multicast함)

Hierarchical Feedback Control

multicast를 scalable하게 하기 위해

붙어있는 이웃 노드와 ACK을 주고받는다.

ACK-based

NACK-based

Receiving vs Delivering a message

Receiving: Network layer에서 받음

Delivering: 패킷을 풀어서 Application layer로 전달함

문제점: Process failures

해결방안: Atomic Multicast (Virtually synchronous, Message ordering)

모두 제대로 된 정보를 받거나, 모두 받지 못하면 된다.

4-2. Virtually synchronous

어떠한 protocol이 동작하여 프로세스가 crash되었는지 아닌지 확인하여 모든 프로세스가 제대로 받았으면 deliver하고, 하나의 프로세스라도 crash가 나면 모든 프로세스에서 deliver하지 않는다.

모든 프로세스에 전달하지 않는 것은 reliable하다. why? Atomic multicast이기 때문

Virtual Synchrony

Group view: 그룹 내 모든 프로세스는 multicast가 끝날 때 까지 같은 view를 가지고 있어야한다.

View change: 프로세스가 그룹에 참여하거나 빠질 수 있다, multicast 중간에는 view change가 일어날 수 없다, multicast가 일어나지 않을 때만 발생함.

4-3. Message ordering

virtual synchronous와는 독립적으로, deliver 순서 결정시 사용.

Unordered multicasts

FIFO-ordered multicasts

같은 프로세스에서 보낸 순서 그대로 다른 프로세스로 받아야한다. (다른 프로세스에서 보낸 것은 제한이 없음)

Causally-ordered multicasts

happened-before 관계의 causally related한 순서가 있다면 그 순서대로 받아야한다.

FIFO-ordered가 전제로 있어야함. 즉, Causally related 되었다면 FIFO도 되는 것이다.

Causal ordering이 되었다고 total ordering이 될 수는 없다.

Totally-ordered multicasts

보낸 순서에 관계없이 받은 순서가 같아야한다.

Atomic Multicast

Multicast	Basic message ordering
Reliable multicast	None
FIFO multicast	FIFO-ordered delivery
Causal multicast	Causla-ordered delivery
Atomic multicast	TO-ordered

(1) FIFO? Irrlevant

(2) Causal? NO, happened-before relationship: M1->M2 성립 안함

(3) Total? NO, 모든 프로세스에서 다른 순서로 보고 있기 때문에 성립 안함

(1) T1과 T2는 Totally ordered? YES, 모든 프로세스가 T2->T1 순서로 받음

(2) F1과 F2는 FIFO-related messages? YES 같은 프로세스에서 보낸 순서가 맞아야하므로 F1->F2 순서로 보나 보면 된다. 

(3) C1와 C3는 Causally realated message? YES happened-before: C1->C2, C1->C3

(4) C1,C2,C3는 Totally ordered? NO

5. Distributed Commit

5-1. 2-phase Commit (2PC)

하나의 coordinator, N개의 worker

Coordinator는 모든 worker들에게 commit 되냐구 물어본다.(VOTE-REQ)

모든 worker로부터 VOTE-COMMIT을 받으면 GLOBAL-COMMIT 을 방송한다.

한 명이라도 보내지 않으면 GLOBAL-ABORT

5-2. 3PC