摘  要： 在折半循環(huán)編碼算法的基礎(chǔ)上，提出了一種增加算法初始化節(jié)點(diǎn)數(shù)量和松弛正向差集的對稱分布式互斥請求集生成算法，使算法的時(shí)間復(fù)雜度大幅度降低，而所生成的請求集長度仍然保持~2之間。
關(guān)鍵詞： 松弛正向差集；請求集;折半循環(huán)編碼算法

　基于請求集的分布式互斥算法作為Maekawa算法[1]的推廣，近年來得到了人們的廣泛關(guān)注，人們提出了許多各具特色的算法[2-5]來構(gòu)建請求集以降低分布式互斥算法的消息復(fù)雜度或者提高分布式互斥算法在其他方面的性能。但在通常情況下，分布式互斥請求集生成算法的性能直接影響分布式互斥算法的性能。例如，請求集生成算法的對稱性將影響分布式互斥算法的對稱性，請求集生成算法所生成請求集的長度直接影響基于其上的分布式互斥算法的消息復(fù)雜度。而目前已經(jīng)存在的分布式互斥請求集生成算法在請求集長度、時(shí)間復(fù)雜性等方面都不能讓人滿意。李美安[6]介紹了一種用循環(huán)編碼產(chǎn)生請求集的互斥算法，它通過循環(huán)編碼產(chǎn)生請求集的方式得出一種消息復(fù)雜度較低、容錯性能高且同步時(shí)間短的對稱分布式互斥算法。但由于李氏循環(huán)編碼互斥算法的初始化節(jié)點(diǎn)數(shù)較少，因此算法的時(shí)間復(fù)雜度還是較高。
　為了在折半循環(huán)編碼算法中改善請求集生成算法的性能，本文提出了一種通過提高請求集中初始化節(jié)點(diǎn)數(shù)量的算法[7]，雖然在算法中引入了對稱請求集的概念，只須計(jì)算前「N/2]骎行和第0行有交點(diǎn)即可，空間復(fù)雜度可降低到O(N2/2)，比李美安提出的用循環(huán)編碼產(chǎn)生請求集的互斥算法的空間復(fù)雜度提高了50%，但和參考文獻(xiàn)[8]提出的一種基于循環(huán)的請求集產(chǎn)生算法的消息復(fù)雜度O()相比，還有較大的改進(jìn)空間。因此本文在折半循環(huán)編碼算法的基礎(chǔ)上引入松弛正向差集的理論，提出了一種提高請求集初始化節(jié)點(diǎn)的數(shù)量和運(yùn)用松弛正向差集的方式來改善請求集生成算法時(shí)間復(fù)雜度的算法，從而更快、更優(yōu)地產(chǎn)生請求集，且易于實(shí)現(xiàn)。
1 系統(tǒng)模型
　設(shè)系統(tǒng)的節(jié)點(diǎn)數(shù)為N，并從0~N-1對節(jié)點(diǎn)編號，第i個節(jié)點(diǎn)的ID號為i-1，假定系統(tǒng)的節(jié)點(diǎn)與通信均可靠，各節(jié)點(diǎn)沒有共享存儲器和共同的物理時(shí)鐘，節(jié)點(diǎn)間依靠消息進(jìn)行異步通信，并且消息通信時(shí)間延遲無法預(yù)知。

　定理：循環(huán)請求集與松弛正向差集等價(jià)。
　循環(huán)編碼算法中已經(jīng)證明，循環(huán)編碼所產(chǎn)生的請求集滿足Maekawa所提出的4個條件，其產(chǎn)生的請求集是對稱請求集，而在松弛差集算法中證明了循環(huán)請求集與松弛差集等價(jià)的定理，因此松弛循環(huán)差集所產(chǎn)生的請求集也是對稱請求集。而本算法是在松弛差集算法的基礎(chǔ)上進(jìn)行的改進(jìn)，即通過增加初始化請求集的長度，來縮短算法的時(shí)間復(fù)雜度，以求更快地找到所求請求集，因此本算法所產(chǎn)生的請求集也是對稱請求集。
1.3 請求集初始化理論
　根據(jù)Maekawa在參考文獻(xiàn)[1]中提出的請求集應(yīng)滿足的條件可知，系統(tǒng)的節(jié)點(diǎn)數(shù)(N)最少需要用長度為m的請求集表示(N<m(m-1)+1)，那么基于循環(huán)編碼的請求集生成算法的請求集方陣中每行至少有一個1，并且每個1與碼字的第0位的距離不相同。
　依據(jù)此條件考慮到2的冪之間的差的互異性，本算法在折半循環(huán)編碼算法中再以2i+1-2i為間距對請求集方陣第0行請求集碼字進(jìn)行初始化。為了更好地優(yōu)化循環(huán)基，令2k≤N/2，因?yàn)橹挥?k≤N/2時(shí)才能保證初始化節(jié)點(diǎn)的任意兩點(diǎn)間的距離不等。比如對于10個節(jié)點(diǎn)的請求集為1101000100，由于第3個節(jié)點(diǎn)和第0個節(jié)點(diǎn)之間的距離與第7個節(jié)點(diǎn)和第0個節(jié)點(diǎn)之間的距離相同，為了使循環(huán)基也變成單向的，應(yīng)使2k≤N/2，從而(2j-2i)mod N(i≠j且i，j∈k)之間的距離不等。為了減少循環(huán)編碼的次數(shù)，本算法在折半循環(huán)編碼算法的基礎(chǔ)上引入松弛正向差集，即當(dāng)(xj-xi)mod(N)(j>i)在小于N/2中的所有節(jié)點(diǎn)都可以表示時(shí)，此時(shí)的請求集即為所求的請求集。
綜上所述，通過松弛正向差集的優(yōu)化能更好地提高本算法的時(shí)間復(fù)雜度。



　本文在折半循環(huán)編碼算法基礎(chǔ)上，在提高循環(huán)編碼初始化節(jié)點(diǎn)的數(shù)量和引進(jìn)松弛正向差集的概念兩方面進(jìn)行合理的改進(jìn)，使空間復(fù)雜度由O(N2/2)下降到O(N)，時(shí)間復(fù)雜度由O(N2/2)降到現(xiàn)在的O(N/2)，因此本算法易于實(shí)際應(yīng)用。
參考文獻(xiàn)
[1] MAEKAWA M. A algorithm for mutual exclusion in decentralized systems[J]. ACM Transactions Computer Systems， 1985， 3(2)：145-159.
[2] AGRAWAL D, ABBADI A E. An efficient and fault-tolerant solution for distributed mutual exclusion[J]. ACM Transactions  on Computer Systems， 1991， 9(1)：158-167.
[3] CHEUNG S Y， AMMAR M H. AHAMAD M. The grid protocol： a high performance scheme for maintaining replicated data [J]. IEEE Transactions on Knowledge and Data Eng，1992，12 (6)：42-53.
[4] KUMAR A. Hierarchical quorum consensus： a new algorithm for managing replicated data[J]. IEEE Transactions on Computer Systems， 1991，9(6)：996-1004.
[5] HARADA T， YAMASHITA M. Transversal merge operation： a no dominated coterie construction method for distributed mutual exclusion[J]. IEEE Transactions on Parallel and Distributed Systems， 2005， 2(2)：183-192.
[6] LI Meian. A high performance distributed mutual exclusion algorithm base on cyclic coding [J]. Acta Electronica Sinica on 2005， 33(8)：1397-1402.
[7] 陳志黨，李美安.一種新的分布式互斥請求集生成算法[J].微計(jì)算機(jī)信息，2010(3-9)：211-212.
[8] LUK Waishing. Two new quorum based algorithms for distributed mutual exclusion[C]. Proceeding of the 17th International Conference on Distributed Computing Systems， IEEE， 1997： 100-106.