Vol. 14, No. 2,  106-113,  Januari  2018
OPERASI JOIN KOTERI-k DIPERLUAS
La Ode Muhlis, 1 Armin Lawi 2 , Amir Kamal Amir 3

## Abstrak
Sebagaiman  diketahui  bahwa  koteri- k merupakan  perluasan  dari  definisi  koteri  yang  dapat diterapkan masalah mutex- k . Pada mutex- k terdapat sebanyak k proses yang dapat mengakses sumber daya.  Selain  itu,  kita  juga  mengenal  koteri- k khusus  yang  disebut  dengan  koteri- k mayoritas  dimana untuk  setiap  korumnya  memiliki  ukuran  yang  sama  yang  ditentukan  dengan | |   ⌈ ⌉ .  Terdapat beberapa  cara  dalam  penggabungan  koter- k i  salah  satu  diantaranya  dan  sudah  tidak  asing  lagi  yaitu operasi join yang merupakan suatu operasi  yang digunakan dalam menggabungkan koteri- k mayoritas yang  diperkenalkan  oleh  Neilsen  dan  Mizuno.  Pada  operasi  join,  terdapat  salah  satu  sifat  yang menyatakan  bahwa  jika dan tak-terdominasi  maka tak-terdominasi.  Ternyata  sifat  tersebut tidak  selamanya  berlaku  sehingga  mengakibatkan  koteri- k yang  dihasilkan  dari  operasi  join  menjadi terdominasi.
Tujuan  dari  penelitian  ini  yaitu  memperkenalkan  suatu  cara  baru  dalam  menggabungkan koteri- k mayoritas  tak-terdominasi  yang  disebut  dengan  operasi  join  diperluas.  Dimana  operasi  join diperluas  ini  adalah  suatu  operasi  yang  dikembangkan  dari  operasi  join  yang  dibangun  dengan  cara menggabungkan  dua  koteri- k mayoritas dan yang  memiliki  ukuran  korum  yang  sama  masing- masing  atas  semesta  tak-kosong dan dengan  unsur  tereliminasi ,  dimana untuk  membentuk atas  semesta  tak-kosong *( * + )+ .  Hasil  dari  penelitian  ini menunjukan bahwa untuk penggabungan dua koteri- k mayoritas tak-terdominasi dengan mengguankan operasi  join  diperluas  akan  selalu  menghasilkan  koteri- k tak-terdominasi  dengan  nilai k sebelum  dan setelah dilakukan operasi penggabungan tidak mengalami perubahan.
Kata kunci :  Koteri- k ,  koteri- k mayoritas,  koteri- k tak  terdominasi,  operasi  join  dan operasi join diperluas.

## Abstract
Operation of merging of k-coteries is not new. Where one of  incorporation operations of the k-coteri has been introduced by Neilsen and Mizuno. However, for research that combined the two forms of k-majority coterie with the same k has not been done by previous researchers. In this study, the background of how to combine the two forms of koteri majority to obtain a new majority k kerier k before and after the operation is fixed and unchanged.
k-Coterie  is  an  extension  of  the  definition  of  coterie  that  can  be  applied  to  the  k-mutex problems. In k-coterie there are as many processes that can access resources. And also we know that in k-coterie there are k-majority coterie. k-Majority coterie is a unik k-coterie in which for each measure of the k-majority coterie has the same quorum size which can be determined by | |   ⌈ ⌉ . There are several ways to combine the k-majority coteries, one of them and familiar is a join operation which is an  operation  combining  two  k-  majority  coteries.  Where,  this  join  operation  was  first  introduced  by Neilsen  and  Mizuno.  The  purpose  of  this  research  is  to  introduce  a  new  way  to  combine  k-majority coterie called 1 extended join operation. Which is this extended join operation is built by combining the
1 Pascasarjana Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin
2,3 Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin
La Ode Muhlis, Armin Lawi, Amir Kamal Amir
two  k-majority  coteries and respectively  under  the  non-empty  set and with  the  eliminated element ,  where to  form under  the  non-empty  set *( * + )+ .  The results  of  this  study  show  that  for  the  merging  of  two  k-  majority  coteriie  by  using  expanded  join operation  will  still  be  obtained  k-  majority  coterie  under  the  non-empty  set *( * + )+ with the value of k before and after done operations of merging remain unchanged. 2
Keywords :  k-Coterie,  k-majority  coterie,non-dominated  k-coterie,  join  operation  and extended join operations.

## 1. PENDAHULUAN
Sistem  terdistribusi  ( distributed  system )  merupakan  sekumpulan  elemen  atau  proses yang saling terhubung satu  sama lain yang membentuk suatu kesatuan untuk menyelesaikan suatu  tujuan  yang  spesifik  atau  menjalankan  seperangkat  fungsi  dimana  setiap  elemen  atau proses  tersebut  saling  berkomunikasi  dengan  cara  saling  bertukar  pesan  ( massage  passing ). Salah  satu  keunggulan  dari  sistem  terdistribusi  adalah  dimana  kemungkinan  adanya kegagalan proses yang tidak diketahui namun kegagalan proses tersebut tidak dapat membuat kegagalan  pada  sistem  secara  keseluruhan.  Sementara  kekurangan  dari  sistem  terdistribusi yaitu  bahwa  terjadinya  masalah  tabrakan  data,  adanya  konflik  akses,  masalah  pemilihan kepemimpinan  dan  lain-lain.  Untuk  mengatasi  permasalah  ini,  maka  diperlukan  suatu algoritma sinkronisasi permasalahan yang dikenal dengan algoritma mutual exlusion problem (algoritma masalah mutex ). Permasalahan mutex ini, pertama kali di uraikan dan diselesaikan oleh  Dijkstra  (Lamport,  1986).  Namun,  permasalahan  mutex  juga  dapat  dipandang  sebagai permasalahan  yang  sangat  mendasar  dan  krusial  dalam  hal  merancang  sistem  terdistribusi (Jiang  &  Huang,  1994;  Kakugawa et  al .,  1994;  Lawi et  al .,  2005).  Tedapat  beberapa algoritma yang telah mengimplementasikan masalah mutex tersebut kedalam lingkup sistem terdistribusi yaitu dalam hal ini adalah sistem terdistribusi dengan cara saling bertukar pesan (massage  passing)  yaitu  seperti  yang  dilakukan  oleh  (Lawi et  al .,  2006;  Neilsen  &  Mizuno, 1994;  Neilsen, 1997).
Pada algoritma masalah mutex terbagi menjadi dua bentuk algoritma. Yang pertama algoritma barbasis tanda ( token-based ) yaitu suatu proses yang mengakses sumberdaya ketika memiliki  token.  Dan  yang  kedua  adalah  algoritma  berbasis  izin  ( permission  based )  yaitu suatu  proses  yang  mengakses  sumberdaya  jika  proses  tersebut  berhasil  mengumpulkan  izin dari  berbagai  proses  dalam  sistem  tersebut.  Untuk  algoritma  berbasis  izin  juga  terbagi menjadi  dua  bagian  yaitu  algoritma  berbasis  izin  klasik  dan  algoritma  berbasis  himpunan korum. Jika dibandingkan dengan algoritma berbasis izin klasik, algoritma berbasis himpunan korum  memiliki  keunggulan  yang  lebih  baik  dari  pada  algoritma  berbasis  izin  klasik.

## La Ode Muhlis, Armin Lawi, Amir Kamal Amir
Keunggulan  dari  algoritma  himpunan  berbasis  korum  ini  yaitu  memiliki  reliabilitas  yang cukup  baik  dan juga  memberikan jumlah  pertukaran pesan  yang  jauh  lebih sedikit  sehingga lebih efisien.
Sehingga  masalah  mutex  dapat  dibentuk  kedalam  sistem  himpunan  korum  yang dikatakan  dengan koteri sebagai  mana  yang  dikaji  oleh Neilsen  &  Mizuno  (1992),  dan Lamport  (1986),  yang  memberikan  hasil  kajian  yaitu  nilai  cost  algoritma  yang  rendah terhadap  penggunaan  koteri.  Yang  dimasud  dengan  koteri  adalah  kumpulan  atau  himpunan dari beberapa korum yang  saling beririsan satu sama  lain dan untuk setiap korumnya bukan merupakan  subset  dari  atau  sama  dengan  korum  lainnya  (Neilsen  &  Mizuno,  1994).  Untuk beberapa  penelitian  seperti  yang  dilakukan  oleh  Agrawal  &  El-Abadi  (1991);  Garcia  & Barbara  (1985),  memperkenalkan  bagaimana  membentuk  suatu  himpunan  korum  yang disebut dengan koteri.
Selain  koteri,  kita  juga  mengenal  apa  yang  disebut  dengan  koteri- .  Koteri- merupakan pengembangan dari koteri. Secara sederhana, koteri- dapat didefinisikan sebagai himpunan  korum  yang  memiliki  paling  banyak korum  yang  saling  pisah.  Dimana,  sistem himpunan korum yang mengkaji tentang koteri- dapat diimplementasikan kedalam masalah alokasi  sumberdaya  yang  di  kenal  dengan  masalah  mutex- .  Masalah  Mutex- merupakan pengembangan dari masalah mutex yang dinyatakan dengan “terdapat paling banyak proses yang  dapat  mengakses  sumberdaya”.  Penerapan  masalah  mutex- yang  menerapkan algoritma  koteri- juga  telah  dilakukan  oleh  Manabe  &  Tajima  (2004);  Kakugawa et  al (1994),  dimana  hasil  dari  penelitian  mereka  memberikan  nilai  cost  yang  rendah.  Sementara Najafi  (2008),  bagaimana  merancang  teory  graf  yang  diterapkan  kemasalah  sistem terdisttribusi dengan nilai cost yang rendah.
Terdapat beberapa cara dalam menggabungkan suatu himpunan korum. Neilsen & Mizuno  (1992),  membangun  operasi  penggabungan  koteri  maupun  koteri- yang  disebut dengan operasi join. Namun operasi join tersebut menghasilkan koteri maupun koteri- yang terdominasi.  Ishak dkk (2016),  melakukan  pembanguna  operasi  penggabungan  dua  koteri mayoritas  yang  disebut  dengan  operasi  join  diperluas  sementara  untuk  koteri- mayoritas belum  dilakukan.  Tujuan  penelitan  ini  yaitu  membangun  definisi  penggabungan  koteri- mayoritas  untuk  mendapatkan  suatu  koteri- yang  baru  dengan  nilai k sebelum  dan  setelah dilakukan  operasi masih tetap sama dalam hal ini nilai k tidak mengalami perubahan.

## 2. METODE

## Rancangan Penelitian
Untuk  rancangan  penelitian  yang  akan  dilakukan  dengan  uraian  sebagai  berikut. Pertama-tama  yang  akan  dikaji  adalah  tentang  sistem  terdistribusi.  Selanjutnya  mengkaji tentang  masalah  mutex- dan  diteruskan  dengan  mengkaji  materi  himpunan  korum  yang mencakup  tentang  definisi  koteri- ,  koteri- mayoritas, dan  koteri- terdominasi. Kemudian melakukan operasi penggabungan koteri- dengan menggunakan operasi join diperluas untuk mendapatkan  suatu  koteri- yang  baru.  Untuk  operasi  penggabungan  koteri- ini,  yaitu menggabungkan  dua  bentuk  koteri- mayoritas  dengan  ukuran  korum  dan  nilai yang  sama untuk  mendapatkan  koteri- yang  baru  dengan  ukuran  dan  banyak  korum  yang  diperoleh melebihi  dua  koteri- mayoritas  awal  sebelum  dilakukan  operasi.  Dan  sebagai  langkah terakhir  yaitu  mendefinisikan  sifat-sifat  opersi  join  diperluas  pada  penggabungan  koteri- mayoritas tersebut.

## 3. HASIL PENELITIAN
Penggabugan dua koteri- mayoritas didefinisikan dengan operasi join diperluas sebagai berikut.
Definisi  1.3 . Misalkan * + dan * + adalah  koteri- mayoritas  masing-masing  atas  semesta dan ,  dimana
.  Operasi  join
diperluas dan dengan  unsur  tereliminasi yang  membentuk atas semesta *( * +) + didefinisikan sebagai berikut:
{  |     { ( * +) .( * +)   ( * +)/   ( ) } Dimana ; ; untuk ; .

## 4. PEMBAHASAN
Untuk koteri- didefinisikan dengan
Definisi  1.1. Koleksi  himpunan  tak-kosong dikatakan -koteri  atas    himpunan  tak kosong jika dan hanya jika berlaku syarat
1. Saling  pisah:  Untuk  setiap (   ) korum  yang  saling  pisah
dimana , (             ) ,  terdapat  korum sedemikian  sehingga ,
(         ) .
2. Saling irisan: Untuk setiap (   ) korum , terdapat pasangan korum , sedemikian sehingga , (             ) .
3. Minimalitas: berlaku .
Koteri- k mayoritas adalah himpunan korum yang memiliki ukuran yang sama. Untuk ukuran korum koteri- k mayoritas didefinisikan dengan
Definisi 1.2. Koleksi himpunan dikatakan -koteri mayoritas atas himpunan tak-kosong jika dan hanya jika * (   )   | |    + . Dimana ⌈ ⌉ , dimana | | .
Definisi  1.3 koteri- terdominasi  atas  semesta  tak-kosong jika  dan  hanya  jika  terdapat (   ) dimana
yang memenuhi:
1. sedemikian sehingga . 2. Untuk  setiap korum  saling  pisah ,  terdapat  korum sedemikian sehingga , (         ) . 3. Terdapat paling banyak
korum saling pisah dimana , (                 ) , sedemikian sehingga , (             ) .
Definisi  1.4. Misalkan dan adalah  koteri  masing-masing  atas  semesta dan ,
dimana
.  Operasi  join dan dengan  satu  unsur  tereliminasi didefinisikan dengan {  |     { ( * +) } Definisi  1.5. Misalkan * + dan * + adalah  koteri- mayoritas  masing-masing  atas  semesta dan ,  dimana
.  Operasi  join
diperluas dan dengan  unsur  tereliminasi yang  membentuk atas semesta *( * +) + didefinisikan dengan:
{  |     { ( * +)
.( * +)   ( * +)/   ( ) } Dimana ; ; untuk ; .
Contoh 1.
Misalkan diberikan koleksi himpunan dan masing-masing atas semseta *          + dan *          + sebagai berikut
{*    +  *    +  *    +  *    +  *    +  *    +}
{*    +  *    +  *    +  *    +  *    +  *    +}
Jika  unsur  tereliminasi
,  dengan  menggunakan  operasi  join  diperoleh atas  semesta
*                   + yaitu
{  |     { ( * +)
}
{*       +  *       +  *       +  *       +  *       +  *       + *       +  *       + *       +  *       +  *       +  *       +  *       +  *       +  *       +  *       +
*       +  *       +  *    +  *    +  *    +} Nampak  bahwa  operasi  join  menghasilkan  koteri- yang  terdominasi  sebab  dapat ditemukan *       +    (  *                   +) , dimana yang memenuhi definisi 1.3.
Contoh 2.
Misalkan diberikan koleksi himpunan dan masing-masing atas semseta *          + dan *          + sebagai berikut
{*    +  *    +  *    +  *    +  *    +  *    +}
{*    +  *    +  *    +  *    +  *    +  *    +} Jika unsur tereliminasi , dengan menggunakan operasi join diperluas maka {  |     { ( * +) .( * +)   ( * +)/   ( ) }
a. (,( * +)- )   .[ ] /
{*       +  *       +  *       +  *       +  *       +  *       +  *       +  *       +  *       +  *       +
*       +  *       +  *       +  *       +  *       +  *       +  *       +  *       +}
b. .[( * +)   ( * +)] /   .[( )] /
{*       +  *       +  *       +  *       +}
c. , - {*    +  *    +  *    +}
Dengan demikian diperoleh atas semesta *                   + yaitu {*       +  *       +  *       +  *       +  *       +  *       + *       +  *       +
*       +  *       +  *       +  *       +  *       +  *       +  *       +  *       + *       +  *       +  *       +  *       +  *       +  *       +  *    +  *    +  *    +}
Nampak  bahwa  pada  operasi  join  diperluas  menghasilkan  koteri- tak-terdominasi sebab  tidak  dapat  ditemukan (  *                   +) ,  dimana yang  memenuhi definisi 1.3.

## 5.KESIMPULAN DAN SARAN
Operasi penggabungan dua koteri- mayoritas yang memiliki ukuran korum dan nilai yang sama didefinisikan dengan operasi join diperluas yaitu
La Ode Muhlis, Armin Lawi, Amir Kamal Amir
{  |     { ( * +) .( * +)   ( * +)/   ( ) } Dimana adalah  koteri -k tak-terdominasi  atas semesta  tak-kosong .  Saran untuk penelitian berikutnya yaitu bagaimana mencari sifat-sifat definisi operasi join diperluas terhadap  penggabungkan  dua  bentuk  koteri- k mayoritas  baik  untuk  koteri- k mayoritas terdominasi maupun untuk koteri- k mayoritas tak-terdominasi.

## UCAPAN TERIMA KASIH
Sebagai rasa syukur dalam menuntaskan penelitian ini, maka tak lupa mengucapkan rasa  terima  kasih  kepada  pembimbing  yang  telah  memberikan  bantuan,  masukan,  dan  saran serta  keluarga  dan  teman-teman  yang  selalu  memberikan  motivasi  dalam  menuntaskan penulisan jurnal ini.

## DAFTAR PUSTAKA
Agrawal  D.  &  El-Abbadi  A.  (1991). An  efficient  and  fault-tolerant  solution  for  distributed mutual exclusion. ACM Trans. Comput. Systems 9 (1): 222-232.
Garcia H. & Barbara D. (1985). How to assign votes in a distributed system. J .ACM 32(4): 841–860.
Ishak  N.,  Lawi  A.,  &  Amir  K.  A.    (2016). Operasi  Penggabungan  Koteri  Tak-terdominasi Dengan Unsur Tereliminasi. Makassar: Hasanuddin University.
Jiang  J.  &  Huang  S.  (1994). Obtaining  Nondominated  k-Coteries  for  Fault-Tolerant Distributed k-Mutual Exclusion . IEEE Transactions on Computer: 30043 R. 0.C.
Kakugawa  H.,  Fujita  S.,  Yamashita  M.,  &  Ae, Tadashi.  (1994). A  distributed  k-mutual exclusion algorithm using k-coterie . Information Processing Letters, 49: 213-218.
Lamport  L.  (1986). The  Mutual  Exclusion  Problem  Part  I:  A  Theory  of  Interprocess Communication . National Science Foundation under grant number, MCS 7816783.
Lawi  A.,  Oda  K.,  &  Yoshida  T.  (2005). A  Quorum  Based  Group  k-Mutual  Exclusion Algorithm  for  Oper  Distributed  Environments .  Parallel  and  Distributed  Processing and Applications: 119-125.
Lawi  A.,  Oda  K.,  &  Yoshida  T.  (2006). A  Quorum  based  distributed  conflictresolution algorithm  for  bounded  capacity  resources .  Lecture  Notes  in  Computer  Science (LNCS), Springer Verlag-Berli, 4331: 135–144.
Maekawa  M.  (1985). A √ algorithm  for  mutual  exclusion  in  decentralized  systems. ACM Trans. Comput. Systems 3(2): 145-159.

## La Ode Muhlis, Armin Lawi, Amir Kamal Amir
Manabe  Y.  &  Tajima  N.  (2004) .  (h,  k)-Arbiters  for  h-out-of-k  Mutual  Exclusion  Problem . Theoretical Computer Science 310: 379-392.
Najafi  S.  (2008). A  New  GA  -  Based  and  Graph  Theory  Supported  Distribution  System Planning . IEEE Transactions on Parallel and Distributed System, 2(8).
Neilsen M. L. & Mizuno M. (1992). Coterie Join Algorithm. IEEE Transactions on Parallel and Distributed System, 3(5): 759-765.
Neilsen M. L. & Mizuno M. (1994) . Nondominated k-Coteries for Multiple Mutual Exclusion . Information Processing Letters, 50: 247-252.
Neilsen  M.  L.  (1997) .  Properties  of  Nondominated  k-Coteries .  J.  Systems  Software by Elsevier Science Inc: 37~91-96 .