Bài giảng Đồng bộ hóa (Synchronization)

Chương 6 : Đồng bộ hóa (Synchronization) Trong chương này chúng ta sẽ tìm hiểu bằng cách nào các tiến trình đồng bộ hóa được với nhau. Ví dụ, thay vì nhiều tiến trình đồng thời truy nhập vào một tài nguyên chia sẻ thì chúng cấp quyền truy nhập tạm thời cho nhau. Một ví dụ khác, nhiều tiến trình đôi khi cần trả lời cho 1 sự kiện nào đó, nói cách khác, cần xác định thông điệp m1 của tiến trình P được gửi trước hay sau thông điệp m2 cùa tiến trình Q. Đồng bộ hóa trong các hệ thống phân tán thường khó hơn rất nhiều so với đồng bộ hóa trong các hệ đơn hoặc đa xử lý. Vấn đề trong chương này hướng tới đồng hộ hóa dựa trên thời gian hoạt động, tức là thời gian có tính tương quan giữa các tiến trình hơn là thời gian tuyệt đối. Trong nhiều trường hợp, đồng bộ hóa có thể được giải quyết bằng cách một nhóm các tiến trình có thể sử dụng 1 tiến trình được thực thi bằng cách lấy trung bình một vài thuật toán lựa chọn. 6.1 Đồng bộ hóa đồng hồ (Clock Synchronization). Trong một hệ tập trung, thời gian hệ thống là rõ ràng. Khi một tiến trình muốn biết thời gian hệ thống, nó chỉ cần đưa ra 1 lời gọi hệ thống và đợi kernel trả lời. Nếu tiến trình A hỏi thời gian, ngay sau đó tiến trình B hỏi thời gian, thì thời gian mà B nhận được sẽ lớn hơn(đôi khi bằng) so với thời gian mà A nhận được. Chắc chắn không bao giờ có chuyện thời gian B nhận được nhỏ hơn A. Nhưng trong một hệ thống phân tán, đạt được sự thống nhất về thời gian như vậy không hề đơn giản. Hãy lấy 1 ví dụ đơn giản trong chương trình make của Unix. Thông thường thì trong Unix, các chương trình lớn được chia nhỏ ra nhiều file nguồn, để khi có thay đổi trong 1 file nguồn thì chỉ có file đó phải được biên dịch lại mà không phải là tất cả chương trình. Nếu 1 chương trình có 100 files, thì không nhất thiết phải biên dịch lại toàn bộ bởi 1 file bất kì thay đổi với tốc độ cao hơn bất kì 1 người lập trình nào có thể làm việc. Lệnh make làm việc hết sức đơn giản. Khi lập trình viên thay đổi file nguồn và chạy lệnh make thì thời điểm đó được đánh dấu cho tất cả các file nguồn đã bị modify. Nếu file input.c có thời gian là 2151 và file đối tượng tương ứng của nó output.o có thời gian là 2150 thì lệnh make hiểu rằng input.c đã bị thay đổi sau khi output.o được tạo ra. Như vậy cần phải biên dịch lại input.c để cho ra phiên bản output.o mới. Trong trường hợp khác, nếu thời gian của output.o là 2144 còn thời gian của input.c là 2143 thì không cần biên dịch lại file này. Như vậy lệnh make kiểm tra lại toàn bộ file nguồn và chỉ gọi trình biên dịch biên dịch những file cần thiết. Bây giờ hãy tưởng tượng những gì xảy ra trong một hệ phân tán cũng với lệnh make như trên. Nếu hệ thống không đạt được sự thống nhất về thời gian, sự việc sẽ xảy ra như trong sơ đồ sau: File output.o có thời gian là 2144, và gần như ngay sau đó, input.c bị thay đổi nhưng lại được đánh dấu thời gian là 2143 vì đồng hồ trên máy đó chậm hơn 1 chút. Do đó lệnh make sẽ không gọi trình biên dịch. Kết quả là chương trình được biên dịch ra lẫn lộn giữa các đối tượng từ file nguồn cũ và mới. Dẫn đến có lỗi trong chương trình mà lập trình viên không thể kiểm soát hoặc hiểu được. Có rất nhiều trường hợp tương tự mà ở đó việc tính toán thời gian chính xác là cần thiết. Trường hợp trên có thể được giải quyết dễ dàng bằng cách gán tem(filestamp). Thêm nữa, rất nhiều lĩnh vực cần tới việc định thời gian chính xác như môi giới tài chính, kiểm toán... Như vậy hiển nhiên là việc định thời chính xác là cực kì quan trọng. Hãy bắt đầu với một câu hỏi đơn giản: Có thể đồng bộ toàn bộ các đồng hồ trong 1 hệ phân tán không? Câu trả lời cho nó lại cực kì phức tạp. 6.1.1 Đồng hồ vật lý (Physical Clock): Gần như tất cả các máy tính đều có mạch tính thời gian. Mặc dù có thể gọi chúng là clock theo nghĩa rộng của từ này, thì thực sự chúng không hẳn là “đồng hồ” theo cách mà hệ thống sử dụng. Có lẽ từ thích hợp hơn với những mạch này là Timer(mạch định thời). Một mạch định thời sử dụng một tinh thể thạch anh đặc biệt. Khi được đặt vào một điện áp, tinh thể thạch anh này sẽ dao động với một tần số xác định tùy thuộc vào loại tinh thể, hình dáng khi cắt và điện áp đặt vào. Với mỗi tinh thể, có hai thanh ghi tương ứng là counter vả holding. Thanh ghi đếm sẽ giảm đi 1 bit với mỗi dao động của tinh thể. Khi thanh ghi đếm về 0, mạch sẽ gọi 1 ngắt để nạp lại giá trị mới cho thanh ghi đếm từ thanh ghi holding. Như vậy việc lập trình cho một mạch định thời chạy dưới một tần số bất kì là hết sức dễ dàng. Mỗi 1 ngắt trong mạch như vậy gọi là 1 clock tick(nhịp đồng hồ). Khi hệ thống được khởi động, nó thường yêu cầu người dùng nhập ngày tháng và thời gian, rồi chuyển đổi thành số nhịp tương ứng tính từ 1 thời điểm xác định lưu trữ trong bộ nhớ. Hầu hết các máy tính có 1 CMOS RAM chạy pin làm nhiệm vụ back up thời gian để mỗi lần khởi động sau đó không cần phải nhập nữa. Với mỗi nhịp đồng hồ, thủ tục ngắt cộng thêm 1 vào thời gian trong bộ nhớ. Bằng cách này, đồng hồ(của phần mềm) được cập nhật. Với một máy tính đơn lẻ và một đồng hồ đơn lẻ, việc đồng hồ chạy sai hoặc ngừng một thời gian không phải vấn đề gì lớn lắm. Vì tất cả tiến trình trên máy sử dụng chung một đồng hồ nên chúng có sự thống nhất. Khi hệ thống đa xử lý ra đời, mỗi 1 CPU có đồng hồ riêng, tình thế đã thay đổi hoàn toàn. Mặc dù tần số dao động của các tinh thể thường khá là ổn định, nhưng thật khó để cho các tinh thể khác nhau dao động cùng 1 tần số. Trong thực tế, khi một hệ thống có n máy tính, tất cả n tinh thể hầu như dao động với n tần số khác nhau, làm cho đồng hồ(của phần mềm) dần dần cách xa nhau về mặt thời điểm và cho các giá trị khác nhau. Sự sai khác này gọi là clock skew(sự sai lệch đồng hồ). Hậu quả của sự sai lệch này là các chương trình dựa vào thời gian được gán cho file, đối tượng, tiến trình hoặc thông điệp độc lập với máy sinh ra chúng có thể bị lỗi, như ví dụ với lệnh make ở trên. Trong một số hệ thống(ví dụ như các hệ thống thời gian thực), thời gian hiện tại là rất quan trọng. Chính vì thế việc sử dụng các đồng hồ vật lý bên ngoài là cần thiết. Vì các lý do hiệu suất và độ phức tạp, việc phát triển một hệ thống các đồng hồ vật lý như vậy đặt ra 2 vấn đề lớn: (1) Làm sao để đồng bộ chúng với các đồng hồ thực tế trên thế giới, và (2) làm sao để đồng bộ chúng với nhau? Trước khi trả lời các câu hỏi trên, hãy xem xét sơ qua làm sao chúng ta đo được thời gian. Ban đầu, người ta tính thời gian dựa trên sự dịch chuyển của mặt trời trên bầu trời(vốn dĩ do sự tự quay quanh trục của trái đất). Theo đó, khoảng thời gian giữa 2 lần mặt trời xuất hiện liên tiếp ở cùng 1 vị trí được gọi là ngày mặt trời. Mỗi một ngày mặt trời được chia ra làm 86400 giây mặt trời. Như mô tả của hình dưới đây: Vào những năm 40 của thế kỉ trước, người ta phát hiện ra rằng sự quay của trái đất là không ổn định. Theo đó, trái đất đang quay chậm dần đều dưới tác động ma sát của thủy triều và bầu khí quyển. Dựa vào các mẫu vật san hô cổ đại, các nhà địa chất tin rằng 300 triệu năm trước một năm có tới 400 ngày(hơ hơ, thế thì 1 ngày chỉ có vỏn vẹn 22 tiếng). Thực tế thì khoảng thời gian của 1 năm hầu như ko đổi(chính là khoảng thời gian trái đất quay 1 vòng quanh mặt trời); nhưng độ dài của 1 ngày đã bị thay đổi. Thêm nữa, sự bất ổn trong nhân trái đất vốn cấu thành từ kim loại nóng chảy cũng gia tăng độ thiếu tin cậy trong cách tính thời gian này. Người ta đành đo khoảng thời gian của 1 số cực lớn các ngày, lấy trung bình và chia khoảng thời gian trung bình đó ra làm 86400 giây mặt trời. Vào năm 1948, phát minh ra đồng hồ nguyên tử đã làm cho việc đo thời gian chính xác hơn rất nhiều, đồng thời tách khái niệm thời gian ra khỏi sự vận động của trái đất. Đồng hồ nguyên tử hoạt động dựa trên cơ sở đếm số dao động trạng thái của nguyên tử Cesium(Cs) 133(số lần chuyển tiếp giữa hai mức trạng thái năng lượng). Mỗi 1 giây, nguyên tử Cs dao động 9 192 631 770 lần. Hiện tại, một vài phòng thí nghiệm rải rác trên thế giới có đồng hồ Cs 133. Các phòng thí nghiệm này định kì gửi kết quả đến Ủy ban giờ quốc tế(BIH) đặt tại Paris, BIH sẽ lấy trung bình các kết quả này để đưa ra Giờ nguyên tử quốc tế(TAI). Giá trị TAI này là số dao động của đồng hồ Cs 133 tính từ nửa đêm ngày 1 tháng 1 năm 1958 đến nay chia cho 9 192 631 770. Tuy nhiên, vấn đề đặt ra ở đây là TAI tuy chính xác tuyệt đối nhưng lại “trượt pha” so với giờ mặt trời. Hiện tại, cứ 86400 giây TAI lại ít hơn so với ngày mặt trời thực tế là 3 mili giây. Sử dụng TAI đồng nghĩa với việc chúng ta chấp nhận rằng sau mỗi năm, buổi trưa sẽ đến càng lúc càng sớm hơn(12h trưa mà vẫn chưa đứng bóng). (cái ví dụ về Giáo hoàng Gregory hơi chuối củ và quá xa chủ đề, tốt nhất là quên nó đi và công nhận Tanenbaum quá đỉnh ở MIT) BHI giải quyết vấn đề này bằng cách đưa ra khái niệm nhảy giây(leap seconds-cấm nhầm với trò chơi con gái nhá). Tức là khi khoảng cách giữa TAI và thời gian mặt trời đạt tới 800 mili giây, sẽ có 1 bước nhảy như mô tả trong hình sau: Bước nhảy này giúp cho thời gian khoa học vẫn chính xác, nhưng lại không bị lệch đi so với thời gian mặt trời(đại loại như năm nhuận ý ạ). Hệ thống này được gọi là Giờ thống nhất vũ trụ(Universal Coordinate Time)-UTC. UTC là cơ sở cho mọi hệ thống định giờ hiện đại thay thế cho hệ thống giờ thiên văn quốc tế GMT. Hầu hết các công ty điện tử lớn đồng bộ các đồng hồ 60 hoặc 50Hz với giờ UTC, do vậy khi BIH cho thời gian nhảy giây 1 bước, các công ty này chỉ cần nâng tần số lên 61 hoặc 51 Hz. Kể từ khi 1 giây trở nên là 1 khoảng thời gian đáng kể so với hoạt động của 1 máy tính thì hệ điều hành của nó cần duy trì sự chính xác của thời gian qua hàng năm trời. Để làm được điều này, hđh cần có 1 phần mềm đặc biệt chuyên tính toán số giây phải nhảy. Viện thời gian chuẩn quốc gia NIST của Mỹ đã lập ra một trạm phát sóng ngắn, tạm gọi là WWV tại Fort Collins, Colorado để cung cấp thời gian UTC chính xác. WWV phát ra một xung ngắn ứng với mỗi giây UTC. Sai số của xung này tại nguồn là vào khoảng 1 mili giây, nhưng dưới điều kiện bầu khí quyển thì sai số thực tế của nó là 10 mili giây. Một vài quốc gia khác cũng có các trạm phát sóng như vậy. GEOS là một hệ thống vệ tinh địa tĩnh cũng cung cấp dịch vụ tương tự. 6.1.2 Hệ thống định vị toàn cầu GPS: Hãy xem xét một ví dụ cụ thể: hệ thống định vị toàn cầu GPS. GPS sử dụng 29 vệ tinh địa tĩnh ở độ cao xấp xỉ 20 000km trên mỗi vòng quỹ đạo trái đất nhằm xác định chính xác vị trí của một đối tượng. Mỗi vệ tinh có khoảng 4 đồng hồ nguyên tử tường xuyên cập nhật với các trạm mặt đất. Một vệ tinh tiếp tục thông báo vị trí của chúng và gán nhãn thông điệp với thời gian hiện tại(giờ địa phương mà đồng hồ trên vệ tinh thông báo). Điều này cho phép máy nhận thông điệp có thể tính toán chính xác vị trí của nó chỉ với 3 vệ tinh “trên đầu”. Ý tưởng của hệ thống như sau: các vệ tinh địa tĩnh được bố trí trên quỹ đạo 20,000km so với mặt đất; mỗi vệ tinh có từ 1 đến 4 đồng hồ nguyên tử nhằm đảm bảo giờ địa phương của nó luôn chính xác, các đồng hồ này còn luôn được đồng bộ với các trạm đặc biệt trên mặt đất, tóm lại giờ của nó là giờ UTC; một thiết bị GPS khi yêu cầu xác định vị trí sẽ nhận được các thông điệp từ vệ tinh có chứa nhãn thời gian thông báo giờ hiện tại trên vệ tinh và tọa độ của vệ tinh với hệ kinh vĩ tuyến trái đất. Giờ của mỗi vệ tinh giúp thiết bị tính được khoảng cách giữa nó và vệ tinh bằng cách trừ đi giờ hiện tại trên thiết bị và nhân với vận tốc sóng truyền tới(vận tốc ánh sáng). Tọa độ của thiết bị là 1 bộ 3 số có thể được tính dựa vào thông tin nhận về từ ít nhất 3 vệ tinh, theo lý thuyết. 6.1.3 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. a. Giải thuật Cristian 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 . Xác định thời gian trong time server Đánh giá: giải thuật này có 2 vấn đề : - 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 CUTC 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 . Đồng bộ theo giải thuật Berkeley c. Giải thuật trung bình sử dụng cho các mạng không dây Giải thuật này sử dụng trong giao thức RBS. 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. 6.2 Đồng hồ logic (Logical Clock) 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. 6.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. a. Xét định nghĩa mối quan hệ “xảy ra trước” (à) 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) 6.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] 6.3 Loại trừ lẫn nhau Nguyên tắc cơ bản của hệ phân tán là sự đồng thời và cộng tác của những đa tiến trình. Trong nhiều trường hợp , điều này có nghĩa là những tiến trình cần truy cập cùng một lúc cùng một tài nguyên. Để tránh điều này giải pháp là cho phép xử lý truy cập theo kiểu lọai trừ lẫn nhau. Thuật toán Phân tán loại trừ lẫn nhau có thể được phân lớp thành 2 giải pháp khác nhau: giải pháp loại trừ lẫn nhau theo biểu tượng và permission-base solution. A. Phương pháp thứ nhất đạt được bằng cách đưa ra một thông điệp đặc biệt giửa các tiến trình, được gọi là biểu tượng – token. Chỉ có 1 token sẵn sang và ai là người có token này được phép truy cập đến tài nguyên chia sẻ. Phương pháp này có một số đặc tính quan trọng. + Đầu tiên là nó phụ thuộc vào các làm thế nào để tổ chức các tiến trình, những đặc tính này dễ dàng bảo đảm cho mọi tiến trình có một sự thay đổi trong cách truy cập tài nguyên. Nói cách khác, những đặc tính này tránh sự thiếu tài nguyên + Do deadlock ,tiến trình phải đợi những tiến trình khác để được xử lý, có thể tránh deadlock một cách dễ dàng bằng cách đóng góp vào sự đơn giản của các tiến trình. Không may là trở ngại chính của token-base solution lại nghiêm trọng hơn, một chương trình con phức tạp được phân phối cần được chạy để chắc chắn rằng một token mới đựoc tạo ra nhưng cái chính là token đó phải token duy nhất Phương pháp thứ 2: một tiến trình muốn truy cập vào tài nguyên thì phải được sự cho phép của các tiến trình khác. Có nhiều cách để có được sự cho phép và được chỉ ra dưới đây Thuật toán tập trung: Cách dễ hiểu nhất để đạt được sự loại trừ lẫn nhau trong hệ thống phân tán là giả lập cách nó thực hiện trong hệ thống một Bộ xử lý. Một tiến trinh được bầu như một bộ điều phối. Bất cứ lúc nào một tiến trình muốn truy cập những tài nguyên chia sẻ, nó gửi một thông điệp yêu cầu tới bộ điều phối đang thống kê xem loại tài nguyên nào mà tiến trình muốn truy cập và xin phép truy cập. Nếu như không có tiến trình nào đang truy cập tào nguyên, bộ điều phối sẽ gửi lại tiến trình xin phép một thông điệp cho phép truy cập hệ thống Ưu điểm và tính chất: Dễ dàng thấy rằng giải thuật đảm bảo sự loại trừ lẫn nhau: bộ điều phối chỉ để một tiến trình truy cập tài nguyên trong 1 thời điểm. Điều này khá tốt nếu các yêu cầu được chấp nhận theo thứ tự mà chúng được nhận. Không có tiến trình nào phải đượi vô thời hạn. Sự xắp xếp này dễ thực thi và chỉ yêu cầu 3 thông điệp cho mỗi lần sử dụng tài nguyên (gồm: yêu cầu truy nhập tài nguyên, sự cho phép và giải phóng tài nguyên). Điều này tạo ra một giải pháp hấp dẫn cho nhiều tình huống thực tế. Hạn chế: Nếu như bộ điều phối lỗi, hệ thống thực thể có thể sẽ bị down. Nếu các tài nguyên làm trở ngại một cách bình thường sau khi tạo yêu cầu thì chúng không thể phân biệt một bộ điều phối đã chết với một từ chối truy cập trong trường hợp không thông điệp nào quay lại. Trong một hệ thống lớn, một bộ điều phối đơn có thể trở thành một thắt cổ chai Sự đơn giản của giải thuật trong nhiều trường hợp mang lại nhiều trở ngại. Thuật tóan không tập trung Thuật tóan được đề cửa sử dụng trong hệ thống dựa trên DHT. Giải pháp là mở rộng những bộ phân phối tập trung theo cách sau: Mỗi tài nguyên được gán một bản sao n lần. Mỗi bản sao có bộ phân phối của nó để điều khiển việc truy nhập bởi những tiến trình thực thi đồng thời Dù vậy, mỗi khi một tiến trình muốn truy cập tài nguyên nó phải được sự cho phép của m >= n/2 bộ điều phối. Không giống như giải pháp tập trung được đưa ra ở trên(trong trường hợp b của ví dụ), khi một bộ điều phối không đưa ra sự đồng ý để truy cập tài nguyên, nó sẽ cho tiến trình yêu cầu tài nguyên biết Khi một bộ điều phối bị hỏng, nó nhanh chóng được khôi phục nhưng lại không nhớ được số vote mà nó đã có trứoc đó., hay nói cách khác là bộ điều phối tự khởi động lại ở thời điểm bất kỳ mà lỗi xảy ra. Nếu như yêu cầu truy cập tài nguyên bị từ chối thì nó sẽ được trả lại một biến thời gian chờ chọn ngẫu nhiên và c