JTRISTE, Vol.2, No.2, Oktober 2015, pp. 29~34 ISSN: 2355-3677
Konstruksi Sistem Korum Menggunakan Desain Blok Tak Lengkap Yang Seimbang Farhan Rezki Arifin1, Armin Lawi2, Hasmawati3 1Universitas Cokroaminoto Makassar 2,3Universitas Hasanuddin e-mail:
[email protected]
Abstrak Sistem korum terkait dengan salah satu teori dasar desain kombinatorial yaitu desain blok tak lengkap yang seimbang yang berhubungan dengan konstruksi dan sifat dari sistem himpunan hingga. Penelitian ini bertujuan untuk mengkaji kembali konstruksi sistem korum dan sifat-sifatnya menggunakan BIBD. Kemudian akan dibandingkan dengan sistem korum dari majority coteri. Metode yang dilakukan adalah studi kepustakaan. Hasil penelitian menunjukkan bahwa berdasarkan -sistem korum dikonstruksi dari -BIBD memiliki beban , rasio keseimbangan optimal dan rank . Sistem korum dari majority koterie memiliki ketersediaan terbaik ketika lebih baik daripada hasil konstruksi BIBD. Kata kunci: korum, BIBD, beban, rank, ketersediaan Abstract Quorum systems contexted with one of the basic theory of combinatorial designs, namely Balanced Incomplete Block Design which is related with construction and properties of definite set system. This study aims to review the construction of a quorum system and its properties using BIBD. Then be compared with quorum system of the majority coteri. The method is literature study. The result of the research revealed that based on -quorum system constructed from -BIBD has a load , the ratio of the optimal balance and rank Quorum system of majority coterie has best availability when better than from BIBD construction. Keywords: quorum, BIBD, load, rank, availability.
1. Pendahuluan Dalam ilmu komputer, khususnya dalam bidang sistem terdistribusi, istilah sistem korum dikenal sebagai koleksi subhimpunan yang merupakan bagian dari himpunan titik-titik, dimana tiap dua dari korum tersebut saling beririsan [11]. Sistem terdistribusi merupakan sistem komputasi yang terdiri dari beberapa titik dalam hal ini dapat dianggap sebagai komputer yang berkomunikasi satu sama lainnya menggunakan jaringan komputer untuk saling bertukar pesan. Dengan demikian, sistem terdistribusi dapat dipandang sebagai sebuah graf komunikasi yang terdiri dari himpunan titik dengan himpunan sisi adalah komunikasi antara titik tersebut. Sistem korum telah digunakan dalam kajian ilmiah pada distribusi kontrol dan manajemen masalah seperti mutual exclusion, protokol replikasi data, kontrol akses terdistribusi, dan signatures [9]. Protokol yang berdasar pada prinsip kerja sistem korum misalnya mengupdate database dimana user memilih sebuah korum dan mengakses semua elemennya sehingga dengan sifat irisan atau intersection menjamin user tetap memiliki view yang konsisten pada kondisi sistem saat itu [1]. Dengan desain sistem korum yang baik, dapat diperoleh cost komunikasi yang rendah dan toleransi terhadap beberapa kegagalan simpul. Beberapa penelitian sebelumnya mengenai konstruksi sistem korum antara lain singleton, weighted majorities, grid, dan finite projective plane [7].
JTRISTE
ISSN: 2355-3677
Terdapat keterkaitan antara sistem korum dengan teori desain kombinatorial. Teori desain kombinatorial adalah bagian dari matematika kombinatorial yang berhubungan dengan konstruksi dan sifat dari sistem himpunan hingga yang memenuhi konsep umum simetris. Salah satu teori dasar desain kombinatorial adalah Balanced Incomplete Block Design. Kajian tentang BIBD dimulai tahun 1930 oleh Fisher dan Yates [10]. Konstruksi sistem korum menggunakan desain kombinatorial telah dilakukan oleh Coulbourn [3]. Tujuan penelitian ini adalah mengkaji kembali konstruksi sistem korum dan sifatsifatnya menggunakan BIBD. Kemudian akan dibandingkan dengan sistem korum dari majority coteri. 2. Hasil dan Analisis
Gambar 1. Alur kerja penelitian. Gambar 1 memperlihatkan alur kerja penelitian. Langkah awal dengan membuat sistem korum dari BIBD dimana dan yang memenuhi sifat irisan. Kemudian mencari rank, beban, rasio keseimbangan dan ketersediaan dari sistem korum tersebut. Sistem korum dan sifat-sifatnya yang dihasilkan dinyatakan melalui beberapa teorema. Tabel 1. Perhitungan ketersediaan dari majority coterie dan sistem korum hasil konstruksi BIBD dengan
dan
sampai
0.0
0.0000000
0.0000000
0.1
0.0027280
0.0068104
0.2
0.0333440
0.0505472
0.3
0.1260360
0.1519668 Farhan Rezki Arifin, Armin Lawi dan Hasmawati
30
JTRISTE
ISSN: 2355-3677
0.4
0.2897920
0.3091456
0.5
0.5000000
0.5000000
0.6
0.7102080
0.6908544
0.7
0.8739640
0.8480332
0.8
0.9666560
0.9494528
0.9
0.9972720
0.9931896
1.0 1.0000000 Sumber : data olahan 2013
1.0000000
Tabel 1 memuat hasil perhitungan ketersediaan dari majority coterie dan sistem korum hasil konstruksi BIBD dengan dan sampai dengan menggunakan program maple 15.
Hasil plot terhadap ketersediaan dari majority coterie dan sistem korum hasil konstruksi BIBD :
yst em Fail ure Pro balil ity
Elemen Failure Probalility, p
Gambar 2.Grafik ketersediaan pada sistem korum
dan Majority Coterie.
Gambar 2 merupakan plot data perhitungan ketersediaan majority coterie dan sistem korum hasil konstruksi BIBD pada tabel 1. Penelitian ini menunjukkan konstruksi sistem korum dan sifat-sifatnya menggunakan BIBD. Teorema 1, Sistem dual dari reguler dengan derajat dan Sebuah dengan rank , dimana
-BIBD adalah sebuah
dan seragam dengan rank
-sistem korum yang dimana
.
-BIBD menghasilkan sebuah dan
-sistem korum yang seragam
.
Farhan Rezki Arifin, Armin Lawi dan Hasmawati
31
JTRISTE
Berikut sistem korum dari (
32
ISSN: 2355-3677
)-BIBD dengan
(Maekawa, 1985).
( )-BIBD dengan dan 5 menghasilkan -sistem korum yang seragam dengan rank , dimana secara berurutan dan 1.12. Sifat-sifat yang diselidiki pada kinerja sistem korum yang dikonstruksi menggunakan BIBD antara lain : beban, rasio keseimbangan, rank dan ketersediaan atau kadang disebut dengan kesalahan polinomial. Beban (load) pada sistem korum merupakan strategi aturan yang memberikan setiap korum frekuensi akses. Jumlah frekuensi dari setiap korum sama dengan satu. Untuk sistem korum , beban adalah peluang akses minimal dari semua strategi yang mugkin terjadi. Misal Untuk
adalah strategi dari sistem himpunan
dibawah himpunan
. Dengan beban strategi w pada u yaitu
w untuk sistem korum
adalah
, maka beban strategi . Dengan menggunakan nilai dari
beban strategi, maka nilai beban sistem korum minimum diambil dari semua strategi w. Teorema 2,
.
adalah
untuk semua (n,m)-sistem korum
, dimana nilai . [6]
Teorema 3, Jika adalah sebuah (n,m)-sistem korum yang reguler dengan derajat d dan seragam dengan rank r, maka . [8] Teorema 4, Jika
adalah sebuah sistem korum yang reguler, maka
. [4]
Farhan Rezki Arifin, Armin Lawi dan Hasmawati
JTRISTE
ISSN: 2355-3677
Dalam sistem korum yang seragam, rank menunjukkan jumlah elemen dalam korum. Rank dari sebuah sistem korum didefinisikan sebagai . Teorema 5, Jika
adalah sebuah
dan seragam dengan rank Untuk sistem
dengan
, didefinisikan
dual.
-sistem korum yang reguler dengan derajat
Misal
. [4] adalah jumlah himpunan perentang pada blok dalam
adalah
sebuah
(n,m)-sistem
korum,
maka
[9] Pandang sistem himpunan
dengan himpunan
dan . Maka adalah sebuah (7,3,1)-BIBD, sistem Dual dari BIBD ini adalah (7,7)-sistem korum yang seragam dengan rank 3 dan reguler dengan derajat 3. Berdasarkan teorema 5, = 3/7, dan teorema 6, karena adalah sebuah sistem korum yang reguler maka rasio keseimbangan . Untuk menghitung polinomial kesalahan atau failure polynomial untuk sistem korum ini, pertama-tama dihitung koefisien , Sehingga persamaan dari kesalahan polinomial adalah Sebagai bahan perbandingan, akan dihitung pula beban dan ketersediaan dari konstruksi sistem korum yang lain yaitu majority coterie.
Hasil perhitungan
dengan
dimana
Dari hasil perhitungan ketersediaan memberikan informasi bahwa untuk setiap titik dengan peluang kegagalan diperoleh peluang dari majority coterie ( ) sebesar 0.1260360 atau 12% sedangkan sistem korum hasil konstruksi dari BIBD ( sebesar 0.1519668 atau 15%. Untuk setiap titik dengan peluang kegagalan diperoleh peluang dari ( ) sebesar 0.9666560 atau 96% sedangkan sistem korum hasil konstruksi dari BIBD ( sebesar 0.9494528 atau 94%. Ini berarti sistem korum dari majority coterie memiliki ketersediaan terbaik ketika dibandingkan hasil konstruksi dari BIBD. Untuk menghitung beban dan rasio keseimbangan dari majority coterie, dimana adalah jumlah titik dan adalah ukuran korum pada . Untuk dan , diperoleh :
Dibandingkan dengan sistem korum dari hasil konstruksi BIBD untuk ukuran dan yang sama, dan (seimbang), maka sistem korum dari hasil konstruksi BIBD lebih baik dengan load yang lebih rendah. 3. Kesimpulan dan Saran Berdasarkan
-sistem korum , dimana
memiliki sebesar
dikonstruksi dari
-BIBD memiliki beban
merupakan faktor konstan. Sistem korum juga
yang merupakan rasio keseimbangan optimal. Rank dari sistem korum . Sistem korum dari majority coterie memiliki ketersediaan terbaik ketika
Farhan Rezki Arifin, Armin Lawi dan Hasmawati
33
JTRISTE
ISSN: 2355-3677
dibandingkan hasil konstruksi dari BIBD. Namun dengan nilai beban yang lebih rendah, dan rasio keseimbangan konstruksi BIBD lebih baik. Sebagai lanjutan dari penelitian ini, terkhusus mengenai ukuran ketersediaan (availability) dari sistem korum dapat dihitung dengan menggunakan prinsip inclusion-exclusion dan algoritma depth-first. Penelitian lainnya dapat dipertimbangkan untuk konstruksi sistem korum yang lain seperti -koteri dan general koteri. 4. Daftar Pustaka [1] Amir, Yair., Wool, Avishai. Optimal Availability Quorum Systems: Theory and Practice. The John Hopkins University and The Wizmann Institute, Revohot 76100, Israel. 1998. [2] Brualdi, Richard A. Introductory Combinatorics Fifth Edition. Pearson Education Asia Limited and China Machine Press. 2009. [3] Colbourn, Charles J., Dinitz, Jeffrey H. Quorum systems Constructed from Combinatorial Designs. University of Vermont. University of Nebraska. 1998. [4] Holzman, Ron., Marcus, Yosi., Peleg, David. Load Balancing in Quorum Systems. SIAM J. Discrete Math. 1997; 10(2): 223-245. [5] Maekawa, M. A Algorithm For Mutual Exclusion in Decentralized Systems. ACM Transactions on Computer. 1985;No.2: 145-159 [6] Malkhi, Dahlia., K. Reiter, Michael. dkk. (2001). Probabilistic Quorum Systems. Information and Computation. 2001; 170: 184-206. [7] Malkhi, Dahlia. Quorum Systems. AT & T Labs-Research. 1999. [8] Naor, Moni., Avishai, Wool. The Load, Capacity, Availability of Quorum System. The Wizmann Institute Rehovot 76100, Israel. Weizmann Science Press of Israel. 1994. [9] Peleg, David,. Wool, Avishai. The Availability of Quorum Systems. The Wizmann Institute Rehovot 76100, Israel. Weizmann Science Press of Israel.1995. [10] Stinson, Douglas R. Combinatorial Designs Constructions and Analysis. Springer. 2004. [11] Vukolic, Marko. (2010). The Origin of Quorum Systems. Bulletin of EATCS. 2010; no. 101:125-147.
Farhan Rezki Arifin, Armin Lawi dan Hasmawati
34
