램포트의 logical clock

• 메시지를 주고받는 이벤트가 인과관계가 맞게하는 것이다. 시간을 조정해줌

Mutual Exclusiuon(상호배제) 알고리즘

1. Centralized 알고리즘
   • 한가지 프로세서가 코디네이터 역할을 한다.
   • 리소스 접근 시 코디네이터에게 리퀘스트 메시지를 보낸다.
   • 크기가 커지면 하나의 코디네이터에 부담이 커져 코디네이터가 망가지면 전체 문제가 생기는 단점이 있다.
   • 그러나 접근하는데 대기시간이 가장 짧다.
2. Decentralized 알고리즘
   • 코디네이터를 여러개 두는 방법이다.
   • 과반수 허락을 받아야 권한을 받게하며, 코디네이터가 한개일때보다 취약성이 낮다.
   • 과반수를 아무도 얻지 못할 수 있어 Starvation과 낮은 효율성의 단점이 있다.
3. Distributed 알고리즘
   • 코디네이터를 두지 않는 알고리즘이다.
   • 모든 프로세스들이 참여하며 코디네이터를 따로 두지 않아도 되는 장점이 있지만, 한 프로세스라도 따르지 않으면 문제가 발생할 수 있다.
   • 트래픽이 길수있고 딜레이 시간이 가장 길다.
4. Token-ring 알고리즘
   • 수건돌리기처럼 돌아가면서 token을 돌리는 방식이다.
   • 자신에게 토큰이 오는 것을 보장할 수 있다.
   • 그러나 토큰을 계속 돌려야하는 부담이 있고, 토큰을 잃어버릴 부담이 있다.

Election Algorithms(선출 알고리즘)

1. Bully Algorithm
   • 프로세스에 넘버를 가지고, 코디네이터가 없는 것을 발견한 프로세스가 election message를 제안한다.
   • 그래서 발견한 프로세스의 higher number중에 선택하고 아무도 없으면 발견한 프로세스가 코디네이터로 선출되는 방법이다.
2. Ring Algorithm
   • 어떤 프로세스가 코디네이터가 없는 것을 발견하면, 옆 프로세스에게 election message를 보내고 링을 돌아서 자신에게 돌아오면 이 발견한 프로세스가 선출되는 방법이다.