Tem thời gian là 1 phần dùng để đồng bộ đồng hồ logic (nghĩa là đồng bộ giữa các sự kiện với nhau).

a. Tem thời gian Lamport

Để đo thời gian tương ứng với sự kiện x thì ta gán một giá trị C(x) cho sự kiện đó và thỏa mãn các điều kiện sau:

Nếu A --> B trong cùng một tiến trình thì C(A) < C(B).

Nếu A và B biểu diễn tương ứng việc gửi và nhận một thông điệp thì ta có C(A)< C(B)

Với mọi sự kiện phân biệt (không có liên quan) thì C(A)<>C(B)

Ví dụ : trong sách, trang 257, nói đơn giản là : khi gửi thông điệp thì bên gửi gửi kèm theo nhãn thời gian của nó, nếu tại nơi nhận thời gian trên nhãn thông điệp lớn hơn thời gian tại nơi nhận thì chỉnh lại thời điểm nhận đó là (thời gian gửi+1) (ít nhất) để đảm bảo yêu cầu của thuật toán.

b. Tem thời gian Vector :

Giải thuật vector timestamp đưa ra một vetor timestamp VT(a) gán cho sự kiện a có thuộc tính là nếu VT(a) < VT(b) thì sự kiện là nguyên nhân của b.

Trong vector thời gian mỗi tiến trình Pi lưu giữ một Vi với giá trị N (các tiến trình khác nhau thì N khác nhau)

- Vi là số các sự kiện đã xảy ra tại Pi

- Nếu Vi[j] = k nghĩa là Pi biết đã có k sự kiện đã xẩy ra tại Pj

Yêu cầu: mỗi khi có sự kiện mới xảy ra ở tiến trình Pi thì phải tăng Vi và phải đảm bảo vector này được gửi cùng thông điệp suốt trong quá trình.

Nhờ đó bên nhận sẽ biết được đã có bao nhiêu sự kiện xảy ra tại Pi .Quan trọng hơn phía nhận sẽ báo cho biết là đã có bao nhiều sự kiện ở các tiến trình khác đã xảy ra trước khi Pi gửi thông điệp m.Nói cách khác timestamp VT của n nói cho bên nhận biết bao nhiêu sự kiện đã xảy ra trong các tiến trình khác trước m.

Luật cập nhật vector

- Thiết lập Vi[j] =0 với mọi j,i

- Sự kiện xảy ra ở Pi là nguyên nhân tăng Vi

- Pi gắn một timestamp t=V vào mọi thông điệp gửi đi

- Khi Pi nhân được một thông điệp có t nó sẽ thiết lập

Vi[j]=Max(Vi[j] ,t[j]) và tăng Vi

Giải thích:

Chỉ nói về "Tem thời gian Lamport" thôi nhé (vì cái kia ko có ví dụ không chơi). Cái ví dụ chính là cách nó hoạt động. Giả sử có 2 máy với thời gian logic là khác nhau.

- Nếu với 2 tiến trình trong 1 máy --> cứ thế thực hiện theo tem thời gian là mốc thời gian của đồng hồ logic của máy đó.

- Khi 1 message được gửi, sender sẽ gửi cùng tem thời gian của thông điệp đó (tức là thời gian lúc gửi).

- Tại nơi nhận, receiver so sánh giữa nhãn thời gian của thông điệp với thời gian logic trên máy, nếu thời gian logic trên máy lớn hơn --> đặt thời gian nhận là thời gian logic trên máy (sự kiện nhận). Nếu ngược lại thì đặt thời gian nhận là thời gian gửi+1 (ít nhất là 1 còn chính xác là cộng thêm 1 gia số nào đó), đồng thời đặt lại thời gian logic=thời gian nhận, tiếp tục thực hiện công việc.

--> Có thể đồng bộ thời gian logic giữa các máy (đảm bảo thứ tự các sự kiện xảy ra)

Tem thời gian Vector đặt ra để khắc phục nhược điểm của Lamport là không cho biết được mối quan hệ giữa 2 sự kiện a và b, nghĩa là nếu biết C(a)<C(b) thì không đảm bảo a xảy ra trước b --> tem thời gian vector.