3.1 Pendahuluan
Lingkungan komputasi modern adalah campuran dari sub-lingkungan yang berbeda diuraikan dalam Bagian 2.1. Lingkungan ini terdiri dari orang, tempat dan hal-hal [109] yang berinteraksi satu sama lain dengan berbagai cara. Selain itu, orang dapat mengambil peran yang berbeda, tergantung pada apa waktu itu atau di mana mereka berada.
Hal-hal yang termasuk perangkat, ditambah objek komputasi, protokol jaringan dan aplikasi. Tempat masing-masing memiliki sifat unik mereka sendiri, yang dapat mempengaruhi interaksi antara unsur-unsur lainnya.
Sangat menarik untuk dicatat kesejajaran antara karakteristik dan ciri-ciri sistem yang kompleks. Pusat Studi Sistem Kompleks [120] menyatakan bahwa suatu sistem yang kompleks memiliki karakteristik sebagai berikut:
Agen-based Komponen dasar sistem ini adalah entitas yang berinteraksi dengan satu sama lain dengan berbagai cara:
Heterogen Para agen dan perilaku mereka yang beragam.
Dinamis Perilaku individu agen dapat berubah dari waktu ke waktu, sebagaimana komposisi dari sistem secara keseluruhan. Perilaku holistik sistem dari waktu ke waktu tidak linier atau bahkan kacau.
FeedBack Dinamika sistem didorong oleh umpan balik yang diterima oleh agen sebagai akibat dari tindakan mereka sendiri.
Organisasi Para agen tersebut akan disusun dalam struktur yang berbeda, baik yang melekat dalam sistem atau muncul dari interaksi antara agen (selforganisation).
Sistem Munculnya perilaku tingkat timbul dari interaksi antara agen lokal. Sebuah muncul fenomena yang dikenal dengan baik adalah diri organisasi.
Karena fitur ini, sistem yang kompleks yang sangat terukur, sebagaimana dicontohkan oleh, ekonomi dan sosial sistem biologis (antara lain) yang kita lihat dan berinteraksi dengan setiap hari. Sistem ini telah berevolusi struktur yang unik dan pola, dan terus berkembang dalam proses adaptasi berlangsung. Kemampuan ini untuk beradaptasi dengan kondisi perubahan, yang timbul sebagai akibat dari umpan balik atau pengaruh eksternal, membuat sistem ini sangat kuat.
Jika mensyaratkan bahwa hari lingkungan komputasi modern adalah sistem yang kompleks, tampaknya masuk akal untuk merancang aplikasi dan protokol jaringan dalam kerangka teori sistem yang kompleks. Secara khusus, penelitian ini berpendapat bahwa penemuan sumber daya protokol yang target lingkungan adalah suatu sistem yang kompleks mungkin akan mendapat keuntungan dengan memasukkan ide-ide dari bidang teori sistem yang kompleks.
Bagian berikut ini akan memberikan gambaran singkat mengenai sistem yang kompleks. Bagian 3.3 dan 3.4 menutup sistem fenomena yang kompleks yang penting bagi tesis ini. Bagian 3.5 mengusulkan sebuah query routing algoritma yang memanfaatkan konsep kemunculan dan adaptasi. Ini juga menjelaskan metode yang sebuah protokol peer-to-peer terstruktur (Chord [40]) dapat berpengaruh terhadap bebas routing topologi-besaran dengan menggunakan strategi caching yang tepat, sehingga kunci pencarian memakan waktu kurang. Akhirnya, Bagian 3.6 merangkum ide-ide kunci yang disajikan dalam bab ini, dengan maksud untuk menggunakan mereka dalam bab-bab berikutnya.
3.2 Sistem Kompleks: Latar Belakang
sistem yang kompleks adalah bidang yang relatif baru ilmu pengetahuan yang bersangkutan dengan cara di mana perilaku bagian dari suatu sistem menimbulkan perilaku global. Sebuah aspek kunci yang membedakan sistem yang kompleks dari sistem rumit adalah sifat interaksi antara komponen-komponen dalam sistem.Sebuah sistem yang rumit, seperti kapal selam nuklir, terdiri dari banyak komponen yang berinteraksi dalam mode diprediksi. Dalam bahasa sistem yang kompleks, seperti sistem dikenal sebagai akibat linier dengan urutan diprediksi sebab dan akibat. Sebuah sistem yang rumit (sebagai lawan satu kompleks) dapat terdiri dari ribuan komponen, tetapi komponen masing-masing memiliki satu set statis dengan komponen lain yang berinteraksi. Di sisi lain, sistem yang kompleks seperti masyarakat, ekonomi dan ekosistem, mengandung komponen yang sering berinteraksi dalam mode nonlinier. Sebuah contoh yang sering dikutip dari sebuah hubungan nonlinear adalah cara di mana efektivitas suatu perubahan obat tertentu sebagai dosis meningkat. obat mungkin benar-benar efektif sampai dosis ambang tercapai.Obat tetap efektif untuk dosis di atas batas ini sampai dosis menjadi terlalu tinggi.
Hubungan kompleks dapat menimbulkan perilaku muncul. Muncul perilaku adalah risiko yang timbul pada atau sistem tingkat global dan tidak dapat diprediksi dari mengamati perilaku komponen individu. Munculnya adalah formalisme belakang umum mengatakan "keseluruhan lebih besar daripada jumlah dari bagian-bagian".Beberapa contoh perilaku yang muncul adalah mereka diri-organisasi seperti berkelompok dan bergerombol pada burung dan serangga, dan tak terlihat tangan "Adam Smith" dimana sumber daya dalam suatu perekonomian dikatakan untuk menemukan jalan mereka ke tempat mereka yang paling efisien digunakan tanpa memerlukan mekanisme membimbing pusat [121]. Komputer jaringan seperti Internet mengorganisir diri dalam jaringan skala bebas. Dalam istilah sederhana, ini adalah jaringan di mana sebagian kecil dari node memiliki sejumlah besar link ke node lain, sedangkan node lain memiliki link lebih sedikit. Dalam istilah yang lebih formal, ini adalah jaringan distribusi yang gelar mengikuti power-law. pola muncul tersebut tidak unik untuk jaringan komputer. Memang, jaringan sosial, yang dibentuk oleh grafik propagasi penyakit dan sebagainya, semuanya telah ditemukan memiliki properti berskala bebas. Dalam banyak kasus, ketika pola muncul dan perilaku yang diamati, a-hukum distribusi daya terletak di jantung interaksi. Antara lain, aspek ilmu kompleksitas sedang digunakan untuk memerangi penyebaran virus, dan juga untuk mempelajari interaksi sosial.
Banyak sistem yang kompleks, terutama yang dikatakan kacau, sangat sensitif terhadap kondisi awal. Sebuah variasi kecil dalam kondisi mulai dapat mengakibatkan hasil yang jauh berbeda. Selain itu, memodifikasi salah satu bagian dari suatu sistem dinamik dapat memiliki mencapai dan non-proporsional konsekuensi yang jauh di bagian lain dari sistem. Gagasan ini umumnya dikenal sebagai efek kupu-kupu, sebuah istilah yang berasal dari gagasan bahwa kupu-kupu yang mengepakkan sayap di satu wilayah di dunia dapat mengakibatkan pembentukan siklon, tornado atau peristiwa cuaca utama di wilayah lain di dunia . Dalam model dan simulasi sistem yang kompleks, kondisi awal biasanya diwakili oleh parameter masukan. Perilaku ditampilkan oleh simulasi atau diprediksi dengan model sebagian besar tergantung pada parameter-parameter awal. Parameter-parameter awal akan memainkan peran penting dalam analisis disajikan dalam Bab 7. Kadang-kadang sistem akan menetap menjadi pola perilaku berulang. Pola-pola ini disebut attractor, dan mungkin mengambil salah satu dari beberapa bentuk. Jenis paling sederhana attractor adalah atraktor titik, dimana sistem mengendap menjadi negara tunggal. Contohnya adalah bergulir bola-bantalan sekitar mangkuk. Akhirnya datang berhenti pada titik terendah mangkuk. attractor siklik, atau siklus batas, jenis lain adalah pemikat. Dalam pola ini, perilaku sistem berosilasi antara himpunan terhingga titik tetap, dan pola mengulangi terus menerus. Contohnya adalah musim dalam setahun dan orbit bulan tentang bumi. attractor lainnya disebut aneh. Attractor ini menunjukkan perilaku kacau. Bab 7 menunjukkan bahwa perilaku dari protokol penemuan layanan yang dikembangkan dalam Bab 4 tertarik ke satu titik atau batas-siklus tergantung pada nilai parameter awal.
Sistem ini sering dinamis nonlinier dimodelkan dengan persamaan diferensial atau persamaan kambuh [122], yang masing-masing, dan diskrit inkarnasi terus menerus alat matematika yang sama [123]. Bab 7 memanfaatkan persamaan kambuh untuk model dinamika nonlinier dari protokol penemuan layanan yang disajikan dalam bab berikutnya.
Bagian ini telah disajikan gambaran singkat sistem yang sangat kompleks. Ia telah memperkenalkan hanya konsep-konsep yang penting bagi sisa tesis ini. Terdapat badan yang luas literatur tentang sistem yang kompleks, berikut ini adalah pilihan kecil publikasi yang menyediakan informasi lebih lanjut tentang daerah ini berkembang ilmu pengetahuan. Bar-Yam [124] memberikan gambaran tentang metode yang digunakan untuk mempelajari dan model sistem yang kompleks. Barab'asi [125] rincian kemajuan baru-baru ini dibuat dalam studi jaringan kompleks, dan Sol'e et al. [126] mengeksplorasi perbedaan dan persamaan antara kompleks bio-sistem dan jaringan kompleks yang diciptakan oleh manusia (seperti Internet dan jaringan leksikal). Akhirnya, Flake [127] menyajikan gambaran mendalam dalam kekacauan, sistem yang kompleks dan adaptasi.
Dua bagian berikut memberikan rincian sistem yang kompleks tertentu yang sangat mempengaruhi desain dari protokol penemuan layanan yang disajikan dalam tesis ini.
Lingkungan komputasi modern adalah campuran dari sub-lingkungan yang berbeda diuraikan dalam Bagian 2.1. Lingkungan ini terdiri dari orang, tempat dan hal-hal [109] yang berinteraksi satu sama lain dengan berbagai cara. Selain itu, orang dapat mengambil peran yang berbeda, tergantung pada apa waktu itu atau di mana mereka berada.
Hal-hal yang termasuk perangkat, ditambah objek komputasi, protokol jaringan dan aplikasi. Tempat masing-masing memiliki sifat unik mereka sendiri, yang dapat mempengaruhi interaksi antara unsur-unsur lainnya.
Sangat menarik untuk dicatat kesejajaran antara karakteristik dan ciri-ciri sistem yang kompleks. Pusat Studi Sistem Kompleks [120] menyatakan bahwa suatu sistem yang kompleks memiliki karakteristik sebagai berikut:
Agen-based Komponen dasar sistem ini adalah entitas yang berinteraksi dengan satu sama lain dengan berbagai cara:
Heterogen Para agen dan perilaku mereka yang beragam.
Dinamis Perilaku individu agen dapat berubah dari waktu ke waktu, sebagaimana komposisi dari sistem secara keseluruhan. Perilaku holistik sistem dari waktu ke waktu tidak linier atau bahkan kacau.
FeedBack Dinamika sistem didorong oleh umpan balik yang diterima oleh agen sebagai akibat dari tindakan mereka sendiri.
Organisasi Para agen tersebut akan disusun dalam struktur yang berbeda, baik yang melekat dalam sistem atau muncul dari interaksi antara agen (selforganisation).
Sistem Munculnya perilaku tingkat timbul dari interaksi antara agen lokal. Sebuah muncul fenomena yang dikenal dengan baik adalah diri organisasi.
Karena fitur ini, sistem yang kompleks yang sangat terukur, sebagaimana dicontohkan oleh, ekonomi dan sosial sistem biologis (antara lain) yang kita lihat dan berinteraksi dengan setiap hari. Sistem ini telah berevolusi struktur yang unik dan pola, dan terus berkembang dalam proses adaptasi berlangsung. Kemampuan ini untuk beradaptasi dengan kondisi perubahan, yang timbul sebagai akibat dari umpan balik atau pengaruh eksternal, membuat sistem ini sangat kuat.
Jika mensyaratkan bahwa hari lingkungan komputasi modern adalah sistem yang kompleks, tampaknya masuk akal untuk merancang aplikasi dan protokol jaringan dalam kerangka teori sistem yang kompleks. Secara khusus, penelitian ini berpendapat bahwa penemuan sumber daya protokol yang target lingkungan adalah suatu sistem yang kompleks mungkin akan mendapat keuntungan dengan memasukkan ide-ide dari bidang teori sistem yang kompleks.
Bagian berikut ini akan memberikan gambaran singkat mengenai sistem yang kompleks. Bagian 3.3 dan 3.4 menutup sistem fenomena yang kompleks yang penting bagi tesis ini. Bagian 3.5 mengusulkan sebuah query routing algoritma yang memanfaatkan konsep kemunculan dan adaptasi. Ini juga menjelaskan metode yang sebuah protokol peer-to-peer terstruktur (Chord [40]) dapat berpengaruh terhadap bebas routing topologi-besaran dengan menggunakan strategi caching yang tepat, sehingga kunci pencarian memakan waktu kurang. Akhirnya, Bagian 3.6 merangkum ide-ide kunci yang disajikan dalam bab ini, dengan maksud untuk menggunakan mereka dalam bab-bab berikutnya.
3.2 Sistem Kompleks: Latar Belakang
sistem yang kompleks adalah bidang yang relatif baru ilmu pengetahuan yang bersangkutan dengan cara di mana perilaku bagian dari suatu sistem menimbulkan perilaku global. Sebuah aspek kunci yang membedakan sistem yang kompleks dari sistem rumit adalah sifat interaksi antara komponen-komponen dalam sistem.Sebuah sistem yang rumit, seperti kapal selam nuklir, terdiri dari banyak komponen yang berinteraksi dalam mode diprediksi. Dalam bahasa sistem yang kompleks, seperti sistem dikenal sebagai akibat linier dengan urutan diprediksi sebab dan akibat. Sebuah sistem yang rumit (sebagai lawan satu kompleks) dapat terdiri dari ribuan komponen, tetapi komponen masing-masing memiliki satu set statis dengan komponen lain yang berinteraksi. Di sisi lain, sistem yang kompleks seperti masyarakat, ekonomi dan ekosistem, mengandung komponen yang sering berinteraksi dalam mode nonlinier. Sebuah contoh yang sering dikutip dari sebuah hubungan nonlinear adalah cara di mana efektivitas suatu perubahan obat tertentu sebagai dosis meningkat. obat mungkin benar-benar efektif sampai dosis ambang tercapai.Obat tetap efektif untuk dosis di atas batas ini sampai dosis menjadi terlalu tinggi.
Hubungan kompleks dapat menimbulkan perilaku muncul. Muncul perilaku adalah risiko yang timbul pada atau sistem tingkat global dan tidak dapat diprediksi dari mengamati perilaku komponen individu. Munculnya adalah formalisme belakang umum mengatakan "keseluruhan lebih besar daripada jumlah dari bagian-bagian".Beberapa contoh perilaku yang muncul adalah mereka diri-organisasi seperti berkelompok dan bergerombol pada burung dan serangga, dan tak terlihat tangan "Adam Smith" dimana sumber daya dalam suatu perekonomian dikatakan untuk menemukan jalan mereka ke tempat mereka yang paling efisien digunakan tanpa memerlukan mekanisme membimbing pusat [121]. Komputer jaringan seperti Internet mengorganisir diri dalam jaringan skala bebas. Dalam istilah sederhana, ini adalah jaringan di mana sebagian kecil dari node memiliki sejumlah besar link ke node lain, sedangkan node lain memiliki link lebih sedikit. Dalam istilah yang lebih formal, ini adalah jaringan distribusi yang gelar mengikuti power-law. pola muncul tersebut tidak unik untuk jaringan komputer. Memang, jaringan sosial, yang dibentuk oleh grafik propagasi penyakit dan sebagainya, semuanya telah ditemukan memiliki properti berskala bebas. Dalam banyak kasus, ketika pola muncul dan perilaku yang diamati, a-hukum distribusi daya terletak di jantung interaksi. Antara lain, aspek ilmu kompleksitas sedang digunakan untuk memerangi penyebaran virus, dan juga untuk mempelajari interaksi sosial.
Banyak sistem yang kompleks, terutama yang dikatakan kacau, sangat sensitif terhadap kondisi awal. Sebuah variasi kecil dalam kondisi mulai dapat mengakibatkan hasil yang jauh berbeda. Selain itu, memodifikasi salah satu bagian dari suatu sistem dinamik dapat memiliki mencapai dan non-proporsional konsekuensi yang jauh di bagian lain dari sistem. Gagasan ini umumnya dikenal sebagai efek kupu-kupu, sebuah istilah yang berasal dari gagasan bahwa kupu-kupu yang mengepakkan sayap di satu wilayah di dunia dapat mengakibatkan pembentukan siklon, tornado atau peristiwa cuaca utama di wilayah lain di dunia . Dalam model dan simulasi sistem yang kompleks, kondisi awal biasanya diwakili oleh parameter masukan. Perilaku ditampilkan oleh simulasi atau diprediksi dengan model sebagian besar tergantung pada parameter-parameter awal. Parameter-parameter awal akan memainkan peran penting dalam analisis disajikan dalam Bab 7. Kadang-kadang sistem akan menetap menjadi pola perilaku berulang. Pola-pola ini disebut attractor, dan mungkin mengambil salah satu dari beberapa bentuk. Jenis paling sederhana attractor adalah atraktor titik, dimana sistem mengendap menjadi negara tunggal. Contohnya adalah bergulir bola-bantalan sekitar mangkuk. Akhirnya datang berhenti pada titik terendah mangkuk. attractor siklik, atau siklus batas, jenis lain adalah pemikat. Dalam pola ini, perilaku sistem berosilasi antara himpunan terhingga titik tetap, dan pola mengulangi terus menerus. Contohnya adalah musim dalam setahun dan orbit bulan tentang bumi. attractor lainnya disebut aneh. Attractor ini menunjukkan perilaku kacau. Bab 7 menunjukkan bahwa perilaku dari protokol penemuan layanan yang dikembangkan dalam Bab 4 tertarik ke satu titik atau batas-siklus tergantung pada nilai parameter awal.
Sistem ini sering dinamis nonlinier dimodelkan dengan persamaan diferensial atau persamaan kambuh [122], yang masing-masing, dan diskrit inkarnasi terus menerus alat matematika yang sama [123]. Bab 7 memanfaatkan persamaan kambuh untuk model dinamika nonlinier dari protokol penemuan layanan yang disajikan dalam bab berikutnya.
Bagian ini telah disajikan gambaran singkat sistem yang sangat kompleks. Ia telah memperkenalkan hanya konsep-konsep yang penting bagi sisa tesis ini. Terdapat badan yang luas literatur tentang sistem yang kompleks, berikut ini adalah pilihan kecil publikasi yang menyediakan informasi lebih lanjut tentang daerah ini berkembang ilmu pengetahuan. Bar-Yam [124] memberikan gambaran tentang metode yang digunakan untuk mempelajari dan model sistem yang kompleks. Barab'asi [125] rincian kemajuan baru-baru ini dibuat dalam studi jaringan kompleks, dan Sol'e et al. [126] mengeksplorasi perbedaan dan persamaan antara kompleks bio-sistem dan jaringan kompleks yang diciptakan oleh manusia (seperti Internet dan jaringan leksikal). Akhirnya, Flake [127] menyajikan gambaran mendalam dalam kekacauan, sistem yang kompleks dan adaptasi.
Dua bagian berikut memberikan rincian sistem yang kompleks tertentu yang sangat mempengaruhi desain dari protokol penemuan layanan yang disajikan dalam tesis ini.
