## STUDI AWAL PENERAPAN ALJABAR MAX PLUS PADA SISTEM PENYIMPANAN TERDISTRIBUSI MELALUI NETWORK CODING

## PRELIMINARY STUDY ON APPLICATION OF MAX PLUS ALGEBRA IN DISTRIBUTED STORAGE SYSTEM THROUGH NETWORK CODING
Agus Maman Abadi * , Musthofa, dan Emut
Jurusan Pendidikan Matetmatika, Fakultas MIPA, Universitas Negeri Yogyakarta, Karangmalang, Yogyakarta, 55281
* email: agusmaman@uny.ac.id
diterima 2 Desember 2014, disetujui 3 Maret 2015

## Abstrak
Peningkatan  kebutuhan  akan  sebuah  cara  untuk  menyimpan  data  dalam  jumlah  yang  besar  menghadirkan  sebuah tantangan  baru.  Salah  satu  cara  untuk  menghadapi  tantangan  ini  adalah  menggunakan  sistem  penyimpanan  data terdistribusi  (Distributed  Storaged  Systems).  Salah  satu  strategi  yang  diterapkan  dalam  sistem  penyimpanan  data terdistribusi  adalah  menggunakan  Erasure  Code  yang  diaplikasikan  pada  network  coding.  Kode  yang  digunakan  pada teknik ini didasarkan pada struktur aljabar berupa ruang vektor. Beberapa penelitian juga telah dilakukan untuk membuat kode  yang  didasarkan  pada  struktur  aljabar  lain,  yaitu  modul.  Pada  penelitian  ini  dicoba  dibentuk  suatu  kode  yang didasarkan pada struktur aljabar yang merupakan generalisasi dari modul, yaitu semimodul dengan memanfaatkan operasi max dan operasi penjumlahan pada aljabar  max plus. Hasil penelitian ini menunjukkan bahwa operasi  max dan operasi penjumlahan  pada  aljabar  max  plus  belum  dapat  digunakan  untuk  membentuk  suatu  kode  semimodule,  namun  dengan memodifikasi operasi “+” sebagai operasi “ min”, dapat dibentuk suatu kode yang didasarkan pada semimodul.
Kata kunci:  kode, sistem penyimpanan data terdistribusi, network coding, semimodul, aljabar max plus

## Abstract
The increasing need in techniques of storing big data presents a new challenge. One way to address this challenge is the use of distributed storage systems. One strategy that implemented in distributed data storage systems is the use of Erasure Code which applied to network coding. The code used in this technique is based on the algebraic structure which is  called  as  vector  space.  Some  studies  have  also  been  carried  out  to  create  code  that  is  based  on  other  algebraic structures such as module.  In this study, we are going to try to set up a code based on the algebraic structure which is a generalization of the module that is semimodule by utilizing the max operations and sum operations at max plus algebra. The results of this study indicate that the max operation and the addition operation on max plus algebra cannot be used to establish a semimodule code, but by modifying the operation "+" as "min", we get a code based on semimodule.
Keywords:  code, distributed storage systems, network coding, semimodule, max plus algebra

## Pendahuluan
Perkembangan
teknologi informasi khususnya  dalam  hal  penggunaan  data  berukuran besar  seperti  video,  gambar  dan  jejaring  sosial telah melahirkan tantangan baru, yaitu bagaimana strategi  untuk  mengelola  data  yang  sedemikian besar  tersebut.  Menurut  [1],  sebuah  penelitian yang  dilakukan  pada  tahun  2011  menyatakan bahwa  setiap  dua  tahun  data  di  dunia  ini meningkat  menjadi  lebih  dari  dua  kali  lipat  dan mencapai 1,8 zettabytes (1 zsettabyte = 10 21 byte). Jika  data  tersebut  disimpan  dalam  DVD,  maka tumpukannnya  bisa  mencapai  jarak  bumi  ke bulan.  Salah  satu  cara  untuk  menghadapi
tantangan  ini  adalah  menggunakan  sistem penyimpanan data terdistribusi (Distributed Storaged  Systems  (DSS)).  Melalui  DSS  ini  data akan  dipecah-pecah  kemudian  disimpan  dalam sistem  penyimpanan.  Salah  satu  strategi  yang diterapkan  dalam  DSS  adalah  menggunakan Erasure  Code  yang  diaplikasikan  pada  network coding.  Melalui  DSS,  data  dipecah-pecah  dan kemudian  disimpan  dalam  sistem  penyimpanan terdistribusi  yang  terkoneksi  melalui  sistem jaringan komunikasi. Masalah yang terjadi dalam DSS  adalah  selalu terjadi bagian  penyimpan  data (node)  yang  gagal  atau  error.  Oleh  karena  itu
proses  perbaikan  data  secara  sistematis  menjadi perhatian  utama.  Berikut  skema  sistem  DSS dalam [1]:

## Gambar 1. Sistem Penyimpanan terdistribusi (DSS)
Beberapa  penelitian  yang  telah  dilakukan pada masalah ini antara lain :
1) Pada  tahun  2012,  Tanakorn  Chareonvisal melakukan  simulasi  DSS  menggunakan beberapa  metode  seperti replicating  code  dan regenerating  code  yang  semuanya  didasarkan pada  struktur  aljabar    ruang  vektor  atas lapangan.
2) Pada  tahun  2013,  Arvind  Kumar  Sinha memperkenalkan penggunaan struktur aljabar
“modul” untuk mendesain kode.
Berdasarkan latar belakang di atas diidentifikasi  beberapa  strategi  dalam  penerapan struktur  aljabar  pada  pembentukan  kode.  Artikel ini  melaporkan  tentang  peluang  penggunaan struktur  aljabar  yang  lebih  umum,  yaitu semimodul atas aljabar max plus untuk membentuk kode.
Meningkatnya penggunaan media penyimpanan  data  seiring  dengan  meningkatnya penggunaan  email,  foto,  video    dan  data-data berukuran besar lainya membutuhkan solusi yang tidak  mudah.Jika  data-data  tersebut  disimpan dalam  satu  tempat,  maka  akan  sangat  berbahaya dikarenakan  media  penyimpanan  dapat  rusak sehingga mengakibatkan hilangnya data.
Solusi yang dapat dilakukan untuk mengatasi hal  tersebut  antara  lain  [6]:  menyimpan  data dengan  menyediakan  cadangan  data  dalam banyak  media  penyimpana  (disk). Jika  salah  satu disk mengalami kerusakan, maka tinggal mengganti  disk  tersebut  denga  yang  baru sehingga  data  bisa  terselamatkan.  Teknik  ini dinamakan  sistem  penyimpanan  terdistribusi (distributed storage system (DSS)).
Namun,  masalah  yang  terjadi  tidaklah sesederhana  ini.    Pusat  data  yang  akan menyimpan data dalam jumlah besar membutuhkan  banyak  sekali  piranti  penyimpan.
Akibatnya  kerusakan  pada  piranti  penyimpan menjadi  hal  yang  tak  terhindarkan  yang  dapat menimbulkan  masalah  baru.  Oleh  karena  itu diperlukan strategi dalam mengelola penyimpanan data. Network  coding  adalah  suatu  pendekatan untuk meningkatkan efisiensi dari proses komunikasi  [3].    Network    coding  adalah  suatu bagian  (node)  dalam  proses  komunikasi  yang terletak  di  antara  sumber  data  (source)  dan penerima (receiver) yang selain mampu menyimpan  dan  meneruskan  data,  juga  mampu mengkombinasikan  secara  independen  data  yang masuk menjadi data yang siap dikirim.
Melalui  network  coding,  bagian  penyimpan data  yang  rusak  dalam  sistem  DSS,  diperbaiki dengan  langkah-langkah  tertentu.  Skema  dari network coding dalam [5] adalah sebagai berikut :

## Gambar 2. Network Coding dalam DSS
Penggunaan Network Coding dapat meningkatkan  meningkatkan  Troughput  ,  yaitu kapasitas  informasi  yang  dialirkan  melalui jaringan  yang  diukur  dengan  satuan  waktu tertentu dan kondisi jaringan tertentu.
Berikut  ini  beberapa  definisi  yg  berkaitan dengan struktur aljabar.

## Definisi 1
Diberikan  ring  R  dan  grup  komutatif  (M,  +)  dan pemetaan f : R × M → M yang memenuhi:
1) r ( m 1 + m 2 ) = rm 1 + rm 2 , 2) (r 1 + r 2 ) m = r 1 m + r 2 m, 3) (r 1 r 2 ) m = r 1 (r 2 m), untuk setiap  r, r 1 , r 2 ∈ R dan m, m 1 ,m 2 ∈ M.   M dinamakan modul(kiri)  atas ring R.

## Definisi 2
Suatu himpunan H ⊆ M dinamakan submodul dari M jika memenuhi :
1) h 1 + h 2 ∈ H, untuk setiap h 1 , h 2 ∈ H 2) rh ∈ H, untuk setiap h ∈ H dan r ∈ M.
Definisi 3 Suatu  semiring  (S, ⊕ , ⊗ )  adalah  himpunan  tak kosong S disertai dengan  dua operasi biner ⊕ dan ⊗ yang memenuhi aksioma berikut :
1) (S, ⊕ )  merupakan  monoid  komutatif  dengan elemen netral ε , yaitu ∀ x,y,z ∈ S memenuhi (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) x ⊕ y = y ⊕ x x ⊕ ε = ε ⊕ x = x
2) (S, ⊗ )  merupakan  monoid  dengan  elemen satuan e, yaitu ∀ x,y,z ∈ S memenuhi (x ⊗ y) ⊗ z = x ⊗ (y ⊗ z) x ⊗ e = e ⊗ x = x
3) Elemen  netral ε merupakan  elemen  penyerap terhadap operasi ⊗ , yaitu ∀ x ∈ S, ε ⊗ x = x ⊗ ε = ε . 4) Operasi ⊗ bersifat distributif terhadap operasi ⊕ , yaitu ∀ x,y,z ∈ S berlaku (x ⊕ y) ⊗ z = (  x ⊗ z) ⊕ (y ⊗ z) x ⊗ ( y ⊕ z ) =  ( x ⊗ y ) ⊕ ( x ⊗ z )

## Definisi 4
Semimodul  kiri  atas  semiring  (  S, ⊕ , ⊗ )  adalah himpunan monoid komutatif (M, ⊕ ) yang dilengkapi  operasi  eksternal  yaitu  pemetaan pergandaan skalar ( kiri ):
f : S × M → M dan memenuhi aksioma-aksioma: ( ∀ x,y ∈ M) da( ∀ r,s ∈ S )
1) r ( x ⊕ y ) = rx ⊕ ry 2) (r ⊕ s) x = rx ⊕ sx 3) r (sx) = (rs)x
Selanjutnya  subsemimodul  didefinisikan  seperti submodul.
Misalkan  B  =  {  0,1}  dan  B 2 =  Z 2 Z 2 =  {00, 01,  10,  11}.  Didefinisikan  operasi  biner  pada  B dan  B 2 sebagai  operasi  penjumlahan  modulo  2. Sebagai contoh  01 + 10 = 11, 11 + 11 = 00, dan seterusnya. Berikut sifat dari himpunan ini.

## Teorema 5.
Jika B n = Z 2 Z 2 … Z 2 ( sebanyak n ), maka    ( B n , +  )  dengan  +  menyatakan  operasi  penjumlahan modulo 2 merupakan modul atas B = { 0, 1}.
Bukti :
1) Jelas bahwa B n merupakan grup komutatif.
2) (B, +, × )  = ({ 0, 1}, + , × )  merupakan ring 3) Untuk setiap m, m 1 , m 2 ∈ B n dan r, r 1 , r 2 , ∈ B, berlaku sifat:
a) r ( m 1 + m 2 ) = rm 1 + rm 2 , b) (r 1 + r 2 ) m = r 1 m + r 2 m,
c) (r 1 r 2 ) m = r 1 (r 2 m)

## Metode Penelitian
Penelitian ini menggunakan metode penelitian  studi  literatur  berupa  jurnal-jurnal ilmiah  yang  terkait  dengan  topik  penelitian,  dan buku-buku referensi yang mendukung. Pada tahap awal  dipelajari  konsep-konsep  dasar  tentang distributed  storage  system  (DSS)  dan  network coding serta pengkonstruksian kode menggunakan  linear  network  coding.  Konsep- konsep  ini  nantinya  digunakan  sebagai  dasar untuk membentuk kode dengan menerapkan sifat- sifat pada aljabar max plus.
Selanjutnya,  dipelajari  beberapa  kelemahan pada  linear  network  coding  yang  telah  diberikan oleh  Dougherty  et  al.  [8].  Langkah  berikutnya adalah  mempelajari  pengkontruksian  secara aljabar  dari  linear  network  coding  dalam  [9], yang  akan  digunakan  sebagai  dasar  untuk memodifikasi metode yang sudah ada.
Langkah  terakhir  adalah  menerapkan hasil-hasil  yang  diperoleh  untuk  membuat rancangan  algoritma  untuk  membentuk  suatu teknik pengkodean berdasarkan operasi dan sifat- sifat dalam aljabar max.

## Hasil dan Pembahasan
Awal  bagian  ini  akan  terlebih  dahulu membahas  tentang  kode  modul  seperti  yang dibahas dalam [2].
A. Kode Modul
Berikut  ini  diberikan  suatu  definisi  kode modul yang dikembangkan dari [2].

## Definisi 6
Misalkan M 1 dan M 2 adalah suatu modul atas ring R dan E: M 1 → M 2 adalah suatu fungsi encoding.
Suatu kode C = E( M 1 ) dinamakan kode modul jika E( M 1 ) merupakan submodul dari M 2 .

## Contoh 7
Diberikan modul B 2 = { 00, 01, 10, 11} dan B 5 = {00000,  10000,  10001,  10011,  10010,  10101, 10110,  10111,  11000,  11001,  11010,  11011, 11100,  11100,  11101,  11110,  00001,  00011, 00010,  00100,  00110,  00111,  01000,  01001, 01010,  01011,  01100,  01101,  01110,  01110, 01111, 11111}.
terhadap operasi penjumlahan modulo 2 dan pergandaaan skalar atas B = {0,1}. Selanjutnya didefinisikan fungsi encoding E: B 2 → B 5 sebagai :
E(00) = 00000 E(01) = 01110 E(10) = 10101 E(11) = 11011 E(B 2 ) merupakan suatu submodul dari B 5 sebab :
1) Tertutup terhadap penjumlahan, yaitu:
01110 + 10101= 11111 01110 + 11011 =10101 10101 + 11011 = 01110 01110 + 01110 = 00000
10101 + 10101 = 00000 11011 + 11011 = 00000 11011 + 11011 = 00000 2) Tertutup terhadap perkalian skalar { 0, 1},
yaitu
0 × (10101 ) = 00000 dan 1 × ( 10101) = 10101 Jadi, E(B 2 )  = { 00000, 01110, 10101, 11011} di atas adalah kode modul sebab merupakan submodul dari B 5 .

## Contoh 8
Diberikan B 2 dan B 4 seperti pada contoh 4.2.
Didefinisikan fungsi enkoding E : B 2 → B 4 sebagai berikut : E(00) = 0000 E(01) = 0101 E(10) = 1010 E(11) = 1111 E(B 2 ) = { 0000, 0101, 1010, 1111} merupakan submodul dari B 4 sebab:
1) Tertutup terhadap penjumlahan, yaitu: 0101 + 1010 = 1111
1010 + 1111 = 0101 0101 + 1111 = 1010 0101 + 0101= 0000
1010 + 1010 = 0000 1111 + 1111 = 0000
2) Tertutup terhadap perkalian skalar B = {0, 1},
yaitu :
1 × ( 1010 ) = 1010 0 × ( 1010 ) = 0000 Jadi,  E(B 2 )  =  {0000,  1010,  0101,  1111} merupakan kode modul.
B.  Kode Semimodul Berdasarkan hasil di atas, dicoba dikembangkan  suatu  kode  yang  didasarkan  atas operasi  maximum  dan  operasi  penjumlahan  yang diinspirasi  oleh  struktur  aljabar  max  plus  yang merupakan semimodul sebagai berikut :
Jika  pada  himpunan  B 2 =  {00,  01,  10,11} didefinisikan  suatu  operasi ⊕ =  max  dan ⊗ = penjumlahan  modulo2,  maka  akan  menghasilkan fakta berikut :
1) (B 2 , ⊕ ) merupakan monoid komutatif 2) (B 2 , ⊗ ) merupakan monoid komutatatif
3) Sifat  distributive ⊗ terhadap  terhadap ⊕ tidak terpenuhi, misal:
01 ⊗ ( 01 ⊕ 01 ) = 01 ⊗ 11 = 01 + 11 = 10 (01 ⊗ 01) ⊕ (01 ⊗ 01) = 00 ⊕ 00 = 00
Karena  sifat  distributifnya  gagal,  maka dicoba  dikembangkan  pada  operasi  yang  mirip dengan  aljabar  max  plus,  yaitu  untuk  operasi ⊗ didefinisikan  sebagai ⊗ =  min.  Diperoleh  hasil sebagai berikut :
1) (B 2 , ⊕ ) merupakan monoid komutatif 2) (B 2 , ⊗ ) merupakan monoid komutatif 3) Sifat distributive berlaku, yaitu : 00 ⊗ (01 ⊕ 10) = 00 ⊗ 11 = 00 = (00 ⊗ 01) ⊕ (00 ⊗ 10) 10 ⊗ (01 ⊕ 10) = 10 ⊗ 11 = 10 = (10 ⊗ 01) ⊕ (10 ⊗ 10) 01 ⊗ (01 ⊕ 10) = 01 ⊗ 11 = 01 = (01 ⊗ 01) ⊕ (01 ⊗ 10) 11 ⊗ ( 01 ⊕ 10 ) = 11 ⊗ 11 = 11 = (11 ⊗ 01) ⊕ (11 ⊗ 10)
Berdasaran  hasil  ini,  kemudian  dapat didefinisikan kode semimodul sebagai berikut:

## Definisi 9
Misalkan S 1 dan S 2 adalah suatu semimodul atas semiring  R  dan  E:  S 1 → S 2 adalah  suatu  fungsi encoding.  Suatu kode C = E(S 1 ) dinamakan kode semimodul  jika  E(  S 1 )  merupakan  subsemimodul dari S 2 .
Contoh 10 Diberikan himpunan (B 2 , ⊕ ), (B 4 , ⊕ ) yang keduaya merupakan  semimodul  atas  semiring  (B, ⊕ , ⊗ ) dengan fungsi encoding E : B 2 → B 4 didefinisikan sebagai :
E(00) = 0000 E(01) = 0101 E(10) = 1010 E(11) = 1111. C = E(B 2 ) = {0000, 0101, 1010, 1111} merupakan subsemimodul dari B 4 sebab :
1) Tertutup terhadap operasi ⊕ = max
0101 ⊕ 1010 = 1111
0101 ⊕ 1111 = 1111
1010 ⊕ 1111 = 1111
1111 ⊕ 1111 = 1111 dst
2) Tetutup terhadap perkalian skalar di B
1 ⊗ (1010) = 1010 0 ⊗ (1010) = 0000
Jadi,  C  =  {0000,  0101,  1010,  1111}  merupakan kode semimodul.
Contoh 11 Diberikan  semimodul  (B 2 , ⊕ )  dan  (B 5 , ⊕ )  atas semiring (B, ⊕ , ⊗ )
Selanjutnya  didefinisikan  fungsi  encoding  E:  B 2 → B 5 sebagai :
E(00) = 00000 E(01) = 01110 E(10) = 10101 E(11) = 11011 E(B 2 )  merupakan  suatu  subsemimodul  dari  B 5 sebab :
1) Tertutup  terhadap  penjumlahan  (operasi max), yaitu:
01110 ⊕ 10101= 11111
01110 ⊕ 11011 =11111
10101 ⊕ 11011 = 11111 01110 ⊕ 01110 = 01110
10101 ⊕ 10101 = 10101
11011 ⊕ 11011 = 11011
11011 ⊕ 11011 = 11011
2) Tertutup terhadap perkalian skalar di B, yaitu
0 ⊗ (10101) = 00000 dan
1 ⊗ (10101) = 10101 Jadi, C = E(B 2 )  = {00000, 01110, 10101, 11011} di atas adalah kode semimodul.

## Simpulan
Penelitian  ini  merupakan  pengkajian  dari penelitian  sebelumnya  yang  dilakukan  oleh Arvind Kumar Sinha [2], yaitu tentang kode yang didasarkan  pada  struktur  aljabar  modul.  Aljabar max plus yang telah dikenal luas dapat dipandang sebagai  semimodul,  namun  pada  hasil  penelitian ini  belum  berhasil  untuk  membentuk  kode.  Oleh karena itu, pada penelitian ini telah dikaji tentang struktur  aljabar  (B m ,  max)  yang  merupakan semimodul  atas  semiring  (B,  max,  min)    dapat digunakan dalam pembentukan kode  yang dalam kajian  ini dinamakan kode semimodul.

## Ucapan Terima Kasih
Tim  Peneliti  mengucapkan  terimakasih kepada Universitas Negeri
Yogyakarta, khususnya  Fakultas  MIPA  yang  telah  mendanai kegiatan penelitian ini.

## Pustaka
[1] Oggier  F.  (2013)  On  Coding  Techniques  for Networked Distributed Storage Systems . First European  Training  School  on  Network Coding, Barcelona.
[2] Sinha  A.K.  (2013)  Application  of  Module
Structure  of  Algebra  in  Coding  Theory  in Different Branches of Engineering, International Journal of Scientific
Engineering and Technology, 2, 4, 295.
[3] Oggier  F.,  Datta.  A.  (2012)  Coding Techniques  for  Repairability  in  Networked Distributed Storage Systems.
[4] Chareonvisal T. (2012) Implementing Distributed  Storage  System  by  Network Coding in Presence of Link Failure.  Master Thesis Report.
[5] Dimakis  A.  G.,  Godfrey  P.  B.,  Wu  Y., Wainwright  M.  J.,  and  Ramchandran  K. (2010)  Network  coding  for  distributed storage  systems,  IEEE  Trans.  on  Info. Theory.
[6] Dimakis A. G., Ramchandran K., Wu Y., and Su  C.  (2010)  A  Survey  on  Network  Codes for  Distributed  Storage,  The  Proceedings  of the IEEE, 99, 476.
[7] Venkatesan  V.  (2007)  Distributed  storage systems,  IBM  Zurich  Research  Lab,  EPFL, Switzerland.
[8] Fragouli  C.  and  Soljanin  E.  (2007)  Network coding fundamentals, Now Publishers,
Germany
[9] Dougherty  R.,  Freiling  C.,  dan  Zeger  K. (2005)  Insufficiency  of  Linear  Coding  in Network Information
Flow.
IEEE
transactions on information theory,  51, 8.
[10]  Gadouleau  M.  (2009)  Algebraic  Codes  for Random  Linear  Network  Coding.  P.hD dissertation, Lehigh University.
[11] Musthofa, Binatari N.. Sifat-sifat Nilai Eigen dan  Vektor  Eigen  Matriks  atas  Aljabar  Max Plus, Jurnal Sains Dasar , 2, 1.
[12]Wei Guan. (2013) Cooperative Communication Withwireless Network
Coding, Ph.D dissertation.
[13]  Rui  A.  Costa.  (2012)  Network  Coding  for Delay  Constrained  Wireless  Systems  with Feedback, Ph.D Dissertation.
[14]  Kenneth  S.  J.  K.  (2000)  Construction  Of Binary Linear Codes. National University of Singapore.
[15]  Oliver  K.,  Lang  T.,  and  David  T.  (2009) Nonlinear  Network  Coding  is  Necessary  to Combat  General  Byzantine    Attacks.  Forty- Seventh Annual Allerton Conference Allerton House, UIUC, Illinois.