## SISTEM HIMPUNAN KORUM DAN MASALAH RESOLUSI KONFLIK TERDISTRIBUSI

## FEBRYANTI*)

## ABSTRACT
The aims of this study are (1) to analyze relaxation of the characteristics of distributed  mutual  exclusion  problem  of  various  problems  of  widening  conflict resolution in distributed system, (2) to develop coterie set system in solving any types of  conflict  resolution  in  distributed  system,  (3)  to  analyze  coterie  set  to  solve  the distributed conflict problem. The method used was literary study by collecting research materials through library journals that relevant with the subject matter i.e. quorum set system  and  various  problems  of  distributed  conflict  resolution.  The  results  of  the research indicated that mutual exclusion (mutex) can be solved with coterie, k-mutex problem  can  be  solved by  using  k-coterie,  read-writer  problem  can  be  solved  by  using bicoteri,  restricted  resources  problem  can  be  solved  by  using  (m,h,k i )-coterie.  For restricted  and  various  resources  matter  can  be  constructed  with  disjoint  and  simple uniform (m,h,k)-coterie.
Key words: Mutual exclusion, Distributed system, conflict resolution, coterie, bicoterie.

## PENDAHULUAN
Sistem  terdistribusi  dapat  dipandang  sebagai  sebuah  sistem  komputasi yang  terdiri  dari  beberapa  simpul  atau  node  (atau  secara  awam  beberapa komputer)  yang  berkomunikasi  satu  dengan  lainnya  menggunakan  jaringan komputer untuk saling bertukar pesan. Masalah utama dan fundamental dalam sistem  terdistribusi  umumnya  berkaitan  dengan  sinkronisasi  akses  diantara pesan  dalam  rangka  mengatasi  masalah-masalah  tabrakan  data,  konflik  akses, pemilihan pimpinan (leader election), dan masalah-masalah lainnya.
Algoritma sinkronisasi dalam sistem terdistribusi secara sederhana dapat dipandang  sebagai  sebuah  masalah  distributed  mutual  exclusion  (mutex).  Secara umum,  algoritma  mutex  memiliki  dua  tipe  yaitu;  algoritma  berbasis  tanda (token-based) dan algoritma berbasis izin (permission-based).
Algoritma berbasis token bekerja dengan mekanisme bahwa proses dapat mengakses  sumber  daya  ketika  memiliki  token,  sedangkan  algoritma  berbasis permission  bekerja  dengan  mekanisme  bahwa  proses  dapat  mengakses  sumber daya  jika  proses  tersebut  berhasil  mengumpulkan  izin  dari  beberapa  proses dalam system.
*) Staf Pengajar FKIP Universitas Al Asyariah Mandar
Mutual  Exclusion  (atau  mutex)  merupakan  mekanisme  sinkronisasi sedemikian sehingga paling banyak satu proses boleh menggunakan sumber daya disetiap  saat  dalam  sistem  terdistribusi.  Misalkan  p 1 ,  p 2, …,  p n adalah sekumpulan proses yang mencoba mengakses sebuah sumber daya R, dimana R hanya  boleh  diakses  oleh  satu  dan  hanya  satu  proses  dalam  setiap  satu  satuan waktu. Solusi dari masalah akses mutex oleh sekumpulan proses kedalam sumber daya R dapat harus memenuhi 2 syarat yaitu syarat Syarat aman (safety) paling banyak  satu  proses  boleh  menggunakan  sumber  daya  setiap  waktu;  syarat liveness  yaitu  semua  proses  yang  ingin  mengakses  sumber  daya  pada  akhirnya akan terkabulkan. (Lawi, et al., 2006)
Mekanisme  kerja  berbasis  izin  memiliki  dua  jenis  yaitu  izin  klasik  dan sistem  himpunan  korum.  Mekanisme  kerja  algoritma  berbasis  izin  klasik memiliki reliabilitas tinggi tetapi jumlah pesan yang dipertukarkan sangat besar sehingga kinerja sistem kurang efisien, berbeda dengan algoritma berbasis sistem himpunan  korum  reliabilitasnya  cukup  tinggi  dan  jumlah  pesan  yang dipertukarkan  lebih  sedikit  karena  hanya  mengirim  pesan  kebeberapa  proses dalam sistem.sehingga lebih efisien. (kakugawa, et.al. 2010)
Sistem  terdistribusi  memungkinkan  proses  untuk  mengakses  sumber daya  R={r 1 ,  r 2 .  ..,  r m }  yang  heterogen.  Sumber  daya  ini  dapat  digunakan bersama-sama  sehingga  memberikan  keuntungan  dalam  meningkatkan kecepatan  komputasi,  ketersediaan  data  serta  meningkatkan  kehandalan  data. (Suhatril, R . J. 2004; Lawi, et al. 2006; Joung, Y.-J., 2010).
Penelitian ini bertujuan untuk menganalisis relaksasi sifat-sifat masalah distributed mutual exclusion untuk berbagai perluasaan masalah resolusi konflik dalam  sistem  terdistribusi  dan  mengembangkan  sistem  himpunan  koteri  dalam menyelesaikan  berbagai  perluasan  masalah  resolusi  konflik  dalam  sistem terdistribusi,  serta  Menganalisis  sistem  himpuanan  koteri  dalam  menyelesaikan masalah konflik terdistribusi.

## BAHAN DAN METODE

## Lokasi dan Rancangan Penelitian
Penelitian  ini  dilakukan  di  wilayah  kampus  Unhas  Makassar.  Metode penelitian  yang  digunakan  adalah  kajian  pustaka,  mengumpulkan  bahan penelitian  melalui  jurnal  dan  literature  yang  ada  hubungannya  dengan  materi pembahasan. Penelitian ini dilakukan melalui berbagai tahapan yang ditempuh agar  hasil  penelitian  yang  diperoleh  memenuhi  kaidah-kaidah  ilmiah  yang dilaksanakan    secara  cermat  dan  sistematis.  Tahapan  penelitian  ini  dilakukan secara bertahap yaitu: Mempelajari sumber-sumber pustaka berupa buku, paper , dan  halaman  web  yang  berisi  tentang  teori  yang  berhubungan  dengan  mutual exclusion,  sistem  terdistribusi,  himpunan  koteri  dan  sistem  himpunan  korum terelaksasi;  Menganalisis  relaksasi  sifat-sifat  masalah  distributed  mutual exclusion  (mutex);  Mendesain  mekanisme  sinkronisasi  yang  dapat  mengatasi
berbagai  masalah  konflik  akses  kedalam  sumber  daya  dengan  menggunakan sistem himpunan korum.

## HASIL PENELITIAN Definisi koteri
Diberikan himpunan proses V   dalam sistem terdistribusi, G. Koleksi himpunan C ⊆ V disebut koteri (atas V ) jika dan hanya jika, memenuhi dua syarat berikut:
1. Irisan:  Q, Q ’  C  Q ⋂ Q ’  .
2. Non-redudansi:  Q, Q ’  C & Q ’  Q Himpunan Q, Q ’  C  disebut korum. (Lawi, et al. 2005)  Contoh : C = {{1,2}, {1,3}, {2,3}} merupakan sebuah koteri atas himpunan V = {1, 2, 3} karena setiap pasangan korum dalam C saling beririsan  dan tidak ada korum yang merupakan superset korum lainnya. Definisi koteri terdominasi  dan tak terdominasi Sebuah koteri C dikatakan terdominasi oleh koteri D, dimana C  D, jika dan hanya jika,  Q  C,  Q’  D  sedemikian  sehingga  Q ⊆ Q’.  Jika  tidak  terdapat  koteri  lain yang  mendominasi  maka  C  dikatakan  tak-terdominasi  atau  non-dominated  (ND coteri). 
Contoh  koteri  terdominasi:  Diberikan  koteri  C  =  {{1,2,3},  {1,2,4},  {1,3,4}, {2,3,4}} dan koteri D = {{1,2}, {1,3}, {1,4}, {2,3,4}} atas himpunan V = {1, 2, 3,4}. Koteri C dikatakan terdominasi oleh koteri D karena untuk setiap Q korum dalam C, dapat ditemukan korum Q’ dalam D sehingga Q’ ⊆ Q. Contoh  koteri  tak-terdominasi:  Diberikan  koteri  C  =  {{1,2},  {2,3},  {1,3}} merupakan  koteri  tak-terdominasi  atas  himpunan  V  =  {1,2,3}  karena  tidak dapat  ditemukan  koteri lain  (atas  V)  yang  mendominasi  C.  Koteri  D =  {{1,2}, {2,4,5}, {2,5,6}, {2,4,6}, {1,4,5}, {1,5,6}, {1,4,6}} atas himpunan V={1, 2,4,5,6} merupakan koteri tak-terdominasi.
Perluasaan sistem himpunan korum k-koteri
Koleksi himpunan C atas himpunan proses-proses V  disebut k-koteri jika dan hanya jika memenuhi 3 sifat berikut.
1. Saling-lepas  (disjoint):  Untuk  setiap  h (< k)  elemen  yang  saling  lepas  Q 1 ,  Q 2 , ...,  Q h yaitu  Q i ⋂ Q j =  ,  1  i  j  h,  terdapat  elemen  Q  C.  sedemikian sehingga Q ⋂ Q i =  ,1  i  h.
2. Saling-iris (intersection): Untuk sembarang Q 1 ,..., Q k+1  C, terdapat pasangan Q i dan Q j sedemikian sehingga Q i ⋂ Q j  .
3. Non-redudansi   Q i , Q j  C, Q i  Q j . (Jiang, Jehn-Ruey.2005) 
Contoh  C  =  {{1,2},  {1,3},  {1,4},  {2,3},  {2,4},  {3,4}}  adalah  2-koteri  atas  V  = {1,2,3,4}.  Koteri  C  dikatakan  2-koteri  karena  ditemukan  maksimal  2  korum yang  disjoint  yaitu  {1,2}  ,  {3,4}  atau  {1,3}  ,  {2,4}   atau  {1,4},  {2,3}  serta  jika
dipilih  sembarang  3  korum  maka  terdapat  paling  sedikit  satu  pasang  korum yang beririsan.

## Bikoteri
Pasangan , dan   adalah himpunan subset dari V, disebut bikoteri
(atas V) jika dan hanya jika memenuhi:
1. WR - saling iris :  W  ,  R  ,W ⋂ R  2. Non – redudansi :  W 1 , W 2  , W 1  W 2 dan  R 1 , R 2  , R 1  R 2 
Contoh:
V = {1, 2, 3, 4}
W = { {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} } R = { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} }
Masalah  resolusi  konflik  terdistribusi  didefinisikan  dengan  memperluas atau  mengeneralisasi  masalah  distributed  mutual  exclusion  (DME).  Perluasaan ini dapat dilakukan dengan merelaksasi syarat safety dari DME sebagai contoh, masalah k-mutual exclusion didefinisikan dengan merelaksasi syarat safety  yang awalnya  membolehkan  satu,  dan  hanya  satu,  proses  mengakses  sumberdaya tunggal setiap saat menjadi paling banyak k proses secara bersamaan.
Beberapa  relaksasi  kondisi  safety  DME  yaitu,  k-mutex  paling  banyak proses  yang  boleh  menggunakan  sumber  daya  tunggal  secara  bersamaan  setiap saat;  Group  mutex  paling  banyak    satu  (dari  m)  sumber  daya  yang  boleh digunakan/diakses  oleh  beberapa  proses  secara  bersamaan  setiap  saat;  Group  k- mutex  paling  banyak  satu  (dari  m)  sumber  daya  yang  boleh  digunakan/diakses oleh paling banyak k proses secara bersamaan setiap saat (gambar 1,2, dan 3).
Perluasan  masalah-masalah  resolusi  konflik  terdistribusi  kemudian  dapat didefinisikan  kedalam  sebuah  masalah  resolusi  konflik  terdistribusi  yang  lebih general  dengan  jumlah  m  buah  sumberdaya  dengan  kemampuan  eksekusi  yang terbatas.  yaitu  masalah  alokasi  sumber  daya  (m,h,k)  atau  (m,h,k)-resource allocated  problem  dan  masalah  sumberdaya  kapasitas  terbatas  (m,h,k i )  atau (m,h,k i )-distributed bounded capacity.

## PEMBAHASAN
Perluasan  masalah  resolusi  konflik  terdistribusi  dilakukan  dengan  cara merelaksasi syarat safety yang hanya boleh satu sumber daya dari m sumberdaya yang  dapat  diakses.  Masalah  ini  disebut  sebagai  masalah  (m,h,k)  resource allocated problem kemudian masalah ini diperluas lagi  menjadi masalah sumber daya  terbatas  atau  (m,h,k i )-distributed  bounded  capacity,  untuk . dengan  menyelesaikan  generalisasi  masalah  (m,h,k i )  maka  masalah  (m,h,k) dapat diselesaikan.
Masalah  (m,h,k)  dapat  diselesaikan  dengan  menggunakan  sistem himpunan  korum  yang  disebut  sebagai  (m,h,k)-koteri  adapun  definisi  dari (m,h,k)-koteri  yaitu  Koleksi  himpunan ,  dimana   B
disebut  (m,h,k)-  koteri  atas  V, adalah  k-koteri  atas  V,  jika  dan  hanya  jika memenuhi syarat (1) Disjoint yaitu Untuk setiap l(<h) yang elemennya disjoint
terdapat  elemen sedemikian  sehingga  untuk  semua dan disjoint.(2).  Bikoteri  yaitu  Untuk  setiap elemen ,  terdapat  pasangan dan yang  membentuk
bikoteri. (Lawi et al. 2006 A; Joung, Yuh-Jzer. 2004) Contoh (m,h,k)-koteri . berikut adalah (6,3,3)-koteri
C 1 = {{1,2,3,10,13,16  ,  4,5,6,11,14,17}, {7,8,9,12,15,18}} C 2 = {{10,11,12,19,22,25  ,  13,14,15,20,23,26}, {16,17,18,21,24,27}} C 3 = {{19,20,21,28,31,34  ,  22,23,24,29,32,35}, {25,26,27,30,33,36}} C 4 = {{28,29,30,37,40,43  ,  31,32,33,38,41,44}, {34,35,36,39,42,45}} C 5 = {{37,38,39,46,49,52  ,  40,41,42,47,50,53}, {43,44,45,48,51,54}} C 6 = {{1,4,7,46,47,48  ,  2,5,8,49,50,51}, {3,6,9,52,53,54}}. Untuk  masalah  sumber  daya  terbatas  m,h,k i atau  masalah  sumberdaya terbatas beragam dapat  diselesaikan dengan cara mengadopsi mekanisme kerja dari  konflik  resolusi  dan  juga  menggunakan  sistem  himpunan  koteri  yang disebut sebagai (m,h,k i )-koteri. Definisi dari (m,h,k i )-koteri yaitu m pasangan k i koteri B={C 1 ,...,C m  C i merupakan k i koteri atas V, yang memenuhi sifat disjoint dan sifat bikoteri}.
Contoh (m,h,k i )-koteri Sistem  korum yaitu koteri  atas . C 1 = {{1,2,7,10,13  ,  3,4,8,11,14}, {5,6,9,12,15}}
C 2 = {{7,8,9,16,19,22  ,  10,11,12,17,20,23}, {13,14,15,18,21,24}} C 3 = {{16,17,18,25,28  ,  19,20,21,26,29}, {22,23,24,27,30}} C 4 = {{25,26,27,31,33  ,  28,29,30,31,34}} C 5 = {{31,32,35,37},  33,34,36,38}} C 6 = {{1,3,5,35,36  ,  2,4,6,37,38}}.
Dari  dua  contoh  tersebut  diatas  dikonstruksikan  dengan  menggunakan  simple uniform.
Simple uniform Pertama  diasumsikan dan .    selanjutnya  P
dipartisi  kedalam  m  yang  merupakan  subset  dari    P 1 ,...P m. sedemikian
sehingga kemudian dibuat  menjadi  k-koteri  untuk
setiap dengan  mengkonstruksikan  k  himpunan  saling  lepas  (disjoint)  atau korum , , dimana . Untuk dan , maka .  B=  C 1 ,...C m  ,
dimana

## KESIMPULAN DAN SARAN
Berdasarkan hasil penelitian, maka dapat disimpulkan bahwa, Perluasan masalah  distribusi  mutual  exclusion  (DME)  menjadi  beberapa  masalah  resolusi konflik  terdistribusi  didefinisikan  dengan  merelaksasi  syarat  safety  dari  DME dan  untuk masalah  sumber  daya  terbatas  dapat  diselesaikan  dengan menggunakan  himpunan  koteri  serta  himpunan  koteri  untuk  masalah-masalah resolusi  konflik  dapat  digenerelaisasi  dan  disesuaikan  sesuai  dengan  relaksasi syarat safety.

## DAFTAR PUSTAKA
Jiang, Jehn-Ruey. (2005). A Fault-Tolerant h-out of k-mutual exclusion Algorithm Using Cohorts Coterie for Distributed Systems, Lecture Notes in Computer Science (LNCS), Vol.3320,267-273, DOI: 10.1007/978-3-540-30501-9_57. Joung,  Yuh-Jzer.  (2000).  Asynchronous  Group  Mutual  Exclusion,  Distributed Computing, Vol.13,Number 4. 189-206,DOI: 10.1007/PL00008918. Joung,  Yuh-Jzer.  (2004).  On  Quorum  Systems  for  Group  Resources  with  Bounded Capacity,  Lecture  Notes  in  Computer  Science  (LNCS),  Vol.  3274, 86- 101, DOI: 10.1007/978-3-540-30186-8_7 Joung,  Yuh-Jzer.  (2010).  On  quorum  systems  for  group  resources  allocation,
Distributed Computing, Vol.22, number 3, 197- 214, DOI: 10.1007/s00446-010-0094-4.
Kakugawa,  Hirotsugu  and  Kamei,  Sayaka.  (2010).  A  Token-Based  Distributed
Algorithm for the Generalized Resource Allocation Problem, Lecture Notes in  Computer  Science  (LNCS),  Vol.  6490,411-426,  DOI:  10.1007/978-3- 642-17653-1_30.
Lawi, A., Oda, K., dan Yoshida, T. (2005). A Simple Quorum Reconfiguration for Open Distributed Environment. Proceedings 11 th international Conference on  Parallel  and  Distributed  Systems  (ICPADS),  Vol.  2,  664-668,  IEEE Xplore Digital Library. DOI: 10.1109/ICPADS. 2005.48 Lawi, A.,  Oda,  K., dan  Yoshida,  T.,  2005.  A  Quorum  Based  Group k-Mutual
Exclusion Algorithm for Open Distributed Environments, Lecture Notes in Computer  Science  (LNCS),  Volume  3758, 119-25,  Springer-Verlag, DOI: 10.1007/11576235_16
Lawi,  A.,  Oda,  K.,  dan  Yoshida,  T.  (2006).  Quorum  Based  Distributed  Conflict
Resolution  Algorithm  for  Bounded  Capacity  Resources,  Lecture  Notes  in Computer Science (LNCS), Vol.  4331, 135-44, Springer-Verlag. DOI: 10.1007/11942634_15 Lawi, A., Oda, K., dan Yoshida, T., (2006). A Quorum Based (m, h, k)-Resource Allocation  Algorithm. Proceedings  of  the  International  Conference  on Paralleland  Distributed  Processing  Techniques  and  Applications (PDPTA), Vol. 1, 399-405, CSREA Poress.
Suhatril,  R.  J.  (2004).  Catatan  Kuliah  Sistem  Terdistribusi.  (serial  online) diunduh 18 Nopember 2011. http://openstorage.gunadarma.ac.id/sistem.terdistribusi/sister_main1.   pdf