Xóa bỏ các thực thể không còn được tham chiếu (Unreferenced Entities)

Mỗi lần client tạo(xóa) một tham chiếu đến một đối tượng O, một bộ đếm tham chiếu sẽ tăng thêm (giảm đi).

Skeleton duy trì một danh sách tất cả các proxy trỏ đến nó.

Ở đây đưa ra khái niệm Idempotent operation là một thao tác nó có thể lặp đi lặp lại nhiều lần mà không ảnh hưởng đến kết quả ( ví dụ 1*1=1).

Thông điệp để thêm/xóa một proxy của danh sách cũng gần giống như tăng/giảm bộ đếm tham chiếu.

Các thực thể chuyển tham chiếu cho các thực thể khác nhưng không thể lấy được từ root.

Tập hợp loại bỏ dựa trên cơ sở truy nguyên: kiểm tra những phương thức có thể lấy được từ root và remove

Trong hệ phân tán,mỗi máy tính là một đồng hồ nên việc đồng bộ các đồng hồ này là rất cần thiết và rất khó khăn.

Chúng ta có nhiều cách để xác định thời gian.Phổ biến nhất là các hệ đếm thời gian theo thiên văn và ở đây là mặt trời.Có 23h một ngày và 3600 giây.Một giây mặt trời được tính là 1/8600 của một ngày mặt trời.Một trong những mô hình để tính thời gian áp dụng phương pháp trên là Internatinal Atomic Time viết tắt là TAI. Tuy nhiên, TAI lại có một vấn đề là cứ 86400TAIs sẽ có 3ms chậm hơn so với đồng hồ mặt trời.

Để thống nhất thời gian vật l‎ người ta đã đưa ra khái niệm thời gian phối hợp toàn cầu UCT (Universal Coordinate Time). Viện chuẩn quốc gia Mỹ đã lập ra trạm phát radio sóng ngắn W W V để gửi UTC khi cần hoặc định kì.

5.1.2 Các giải thuật đồng bộ hóa vật lý (Clock synchronization algorithm).

Nếu tất cả các máy tính đều có WWV Receiver thì việc đồng bộ chúng là dễ dàng vì tất cả đều cùng đồng bộ với giờ chuẩn quốc tế UTC.Tuy nhiên khi không có WWV thì việc đồng bộ được thực hiện bằng các giải thuật đồng bộ sau.

Giả sử trong hệ phân tán có một máy có WWV (gọi là Time server ) và chúng ta sẽ tiến hành đồng bộ các máy khác với máy này.Trong khoảng thời gian δ/2p mỗi máy sẽ gửi một thông điệp đến máy chủ hỏi thời gian hiện tại. Máy chủ nhanh sẽ phản hồi bằng một thông điệp mang giá trị thời gian C(utc).Bên gửi nhận được phản hồi nó sẽ thiết lập lại clock thành C(uct).

Hình 25 . Xác định thời gian trong time server

- Một là nếu clock bên gửi chạy nhanh thì lúc này C(uct) sẽ nhỏ hơn thời gian hiên tại C của bên gửi..Có thể giải quyết bằng cách thay đổi nhịp ngắt lại nhanh hơn hoặc chậm hơn cho đến lúc khớp nhau.

- Hai là sự chênh lệch từ lúc C(uct) được gửi cho đến lúc nhận được có thể gây lỗi.Giải quyết bằng cách ghi nhận khoản thời gian giữa lúc gửi và nhận
b. Giải thuật Berkeley.

Tư tưởng của giải thuật:

Server sẽ chủ động cho các máy khác biết thời gian chuẩn của mình C_UTC sau đó sẽ yêu cầu thông tin về thời gian của các client.

Client sẽ trả lời khoảng thời gian chênh lệch giữa nó và server.

Server sẽ tính khoảng thời gian mà các client so với thời gian chuẩn của server lúc đó và gửi cho các máy khách cách điều chỉnh thời gian cho phù hợp.

Hình 26 . Đồng bộ theo giải thuật Berkeley

Giải thuật này thực hiện chia thời gian thành những khoảng đồng bộ cố định. Khoảng thời gian I sẽ bắt đầu từ thời điểm (To + i.R) và chạy đến khi To+(i+1)R với To là thời điểm xác định trước và R là một biến hệ thống .

Vào thời điểm bắt đầu của mỗi lần đồng bộ tất cả các máy của mạng sẽ broadcast thời gian của mình .

Sau khi broadcast nó sẽ bắt đầu thu thập thời gian mà các máy khác gửi đến trong khoảng thời gian S. Sau đó bỏ đi giá trị lớn nhất và nhỏ nhất rồi tính trung bình của các giá trị thời gian còn lại.

Trong nhiều trường hợp, giữa các tiến trình không nhất thiết phải phù hợp theo thời gian thực tế mà chỉ cần khớp với nhau về thời gian. Do đó người ta đưa ra khái niệm đồng hồ

logic.
5.2.1 Nhãn thời gian Lamport (Lamport timestamps).

Lamport đã đưa ra mô hình đồng hồ logic đầu tiên cùng với khái niệm nhãn thời gian.

Khi có A B : A xảy ra trước B thì tất cả các tiến trình trong hệ phân tán thỏa thuận sự kiện A xảy ra trước rồi đến sự kiện B.

A và B là hai sự kiện của cùng một tiến trình. Nếu A xảy ra trước B thì AB là đúng.

Nếu A là sự kiện bản tin được gửi bởi một tiến trình nào đó, còn B là sự kiện bản tin đó được nhận bởi một tiến trình khác thì quan hệ A B là đúng.

Quan hệ xảy ra trước có tính bắc cầu: A B , B C thì A C.
b. Tem thời gian (Time Stamps)

Để đo thời gian tương ứng với 4 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)
5.2.2 Vector thời gian (Vector Timestamps)

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 Vtt(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[i] 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[i] 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[i]

- Pi gắn một timestamp t=V[i] 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[i]
5.3 Trạng thái tổng thể (Global sate).

Việc xác định trạng thái tổng thể của hệ thống rất có ích. Một trong những phương pháp được đưa ra là Chụp Nhanh Phân Tán (Distributed Snapshort) cùng khái niệm lát cắt (cut).

Hình 28 .(a) Lát cắt nhất quá. (b) Lát cắt không nhất quán

Một lát cắt nhất quán được biểu diễn là đường chấm gạch trong hình a. Lát cắt mô tả sự kiện cuối cùng mà sự kiện này được ghi lại cho mỗi tiến trình. Bằng cách này nó có thể kiểm tra lại rằng tất cả các thông điệp nhận đều tương ứng với các thông điệp gửi được ghi lại trên đường cắt. Ngược lại là lát cắt không nhất quán như hình vẽ b: Thời điểm tiến trình P_­3 nhận thông điệp m₂ được ghi vào lát cắt nhưng việc ghi lại này không tương ứng với sự kiện gửi.