搜索分佈式算法來分配一些對象

Question

我在尋找一種算法來解決以下問題：

有n軟件組件，其能夠通過多播通信。此外還有一個帶有m對象的游泳池。每個sw組件都知道該池包含的內容。 對象具有不同的值。取決於我想要將對象分配給sw組件的值。這意味着：必須優先考慮具有較大值的對象，忽略具有較低值的對象（例如，當所有sw組件不能取更多對象時）。

這是非常重要的，沒有對象分佈不止一次。當一個對象被分配給一個SW組件時，它不能被分配給另一個SW組件。

此外，我想實現整個事情作爲分佈式算法，這意味着沒有一箇中央單位執行該分配。

任何想法？

Answer 1

1. 一個解決方案是實現一個互斥算法（一個非常簡單的就是麪包店算法），每個sw都會在輪到時獲得最高的對象。 （這就像寫入文件相互排斥）
2. 另一個會涉及到節點之間的大量通信。假設N> = M的一般情況。假設每個sw取n/m個分量，然後他取最大值，並將其餘的x分量多播到x sw，但使用額外的值，即這些分量的最大值。然後接收sw會查看它們的值是否大於接收到的值，並將交換它，並從列表中刪除該值，但插入它的舊值。然後它會將組件的最大值計算爲相同的x sw組件。這個想法是sw的集合X將彼此通信，直到每個節點具有不同的值。你將會有一些這樣的X套。當然，這個算法必須被細化，所以每個sw都有不同的值，並且證明這個算法會發生，所以你可以肯定。

但你想和想法，所以我給你2.希望它有幫助。 算法的實現將在OpenMPI中（使用C或C++）。至少我在OpenMPI中實現了我的分佈式算法（和Lam MPI，但現在已經過時）。