COORDINATION AND AGREEMENT

DISTRIBUTED SYSTEMS Concept and Design – Fifth Edition
George Coulouris
Cambridge University
Jean Dollimore
formerly of Queen Mary, University of London
Tim Kindberg
matter 2 media
Gordon Blair
Lancaster University

Dalam bab ini , kami memperkenalkan beberapa topik dan algoritma yang berkaitan dengan masalah bagaimana proses mengkoordinasikan tindakan mereka dan menyepakati nilai-nilai bersama dalam sistem terdistribusi ,meskipun kegagalan . Bab ini dimulai dengan algoritma untuk mencapai saling pengecualian antara kumpulan proses , sehingga untuk mengkoordinasikan akses mereka ke sumber daya bersama . kelanjutannya untuk mengkaji bagaimana pemilu dapat diimplementasikan dalam sistem terdistribusi - yaitu, bagaimanasekelompok proses dapat menyepakati koordinator baru kegiatan mereka setelah sebelumnyaKoordinator telah gagal .
              Bagian kedua dari bab ini mengkaji masalah terkait kelompokkomunikasi , konsensus , kesepakatan Bizantium dan konsistensi interaktif . Dalam konteks komunikasi kelompok , masalah adalah bagaimana untuk menyepakati hal-hal seperti perintahdi mana pesan yang akan disampaikan . Konsensus dan masalah lain generalisasi dari ini : bagaimana bisa setiap koleksi proses menyepakati beberapa nilai , tidak peduli apa domain dari nilai-nilai tersebut ? Kami menemukan hasil mendasar dalam teori didistribusikan sistem : bahwa di bawah kondisi tertentu - termasuk kondisi kegagalan mengejutkan jinak - Tidak mungkin untuk menjamin bahwa proses akan mencapai konsensus .        
15.1 Pendahuluan  Bab ini memperkenalkan koleksi algoritma yang tujuan bervariasi tetapi pangsa bahwa tujuanyang mendasar dalam sistem terdistribusi: untuk serangkaian proses untuk mengkoordinasikan mereka tindakan atau setuju pada satu atau lebih nilai. Misalnya, dalam kasus sepotong kompleks mesin seperti sebuah pesawat ruang angkasa, adalah penting bahwa komputer mengendalikannya setuju pada kondisi seperti apakah misi pesawat ruang angkasa sekarang melanjutkan atau telah dibatalkan. Selain itu, komputer harus mengkoordinasikan tindakan mereka benar dengan hormat ke sumber daya bersama (sensor pesawat ruang angkasa dan aktuator). Komputer harus mampu untuk melakukannya bahkan di mana tidak ada hubungan tuan-budak tetap antara komponen (Yang akan membuat koordinasi khususnya sederhana). Alasan untuk penghindaran tetap hubungan tuan-budak adalah bahwa kita sering membutuhkan sistem kami tetap bekerja dengan benar bahkan jika kegagalan terjadi, jadi kita perlu untuk menghindari titik tunggal kegagalan, seperti master tetap.               Perbedaan penting bagi kita, seperti dalam Bab 14, akan menjadi apakah didistribusikan Sistem diteliti adalah asynchronous atau synchronous. Dalam sistem asynchronous kita bisa tidak membuat waktu asumsi. Dalam sistem sinkron, kita akan berasumsi bahwa ada batas pada keterlambatan transmisi pesan maksimum, pada waktu yang dibutuhkan untuk mengeksekusi setiap langkah dari proses, dan pada tingkat pergeseran jam. Asumsi sinkron memungkinkan kita untuk menggunakan timeout untuk mendeteksi proses crash.               Tujuan penting dari bab ini adalah untuk mempertimbangkan kegagalan , dan bagaimana menghadapi mereka ketika merancang algoritma . Bagian 2.4.2 memperkenalkan model kegagalan , yang kita akan digunakan dalam bab ini . Mengatasi kegagalan adalah bisnis yang halus , jadi kami mulai dengan mempertimbangkan beberapa algoritma yang mentolerir kegagalan dan kemajuan melalui jinak kegagalan sebelum menjelajahi bagaimana mentolerir kegagalan sewenang-wenang . Sepanjang jalan , kita temui hasil mendasar dalam teori sistem terdistribusi : bahkan di bawah mengejutkan jinak kondisi kegagalan , adalah mustahil untuk menjamin dalam sistem asynchronous bahwa kumpulan proses dapat menyepakati nilai bersama - misalnya , untuk semua pesawat ruang angkasa ini mengendalikan proses setuju ' misi melanjutkan ' atau ' misi batalkan ' .               Bagian 15.2 meneliti masalah didistribusikan pengecualian bersama. Ini adalah ekstensi untuk sistem terdistribusi dari masalah akrab menghindari kondisi lomba di kernel dan aplikasi multi-threaded. Sejak banyak dari apa yang terjadi pada didistribusikan sistem adalah berbagi sumber daya, ini merupakan masalah penting untuk memecahkan. Selanjutnya, Bagian 15.3 memperkenalkan isu terkait tetapi lebih umum tentang bagaimana 'memilih' salah satu koleksi proses untuk melakukan peran khusus. Misalnya, dalam Bab 14 kita melihat proses bagaimana sinkronisasi jam mereka ke waktu server yang ditunjuk. Jika server ini gagal dan beberapa selamat server dapat memenuhi peran itu, maka demi konsistensi perlu memilih hanya satu server untuk mengambil alih.               Koordinasi dan kesepakatan yang berkaitan dengan komunikasi kelompok adalah subjek Bagian 15.4. Sebagai Bagian 4.4.1 menjelaskan, kemampuan untuk multicast pesan ke grup ini paradigma komunikasi yang sangat berguna, dengan aplikasi dari lokasi sumber daya untuk mengkoordinasikan update data direplikasi. Bagian 15.4 memeriksa keandalan multicastdan memesan semantik, dan memberikan algoritma untuk mencapai variasi. Multicast pengiriman pada dasarnya adalah masalah kesepakatan antara proses: penerima setuju yang pesan mereka akan menerima, dan dalam urutan yang mereka akan menerima mereka. Bagian 15,5 membahas masalah perjanjian lebih umum, terutama dalam bentuk dikenal sebagai konsensus dan kesepakatan Bizantium.  Gambar 15.1 Sebuah partisi jaringan











Pengobatan diikuti dalam bab ini melibatkan menyatakan asumsi dantujuan yang harus dipenuhi, dan memberikan account informal mengapa algoritma yang disajikanbenar. Ada cukup ruang untuk memberikan pendekatan yang lebih ketat. Untuk itu, kamimerujuk pembaca untuk teks yang memberikan account menyeluruh dari algoritma terdistribusi, sepertiAttiya dan Welch [1998] dan Lynch [1996].Sebelum menyajikan masalah dan algoritma, kita membahas asumsi kegagalandan masalah praktis mendeteksi kegagalan dalam sistem terdistribusi.     15.1.1 Asumsi Kegagalan dan detektor kegagalan Demi kesederhanaan, bab ini mengasumsikan bahwa setiap pasangan proses terhubung oleh saluran handal. Artinya, meskipun komponen jaringan yang mendasarinya mungkin menderitakegagalan, proses menggunakan protokol komunikasi yang handal yang topeng kegagalan ini -missalnya, dengan transmisi ulang hilang atau rusak pesan. Juga demi kesederhanaan, kita mengasumsikan bahwa tidak ada kegagalan proses menyiratkan ancaman bagi proses lainnya 'kemampuan untuk berkomunikasi. Ini berarti bahwa tidak ada proses tergantung lain untukpesan ke depan.               Perhatikan bahwa saluran diandalkan akhirnya memberikan pesan ke masukan penerima penyangga. Dalam sistem sinkron, kita menganggap bahwa ada redundansi hardware mana diperlukan, sehingga saluran handal tidak hanya pada akhirnya memberikan setiap pesan meskipun mendasari kegagalan, tetapi melakukannya dalam waktu tertentu terikat.               Dalam setiap selang waktu tertentu, komunikasi antara beberapa proses mungkin berhasil sementara komunikasi antara lain tertunda. Misalnya, kegagalan router antara dua jaringan mungkin berarti bahwa koleksi empat proses dibagi menjadi dua pasang, sehingga intra-pair komunikasi adalah mungkin melalui jaringan masing-masing; tapi antar-pair komunikasi tidak mungkin sementara router telah gagal. Ini diketahui sebagai partisi jaringan (Gambar 15.1). Melalui jaringan point-to-point seperti Internet, topologi kompleks dan independen routing yang pilihan berarti bahwa konektivitas mungkin asimetris: komunikasi adalah mungkin dari proses p untuk memproses q, tetapi tidak sebaliknya. Konektivitas juga mungkin intransitif: komunikasi adalah mungkin dari p ke q dan dari q untuk r, tapi p tidak dapat berkomunikasi langsung dengan Jadi asumsi kehandalan kami memerlukan yang akhirnya setiap gagal link atau router akan diperbaiki atau dielakkan. Namun, proses mungkin tidak semua dapat berkomunikasi pada waktu yang sama.                Bab ini mengasumsikan, kecuali kita menyatakan sebaliknya, bahwa proses gagal hanya dengan menerjang - sebuah asumsi yang cukup baik untuk banyak sistem. Dalam Bagian 15.5, kita akan mempertimbangkan bagaimana memperlakukan kasus di mana proses memiliki sewenang-wenang (Bizantium) kegagalan. Apapun jenis kegagalan, sebuah proses yang benar adalah salah satu yang menunjukkan tidak ada kegagalan pada setiap titik di eksekusi di bawah pertimbangan. Perhatikan bahwa kebenaran berlaku untuk seluruh eksekusi, tidak hanya untuk bagian dari itu. Jadi proses yang menderita kegagalan kecelakaan adalah 'non-gagal' sebelum titik itu, tidak 'benar' sebelum titik itu.               Salah satu masalah dalam desain algoritma yang dapat mengatasi proses crash adalah bahwa memutuskan kapan suatu proses telah jatuh. Sebuah detektor kegagalan [Chandra dan Toueg 1996, Stelling et al. 1998] adalah layanan yang memproses pertanyaan tentang apakah tertentu Proses telah gagal. Hal ini sering dilaksanakan oleh sebuah objek lokal untuk setiap proses (pada sama komputer) yang menjalankan algoritma kegagalan-deteksi dalam hubungannya dengan yang rekan-rekan di proses lainnya. objek lokal untuk setiap proses yang disebut kegagalan lokal detektor. Kami menjelaskan bagaimana menerapkan detektor kegagalan lama, tapi pertama kami berkonsentrasi pada beberapa sifat dari detektor kegagalan.                Kegagalan 'detektor' belum tentu akurat. Sebagian jatuh ke dalam kategoridetektor kegagalan tidak dapat diandalkan. Detektor kegagalan tidak dapat diandalkan dapat menghasilkan salah satu dari dua nilai ketika diberikan identitas proses: Tak disangka atau Diduga. Kedua hasilnya petunjuk, yang mungkin atau mungkin tidak secara akurat mencerminkan apakah proses memiliki sebenarnya gagal. Sebuah hasil Tak disangka menandakan bahwa detektor baru-baru ini menerima bukti yang menunjukkan bahwa proses tidak gagal; misalnya, pesan baru-baru ini diterima dari itu. Tapi tentu saja, proses tersebut mungkin telah gagal sejak saat itu. Sebuah hasil Diduga menandakan bahwa detektor kegagalan memiliki beberapa indikasi bahwa proses dapat telah gagal. Sebagai contoh, mungkin bahwa ada pesan dari proses telah diterima selama lebih dari panjang maksimum nominal diam (bahkan dalam sistem asynchronous, batas atas praktis dapat digunakan sebagai petunjuk). Kecurigaan mungkin salah: untuk Misalnya, proses dapat berfungsi dengan benar tapi di sisi lain dari jaringan partisi, atau bisa berjalan lebih lambat dari yang diharapkan.               Sebuah detektor kegagalan diandalkan adalah salah satu yang selalu akurat dalam mendeteksi proses ini kegagalan. Ini menjawab pertanyaan proses 'dengan baik respon Tak disangka - yang, seperti sebelumnya, hanya bisa menjadi petunjuk - atau Gagal. Sebuah hasil Gagal berarti bahwa detektor memiliki ditentukan bahwa proses telah jatuh. Ingat bahwa sebuah proses yang memiliki jatuh tetap yang cara, karena dengan definisi proses tidak pernah mengambil langkah lain setelah telah jatuh. Adalah penting untuk menyadari bahwa, meskipun kita berbicara tentang salah satu detektor kegagalan bertindak untuk kumpulan proses, respon yang detektor kegagalan memberikan suatu proses hanya sebagus informasi yang tersedia pada proses itu. Sebuah detektor kegagalan mungkin kadang-kadang memberikan respon yang berbeda untuk proses yang berbeda, karena kondisi komunikasi bervariasi dari proses ke proses.               Kita bisa menerapkan detektor kegagalan diandalkan menggunakan algoritma berikut. Setiap proses p mengirimkan 'p sini' pesan ke proses lainnya, dan hal ini setiap detik T. Detektor gagal menggunakan perkiraan transmisi pesan maksimum saat detik D. Jika detektor kegagalan lokal di proses q tidak menerima 'p sini' Pesan dalam T + D detik dari yang terakhir, maka laporan untuk q yang p Diduga. Namun, jika kemudian menerima 'p sini' pesan, maka laporan untuk q bahwa p OKE.               Dalam sistem terdistribusi nyata, ada batas-batas praktis tentang transmisi pesan kali. Bahkan sistem email menyerah setelah beberapa hari, karena kemungkinan komunikasi yang link dan router akan telah diperbaiki pada waktu itu. Jika kita memilih nilai kecil untuk T dan D (sehingga mereka total 0,1 detik, mengatakan), maka detektor kegagalan cenderung mencurigai proses non-jatuh berkali-kali, dan banyak bandwidth akan diambil dengan 'p di sini 'pesan. Jika kita memilih besar nilai timeout (seminggu, mengatakan), kemudian jatuh proses akan sering dilaporkan sebagai Tak disangka. Sebuah solusi praktis untuk masalah ini adalah dengan  kondisi jaringan delay yang diamati. Jika detektor kegagalan lokal menerima 'p sini' di 20 detik bukan maksimum yang diharapkan dari 10 detik, itu dapat me-reset nilai timeout-nya untuk p sesuai. Detektor kegagalan tetap tidak dapat diandalkan, dan jawaban untuk pertanyaan yang masih hanya petunjuk, tapi kemungkinan akurasi meningkat.               Dalam sistem sinkron, detektor kegagalan kita dapat dibuat menjadi salah satu yang handal. Kami dapat memilih D sehingga tidak perkiraan tapi terikat mutlak pada transmisi pesan kali; tidak adanya 'p sini' pesan dalam T + D detik hak lokal Kegagalan detektor untuk menyimpulkan bahwa p telah jatuh. pembaca mungkin bertanya-tanya apakah detektor kegagalan adalah dari penggunaan praktis. detektor kegagalan tidak dapat diandalkan mungkin menduga proses yang tidak gagal (mereka mungkin akurat), dan mereka mungkin tidak menduga proses yang sebenarnya telah gagal (mereka mungkin tidak lengkap). detektor kegagalan diandalkan, di sisi lain, mengharuskan sistem ini sinkron (dan beberapa sistem praktis). Kami telah memperkenalkan detektor gagal karena mereka membantu kita untuk berpikir tentang sifat kegagalan dalam sistem terdistribusi. Dan sistem praktis yang dirancang untuk mengatasi kegagalan harus mendeteksi mereka - namun tidak sempurna. Tapi ternyata bahwa bahkan detektor kegagalan tidak dapat diandalkan dengan sifat yang terdefinisi tertentu dapat membantu kita untuk memberikan solusi praktis untuk masalah koordinasi proses di hadapan kegagalan. Kami kembali ke titik ini dalam Bagian 15.5.  15.2 Distributed pengecualian saling                Proses didistribusikan sering perlu untuk mengkoordinasikan kegiatan mereka. Jika koleksiproses berbagi sumber daya atau koleksi sumber daya, maka sering saling pengecualian adalah diperlukan untuk mencegah gangguan dan memastikan konsistensi ketika mengakses sumber daya. Ini adalah masalah critical section, familiar dalam domain sistem operasi. Di sebuah sistem, variabel Namun, tidak didistribusikan bersama atau fasilitas yang disediakan oleh satu kernel lokal dapat digunakan untuk mengatasinya, pada umumnya. Kami membutuhkan solusi untuk didistribusikan mutual exclusion: satu yang hanya didasarkan pada pesan lewat.Dalam beberapa kasus sumber daya bersama yang dikelola oleh server yang juga menyediakan mekanisme untuk saling pengecualian - Bab 16 menjelaskan bagaimana beberapa server sinkronisasi client akses ke sumber daya. Namun dalam beberapa kasus praktis, mekanisme terpisah untuk mutual exclusion diperlukan.               Pertimbangkan pengguna yang memperbarui file teks. Sebuah cara sederhana untuk memastikan bahwa mereka update konsisten adalah untuk memungkinkan mereka untuk mengaksesnya hanya satu pada satu waktu, dengan mewajibkan para editor untuk mengunci file sebelum update dapat dibuat. File server NFS, dijelaskan pada Bab 12, dirancang untuk menjadi stateless dan karena itu tidak mendukung penguncian berkas. Untuk alasan ini, sistem UNIX menyediakan layanan file-locking terpisah, dilaksanakan oleh daemon lockd, untuk menangani mengunci permintaan dari klien.               Sebuah contoh yang sangat menarik adalah di mana tidak ada server, dan koleksiproses rekan harus mengkoordinasikan akses mereka ke sumber daya bersama di antara mereka sendiri. ini terjadi secara rutin pada jaringan seperti Ethernets dan IEEE 802.11 jaringan nirkabel di 'ad hoc' mode, di mana antarmuka jaringan bekerja sama sebagai rekan-rekan sehingga hanya satu node mentransmisikan pada waktu pada media bersama. Pertimbangkan, juga, sebuah sistem pemantauan jumlah lowongan di parkir mobil dengan proses di setiap pintu masuk dan keluar yang melacak jumlah kendaraan yang masuk dan meninggalkan. Setiap proses menyimpan hitungan jumlah kendaraan dalam parkir dan menampilkan apakah atau tidak itu adalah penuh. Proses harus memperbarui hitungan bersama jumlah kendaraan secara konsisten. Ada beberapa cara mencapai itu, tapi itu akan mudah untuk proses ini untuk dapat memperoleh mutual exclusion hanya dengan berkomunikasi di antara mereka sendiri, menghilangkan kebutuhan untuk server terpisah.               Hal ini berguna untuk memiliki mekanisme generik untuk didistribusikan pengecualian saling di kami pembuangan - salah satu yang independen dari skema pengelolaan sumber daya tertentu di pertanyaan. Kami sekarang memeriksa beberapa algoritma untuk mencapai itu.  15.2.1 Algoritma untuk saling pengecualian Kami menganggap sistem N proses pi i = 1 2 N, yang tidak berbagi variabel. Proses mengakses sumber daya umum, tetapi mereka melakukannya di bagian kritis. Demi kesederhanaan, kita mengasumsikan bahwa hanya ada satu bagian kritis. Hal ini mudah untuk memperpanjang algoritma kami hadir untuk lebih dari satu bagian kritis. Kami berasumsi bahwa sistem ini asynchronous, bahwa proses tidak gagal dan bahwa pengiriman pesan dapat diandalkan, sehingga setiap pesan yang dikirim akhirnya disampaikan utuh, tepat sekali. Protokol tingkat aplikasi untuk mengeksekusi bagian kritis adalah sebagai berikut: masukkan () // critical section - blok jika perlu resourceAccesses () // akses bersama sumber daya di bagian kritis exit () // meninggalkan bagian kritis - proses lainnya sekarang dapat masuk persyaratan utama kami untuk saling pengecualian adalah sebagai berikut: ME1: (safety) Paling banyak satu proses dapat mengeksekusi pada bagian kritis (CS) pada suatu waktu. ME2: (liveness) Permintaan untuk masuk dan keluar bagian kritis akhirnya berhasil. Kondisi ME2 menyiratkan kebebasan dari kedua kebuntuan dan kelaparan. Sebuah kebuntuan akan melibatkan dua atau lebih dari proses menjadi terjebak tanpa batas saat mencoba masuk atau keluar dari bagian kritis, berdasarkan saling ketergantungan mereka. tetapi bahkan tanpa kebuntuan, algoritma yang buruk mungkin menyebabkan kelaparan: yang tak terbatas penundaan entri untuk proses yang telah meminta itu. Tidak adanya kelaparan adalah kondisi keadilan. Masalah keadilan lain adalah urutan proses memasuki critical section.                Hal ini tidak memungkinkan untuk memesan masuk ke critical section oleh kali bahwa proses meminta itu, karena tidak adanya jam global. Tapi persyaratan keadilan berguna yang kadang-kadang membuat memanfaatkan yang terjadi-sebelum memesan (Bagian 14.4) antara pesan yang meminta masuk ke bagian kritis. 15.2 Server mengelola token pengecualian saling untuk serangkaian proses                        ME3: pemesanan) Jika salah satu permintaan untuk memasukkan CS terjadi-      sebelum lain,   kemudian     masuk ke CS diberikan dalam urutan itu. Jika solusi memberikan masuk ke bagian penting dalam terjadi-sebelum pesanan, dan jika semua permintaan terkait deng  an terjadi-sebelumnya, maka tidak mungkin bagi suatu proses untuk memasukkan bagian kritis lebih dari sekali sementara menunggu yang lain untuk masuk. pemesanan ini juga memungkinkan proses untuk mengkoordinasikan akses mereka ke bagian kritis. Sebuah proses multi-threaded dapat terus dengan proses lain sementara thread menunggu untuk diberikan masuk ke kritis bagian. Selama ini, mungkin mengirim pesan ke proses lain,yang akibatnya juga mencoba untuk memasuki critical section. ME3 menetapkan bahwa proses pertama diberikan akses sebelum kedua.               Kami mengevaluasi kinerja algoritma untuk saling pengecualian menurut kriteria sebagai berikut:• bandwidth yang dikonsumsi, yang sebanding dengan jumlah pesan yang dikirim di setiap masuk dan keluar operasi;• keterlambatan klien yang dikeluarkan oleh proses di setiap operasi masuk dan keluar;• efek algoritma ini pada throughput sistem. Ini adalah tingkat di mana koleksi proses secara keseluruhan dapat mengakses bagian penting, mengingat bahwa beberapa komunikasi yang diperlukan antara proses berturut-turut. Kami mengukur efek menggunakan delay sinkronisasi antara satu proses keluar kritis bagian dan proses selanjutnya memasuki itu; throughput yang lebih besar ketika sinkronisasi delay yang lebih pendek.                Kami tidak mengambil pelaksanaan dari sumber daya akses ke rekening dalam deskripsi kami. Kami, bagaimanapun, menganggap bahwa proses klien yang berperilaku baik dan menghabiskan terbatas waktu mengakses sumber daya di dalam bagian kritis mereka. Algoritma server pusat • Gambar 15.2 Server mengelola token pengecualian saling untuk serangkaian proses Server 1. Permintaan token antrian Permintaan 2. Rilis token 3. Hibah Token p 4 p p 3 2 p 1 2 4 Cara termudah untuk mencapai saling pengecualian adalah untuk mempekerjakan server yang memberikan izin untuk memasuki critical section. Gambar 15.2 menunjukkanpenggunaan server ini.        Gambar 15.3 Sebuah cincin dari proses mentransfer token pengecualian saling             Untuk memasukkan bagian kritis, proses mengirim pesan permintaan ke server dan menunggu balasan dari itu. Secara konseptual, jawabannya merupakan tokenmenandakan izin untuk memasuki critical section. Jika tidak ada proses lain memiliki tanda di waktu permintaan, maka server menjawab segera, pemberian token. Jika token saat ini dipegang oleh proses lain, maka server tidak menjawab, tapi antrian yang permintaan. Ketika sebuah proses keluar bagian kritis, ia akan mengirimkan pesan ke server, memberikan itu kembali token. Jika antrian proses menunggu tidak kosong, maka server memilih tertua masuk dalam antrian, menghapus dan membalas proses yang sesuai. Yang terpilih Proses kemudian memegang token. Dalam gambar, kami menunjukkan situasi di mana permintaan p2 's telah ditambahkan ke antrian, yang sudah berisi permintaan p4 's. p3 keluar dari bagian kritis, dan server menghapus entri dan hibah izin p4 's untuk masuk ke p4 dengan membalas itu. Proses p1 tidak saat ini membutuhkan masuk ke bagian kritis. Mengingat asumsi kami bahwa tidak ada kegagalan terjadi, mudah untuk melihat bahwa keselamatan dan kondisi liveness dipenuhi oleh algoritma ini. pembaca harus memverifikasi, bagaimanapun, bahwa algoritma tidak memuaskan properti ME3. Kami sekarang mengevaluasi kinerja algoritma ini. Memasuki bagian kritis . Bahkan ketika tidak ada proses saat ini menempati itu - mengambil dua pesan (permintaan diikuti oleh hibah) dan penundaan proses meminta dengan waktu yang diperlukan untuk ini pulang-pergi. Keluar bagian penting mengambil satu pesan rilis. Dengan asumsi pesan asynchronous lewat, ini tidak menunda proses keluar. server mungkin menjadi hambatan kinerja sistem secara keseluruhan. Itu sinkronisasi delay adalah waktu yang dibutuhkan untuk pulang-pergi: pesan rilis ke server, diikuti dengan pesan hibah untuk proses selanjutnya untuk memasuki critical section.Sebuah algoritma berbasis cincin • Gambar 15.3 Sebuah cincin dari proses mentransfer token pengecualian salingp1 Salah satu cara paling sederhana untuk mengatur saling pengecualian antara proses N tanpa memerlukan proses tambahan untuk mengatur mereka secara logiscincin. Ini hanya membutuhkan bahwa setiap proses pi memiliki saluran komunikasi ke depan Proses di atas ring, pi + 1mod N. Idenya adalah pengecualian yang diberikan dengan mendapatkan Token dalam bentuk pesan lulus dari proses ke proses dalam satu arah - searah jarum jam, katakan - di sekitar ring. Topologi cincin mungkin tidak berhubungan dengan fisik interkoneksi antara komputer yang mendasari.               Jika proses tidak perlu memasukkan bagian kritis ketika menerima token, kemudian segera meneruskan token untuk tetangganya. Sebuah proses yang membutuhkan token menunggu sampai menerima itu, tapi mempertahankan itu. Untuk keluar dari critical section, proses mengirim token ke tetangganya.Susunan proses ditunjukkan pada Gambar 15.3. Hal ini mudah untuk memverifikasi bahwa kondisi ME1 dan ME2 dipenuhi oleh algoritma ini, tapi itu token adalah belum tentu diperoleh dalam rangka terjadi-sebelumnya. (Ingat bahwa proses dapat bertukar pesan secara independen dari rotasi token.) Algoritma ini terus mengkonsumsi bandwidth jaringan (kecuali bila proses di dalam bagian kritis): proses mengirim pesan sekitar ring bahkan bila tidak ada proses membutuhkan masuk ke bagian kritis. Penundaan yang dialami oleh Proses meminta masuk ke bagian kritis adalah antara 0 pesan (ketika itu baru saja menerima token) dan pesan N (ketika itu baru saja lulus pada token). Untuk keluar bagian kritis hanya membutuhkan satu pesan. Sinkronisasi delay antara satu Proses ini keluar dari bagian kritis dan proses selanjutnya entry mana saja dari 1 untuk transmisi pesan N. Algoritma menggunakan jam multicast dan logis • Gambar 15.4 Ricart dan Agrawala Algoritma pada inisialisasinegara: = RELEASED;Untuk memasukkan bagiannegara: = WANTED;permintaan multicast untuk semua proses;T: = permintaan ini timestamp;Tunggu sampai (jumlah jawaban yang diterima = (N - 1));negara: = HELD;Pada saat menerima permintaan <Ti, pi> di pj (i j)jika (state = HELD atau (state = WANTED dan (T, pj) <(Ti, pi)))kemudianantrian permintaan dari pi tanpa menjawab;lainbalas segera pi;berakhir jikaUntuk keluar dari bagian kritisnegara: = RELEASED;membalas permintaan antri; Permintaan pengolahan ditangguhkan siniRicart dan Agrawala [1981] dikembangkanalgoritma untuk mengimplementasikan mutual exclusion antara proses rekan N yang berdasarkan multicast. Ide dasarnya adalah bahwa proses yang membutuhkan masuk ke bagian kritis multicast pesan permintaan, dan bisa masuk hanya ketika semua proses lainnya memiliki membalas pesan ini. Kondisi di mana proses balasan untuk permintaan yang dirancang untuk memastikan bahwa kondisi ME1-ME3 terpenuhi. Proses p1 p2 pN menanggung pengidentifikasi numerik yang berbeda. Mereka diasumsikan untuk memiliki saluran komunikasi satu sama lain, dan setiap proses pi menyimpan Jam Lamport, diperbarui sesuai dengan LC1 aturan dan LC2 Bagian 14,4. Pesan meminta masuk adalah dari bentuk <T pi >, di mana T adalah cap pengirim dan pi adalah pengenal pengirim. Setiap proses mencatat negaranya berada di luar bagian kritis (RELEASED), ingin masuk (WANTED) atau berada di bagian kritis (HELD) dalam keadaan variabel. Itu protokol diberikan pada Gambar 15.4. Jika entri permintaan proses dan keadaan semua proses lain RELEASED, maka semua proses akan segera membalas permintaan dan pemohon akan mendapatkan entri. Jika beberapa proses dalam keadaan HELD, maka proses yang tidak akan membalas permintaan sampai memiliki selesai dengan bagian kritis, sehingga pemohon tidak bisa mendapatkan masuk sementara itu. Jika dua atau lebih proses meminta masuk pada saat yang sama, maka mana proses ini permintaan menyandang cap terendah akan menjadi yang pertama untuk mengumpulkan N - 1 balasan, pemberian itu entri berikutnya. Jika permintaan menanggung cap waktu Lamport sama, permintaan yang diperintahkan menurut pengidentifikasi sesuai proses '. Perhatikan bahwa, ketika permintaan proses entri, itu menangguhkan permintaan pengolahan dari proses lainnya sampai permintaan sendiri telah mengirim dan telah mencatat T timestamp permintaan. Hal ini dimaksudkan agar proses membuat keputusan yang konsisten saat memproses permintaan. Algoritma ini mencapai properti keselamatan ME1. Jika mungkin untuk dua proses pi dan pj (i j) untuk memasuki critical section pada saat yang sama, maka kedua proses tersebut harus telah membalas lainnya. Tapi karena pasangan <Ti pi > adalah benar-benar memerintahkan, ini tidak mungkin. Kami meninggalkan pembaca untuk memverifikasi bahwa algoritma juga memenuhi persyaratan ME2 dan ME3. Untuk menggambarkan algoritma, mempertimbangkan situasi yang melibatkan tiga proses, p1, p2 dan p3, yang ditunjukkan pada Gambar 15.5  Gambar 15.5 Multicast sinkronisasi   . Mari kita asumsikan p3 yang tidak tertarik dalam memasukibagian kritis, dan bahwa p1 dan p2 permintaan masuk secara bersamaan. Timestamp dari p1 inipermintaan adalah 41, dan bahwa dari p2 adalah 34. Ketika p3 menerima permintaan mereka, balasansegera. Ketika p2 menerima permintaan p1 ini, ia menemukan bahwa permintaan sendiri memiliki lebih rendahtimestamp dan tidak membalas, memegang p1 off. Namun, p1 menemukan bahwa permintaan p2 'smemiliki timestamp lebih rendah dari permintaan sendiri dan balasan segera. Dimenerima balasan kedua ini, p2 dapat memasuki critical section. Ketika p2 keluar kritisbagian, itu akan membalas permintaan p1 's dan mengabulkannya entri.Mendapatkan masuk mengambil 2N - 1 pesan dalam algoritma ini: N - 1 untuk multicast yangpermintaan, diikuti oleh N - 1 balasan. Atau, jika ada dukungan hardware untuk multicast, hanyasatu pesan diperlukan untuk permintaan; totalnya kemudian pesan N. Dengan demikian lebihalgoritma mahal, dalam hal konsumsi bandwidth, daripada algoritma hanyadijelaskan. Namun, keterlambatan klien dalam meminta masuk lagi waktu pulang-pergi(Mengabaikan keterlambatan yang terjadi di multicasting pesan permintaan).Keuntungan dari algoritma ini adalah bahwa penundaan sinkronisasi hanya satuwaktu transmisi pesan. Kedua algoritma sebelumnya dikeluarkan pulang-pergisinkronisasi delay.Kinerja algoritma dapat ditingkatkan. Pertama, perhatikan bahwa prosesyang terakhir memasuki bagian kritis dan tidak menerima permintaan lain untuk itu masih berlangsungmelalui protokol seperti yang dijelaskan, meskipun itu hanya bisa memutuskan secara lokal untuk masuk kembalibagian kritis. Kedua, Ricart dan Agrawala halus protokol ini sehingga memerlukanN pesan untuk mendapatkan masuk dalam terburuk (dan umum) kasus, tanpa dukungan hardwareuntuk multicast. Hal ini dijelaskan dalam Raynal [1988].algoritma voting Maekawa ini • Maekawa [1985] mengamati bahwa dalam rangka untuk proses untukmasukkan bagian kritis, tidak perlu untuk semua rekan-rekan untuk memberikan akses. proseshanya perlu mendapatkan izin masuk dari subset dari rekan-rekan mereka, asalkan subsetdigunakan oleh dua proses tumpang tindih. Kami bisa memikirkan proses sebagai suara untuk satu sama lainuntuk memasuki critical section. A 'calon' proses harus mengumpulkan suara yang cukup untuk masuk.Proses di persimpangan dua set pemilih memastikan properti keselamatan ME1, yangpaling banyak satu proses dapat memasuki critical section, dengan memberikan suara mereka untuk hanya satucalon.Maekawa terkait satu set voting Vi dengan masing-masing pi proses (i = 1 2 N),di mana Vi p1 p1 pN . Set Vi dipilih sehingga, untuk semua i j = 1 2 N:• pi Vi • Vi Vj - ada setidaknya satu anggota umum dari dua set voting• Vi = K - untuk menjadi adil, setiap proses memiliki satu set suara dengan ukuran yang sama• Setiap pj proses yang terkandung dalam M pemungutan suara set Vi.Maekawa menunjukkan bahwa solusi optimal, yang meminimalkan K dan memungkinkanproses untuk mencapai saling pengecualian, memiliki K N dan M = K (sehingga setiap prosesdalam beberapa set voting karena ada unsur di setiap salah satu dari mereka set). Hal ini trivialuntuk menghitung optimal set Ri. Sebagai perkiraan, cara yang mudah untuk menurunkanset Ri sehingga Ri 2 N adalah menempatkan proses dalam N dengan N matriks dan membiarkanVi menjadi persatuan baris dan kolom yang berisi pi.Algoritma Maekawa ini yang ditampilkan pada Gambar 15.6. Untuk mendapatkan masuk ke kritisbagian, proses pi mengirimkan pesan permintaan kepada semua anggota K Vi (termasuk dirinya sendiri).pi tidak bisa masuk ke bagian kritis sampai telah menerima semua pesan balasan K. Ketika sebuahProses pj di Vi menerima pi 's pesan permintaan, ia akan mengirimkan pesan balasan segera,640 BAB 15 KOORDINASI DAN PERJANJIANkecuali salah negaranya adalah HELD atau sudah membalas ( 'sebagai') sejak terakhir menerimaPesan rilis. Jika tidak, itu antrian pesan permintaan (dalam urutan kedatangannya)tapi belum membalas. Ketika sebuah proses menerima pesan rilis, menghilangkan kepalaantrian yang permintaan yang luar biasa (jika antrian tidak kosong) dan mengirimkan balasanPesan (a 'suara') dalam menanggapi hal itu. Untuk meninggalkan bagian kritis, pi mengirimkan rilispesan ke semua anggota K Vi (termasuk dirinya sendiri).Gambar 15.6 Algoritma Maekawa inipada inisialisasinegara: = RELEASED;sebagai: = SALAH;Untuk masuk ke bagian kritisnegara: = WANTED;permintaan multicast untuk semua proses dalam;Tunggu sampai (jumlah jawaban yang diterima = K);negara: = HELD;Pada saat menerima permintaan dari dijika ( state = HELD atau sebagai = TRUE )kemudianantrian permintaan dari tanpa menjawab ;lainmengirim balasan ke ;sebagai : = TRUE;berakhir jikaUntuk keluar bagian kritisnegara : = RELEASED ;rilis multicast untuk semua proses dalam ;Pada saat menerima siaran dari dijika ( antrian permintaan tidak kosong )kemudianmenghapus kepala antrian - dari, mengatakan ;mengirim balasan ke ;sebagai : = TRUE;lainsebagai : = SALAH ;berakhir jikapiVipi pjpipipiVipi pjpkpkAlgoritma ini mencapai properti keselamatan , ME1 . Jika mungkin untuk duaproses-proses pi dan pj untuk memasuki critical section pada saat yang sama , maka proses diVi Vj harus telah memilih keduanya. Tapi algoritma memungkinkan proses untukmembuat paling banyak satu suara antara penerimaan berturut pesan rilis , jadi iniSituasi tidak mungkin .Sayangnya, algoritma adalah kebuntuan rawan. Perhatikan tiga proses, p1, p2dan p3, dengan V1 p1 p2 = , V2 p2 p3 = dan V3 p3 p1 = . Jika tiga proses secara bersamaan meminta masuk ke bagian kritis, maka dimungkinkan untuk p1untuk membalas sendiri dan menahan p2, untuk p2 untuk membalas sendiri dan menahan p3, dan untuk p3 untukmembalas sendiri dan menahan p1. Setiap proses telah menerima satu dari dua balasan, dantidak dapat melanjutkan.algoritma dapat disesuaikan [Sanders 1987] sehingga menjadi jalan buntu bebas. Diprotokol disesuaikan, proses antrian permintaan yang luar biasa dalam rangka terjadi-sebelumnya, sehinggabahwa kebutuhan ME3 juga puas.pemanfaatan bandwidth algoritma adalah 2 N pesan per masuk ke kritisbagian dan N pesan per exit (dengan asumsi tidak ada hardware fasilitas multicast). Jumlah seluruhnyadari 3 N unggul dengan 2N - 1 pesan yang dibutuhkan oleh Ricart dan Agrawala inialgoritma, jika N> 4. Klien delay adalah sama dengan Ricart dan Agrawala inialgoritma, tapi delay sinkronisasi lebih buruk: waktu round-trip bukannya satuwaktu transmisi pesan.Toleransi kesalahan • Poin utama yang perlu dipertimbangkan ketika mengevaluasi algoritma di atassehubungan dengan toleransi kesalahan adalah:• Apa yang terjadi ketika pesan yang hilang?• Apa yang terjadi ketika proses crash?Tak satu pun dari algoritma yang kita telah dijelaskan akan mentolerir hilangnya pesan, jika saluran yang bisa diandalkan. Algoritma berbasis-ring tidak bisa mentolerir kegagalan kecelakaan setiap proses tunggal. Seperti berdiri, algoritma Maekawa dapat mentolerir beberapa proses kecelakaan kegagalan: jika proses jatuh tidak di set suara yang diperlukan, maka kegagalan tidak akan mempengaruhi proses lainnya. Algoritma server pusat dapat mentolerir kegagalan kecelakaan proses klien yang tidak memegang atau telah meminta token. The Ricart dan Agrawala algoritma seperti yang kita telah dijelaskan dapat disesuaikan dengan mentolerir kegagalan kecelakaan tersebut proses, dengan mengambil itu untuk memberikan semua permintaan secara implisit. Kami mengundang pembaca untuk mempertimbangkan bagaimana beradaptasi algoritma untuk mentolerir kegagalan, pada asumsi bahwa detektor kegagalan handal tersedia. Bahkan dengan kegagalan terpercaya detektor, perawatan diperlukan untuk memungkinkan kegagalan pada setiap titik (termasuk selama pemulihan Prosedur), dan untuk merekonstruksi keadaan proses setelah kegagalan telah terdeteksi. Misalnya, dalam algoritma pusat-server, jika server gagal itu harus ditetapkan apakah itu atau salah satu proses klien diadakan token. Kami meneliti masalah umum tentang bagaimana proses harus mengkoordinasikan tindakan mereka dengan adanya kesalahan dalam Bagian 15.5.    15.3 Pemilihan Algoritma untuk memilih proses yang unik untuk memainkan peran tertentu disebut pemilihan algoritma. Misalnya, dalam varian algoritma pusat-server kami untuk saling pengecualian, 'server' dipilih dari antara proses pi i = 1 2 N yang perlu menggunakan bagian kritis. Sebuah algoritma pemilihan diperlukan untuk pilihan ini. Ini penting bahwa semua proses setuju pada pilihan. Setelah itu, jika proses yang memainkan peran server ingin pensiun maka pemilihan lain diperlukan untuk memilih penggantian.               Kami mengatakan bahwa proses panggilan pemilu jika dibutuhkan suatu tindakan yang memulairun tertentu dari algoritma pemilu. Proses individu tidak menelepon lebih darisatu pemilu pada satu waktu, tetapi pada prinsipnya proses N bisa menelepon N pemilu bersamaan.Pada setiap titik waktu, proses pi adalah salah satu peserta - yang berarti bahwa itu terlibat dalambeberapa menjalankan algoritma pemilu - atau non-peserta - yang berarti bahwa tidaksaat ini terlibat dalam pemilihan apapun.

Kebutuhan penting adalah untuk pilihan proses terpilih untuk menjadi unik, bahkan

jika beberapa proses memanggil pemilu secara bersamaan. Misalnya, dua proses bisa

memutuskan secara independen bahwa proses koordinator telah gagal, dan kedua menyerukan pemilu.

Tanpa kehilangan umum, kami mengharuskan proses terpilih dipilih sebagai salah satu

dengan identifier terbesar. The 'identifier' mungkin saja nilai yang berguna, asalkan

pengidentifikasi unik dan benar-benar memerintahkan. Sebagai contoh, kita bisa memilih proses dengan

komputasi beban terendah dengan memiliki setiap penggunaan proses <1 beban, i> sebagai identifier-nya,

di mana beban> 0 dan indeks proses i digunakan untuk memesan pengidentifikasi dengan beban yang sama.

Setiap proses pi (i = 1 2 N) memiliki electedi variabel, yang akan berisi

identifier dari proses terpilih. Ketika proses pertama menjadi peserta dalam

Pemilu itu set variabel ini dengan nilai khusus '' untuk menunjukkan bahwa itu belum ditentukan.

persyaratan kami adalah bahwa, selama setiap jangka tertentu algoritma:

E1: (safety)            Seorang peserta proses pi memiliki electedi = atau electedi = P,

dimana P dipilih sebagai proses non-jatuh pada akhir

jalankan dengan identifier terbesar.

E2: (liveness)         Semua proses pi berpartisipasi dan akhirnya baik set

electedi - atau kecelakaan.

Perhatikan bahwa mungkin ada proses pj yang belum peserta, yang merekam di

electedj pengenal dari proses terpilih sebelumnya.

Kami mengukur kinerja algoritma pemilihan oleh jaringan total

pemanfaatan bandwidth (yang sebanding dengan jumlah total pesan yang dikirim), dan

oleh waktu penyelesaian untuk algoritma: jumlah transmisi pesan serial

kali antara inisiasi dan penghentian menjalankan tunggal.



Algoritma pemilu berbasis cincin • Algoritma Chang dan Roberts [1979] adalahcocok untuk koleksi proses diatur seperti sebuah cincin. Setiap pi proses memilikisaluran komunikasi ke proses selanjutnya di ring, pi + 1mod N, dan semua pesandikirim searah jarum jam di sekitar ring. Kami berasumsi bahwa tidak ada kegagalan terjadi, dan bahwa sistemadalah asynchronous. Tujuan dari algoritma ini adalah untuk memilih proses tunggal yang disebutKoordinator, yang merupakan proses dengan identifier terbesar.Awalnya, setiap proses ditandai sebagai non-peserta pemilu. setiap prosesdapat mulai pemilihan. Ini hasil dengan menandai dirinya sebagai peserta, menempatkan identifierdalam pesan pemilu dan mengirimnya ke tetangga searah jarum jam nya.Ketika proses menerima pesan pemilu, membandingkan pengenal dipesan dengan sendiri. Jika identifier tiba lebih besar, maka meneruskan pesan ketetangganya. Jika identifier tiba lebih kecil dan penerima tidak satu peserta, makaia menggantinya identifier sendiri dalam pesan dan meneruskannya; tetapi tidak meneruskanpesan jika sudah peserta. Pada forwarding pesan pemilu dalam hal apapun,proses menandai dirinya sebagai peserta.        Gambar 15.7 Pemilihan berbasis cincin berlangsung                                           Catatan: Pemilihan itu dimulai oleh proses 17. Proses tertinggi identifier ditemuisejauh ini 24. proses Peserta akan ditampilkan dalam warna yang lebih gelap.                  Namun, jika pengenal yang diterima adalah bahwa penerima itu sendiri, maka proses ini identifier harus menjadi yang terbesar, dan itu menjadi koordinator. Tanda koordinatordirinya sebagai non-peserta sekali lagi dan mengirim pesan terpilih untuk tetangganya,mengumumkan pemilihan umum dan melampirkan identitas.Ketika proses pi menerima pesan terpilih, menandai dirinya sebagai nonpartisipan sebuah,set electedi variabel untuk pengenal dalam pesan dan, kecuali itu adalahKoordinator baru, meneruskan pesan ke tetangganya.Sangat mudah untuk melihat bahwa kondisi E1 terpenuhi. Semua pengidentifikasi dibandingkan, karenaProses harus menerima identifier sendiri kembali sebelum mengirim pesan terpilih. untuk setiapdua proses, satu dengan identifier yang lebih besar tidak akan lulus pada pengenal lain. Saya tOleh karena itu tidak mungkin bahwa kedua harus menerima pengenal mereka sendiri kembali.Kondisi E2 mengikuti segera dari traversals dijamin cincin(Tidak ada kegagalan). Perhatikan bagaimana non-peserta dan peserta negara yang digunakan sehinggayang duplikat pesan yang muncul ketika dua proses mulai pemilihan pada waktu yang samadipadamkan sesegera mungkin, dan selalu sebelum 'menang' hasil pemilu memilikitelah diumumkan.Jika hanya satu proses dimulai pemilu, maka kasus berkinerja terburuk adalah ketikatetangga anti-searah jarum jam yang memiliki pengenal tertinggi. Sebanyak N - 1 pesan yangkemudian diperlukan untuk mencapai tetangga ini, yang tidak akan mengumumkan pemilu sampai nyaidentifier telah menyelesaikan sirkuit lain, mengambil lanjut pesan N. yang terpilihpesan tersebut kemudian dikirim N kali, membuat 3N - 1 pesan di semua. Waktu penyelesaian adalahjuga 3N - 1, karena pesan ini dikirim secara berurutan.  Contoh dari pemilu berbasis cincin berlangsung ditunjukkan pada Gambar 15.7. ItuPesan pemilu saat ini berisi 24, namun proses 28 akan mengganti ini dengan identifierketika pesan mencapai itu.Sementara algoritma berbasis cincin berguna untuk memahami sifat-sifatalgoritma pemilihan pada umumnya, fakta bahwa itu tidak mentolerir kegagalan membuatnya dari terbatasnilai praktis. Namun, dengan detektor kegagalan diandalkan itu pada prinsipnya mungkin untuk menyusun kembaliring ketika proses crash.Algoritma bully •               Angka 15,8 Algoritma bully   Pemilihan koordinator p2 , setelah kegagalan p4 dan kemudian p3  p1 p 2 p3 p4p1 p2 p 3 p4Ckoordinatortahap 4Cpemilihanpemilihantahap 2p1 p2 p 3 p4CpemilihanmenjawabmenjawabpemilihanTahap 1waktu habistahap 3Akhirnya.....p1 p2 p 3 p4Pemilihan koordinator p2, setelah kegagalan p4 dan kemudian p3pemilihanmenjawabAlgoritma bully [ Garcia - Molina 1982 ] memungkinkan proses untukkecelakaan selama pemilu , meskipun mengasumsikan bahwa pengiriman pesan antar proseshandal . Berbeda dengan algoritma berbasis cincin , algoritma ini mengasumsikan bahwa sistem inisinkron : menggunakan timeout untuk mendeteksi kegagalan proses . Perbedaan lain adalah bahwaalgoritma berbasis cincin diasumsikan bahwa proses memiliki minimal pengetahuan apriori dari satulain : setiap tahu hanya bagaimana berkomunikasi dengan tetangganya , dan tidak ada yang tahupengidentifikasi proses lainnya . Algoritma bully , di sisi lain , menganggap bahwasetiap proses yang tahu proses memiliki pengenal yang lebih tinggi , dan bahwa hal itu dapatberkomunikasi dengan semua proses tersebut .Ada tiga jenis pesan dalam algoritma ini : pesan pemilu dikirim kemengumumkan pemilihan ; pesan jawaban dikirim dalam menanggapi pesan pemilu danpesan koordinator dikirim untuk mengumumkan identitas proses terpilih - baru



'koordinator'. Proses dimulai pemilihan ketika pemberitahuan, melalui timeout, bahwa

Koordinator telah gagal. Beberapa proses mungkin menemukan ini secara bersamaan.

Karena sistem ini sinkron, kita dapat membangun sebuah detektor kegagalan handal.

Ada pesan transmisi delay maksimum, Ttrans, dan penundaan maksimum untuk

memproses pesan Tprocess. Oleh karena itu, kita dapat menghitung waktu

T = 2Ttrans + Tprocess yang merupakan batas atas pada saat itu dapat berlalu di antara

mengirim pesan ke proses lain dan menerima respon. Jika tidak ada respon tiba

dalam waktu T, maka detektor kegagalan lokal dapat melaporkan bahwa penerima yang dimaksud dari

Permintaan telah gagal.

Proses yang tahu itu telah pengenal tertinggi dapat memilih dirinya sebagai

Koordinator hanya dengan mengirimkan pesan koordinator untuk semua proses dengan rendah

pengidentifikasi. Di sisi lain, proses dengan identifier yang lebih rendah dapat mulai pemilihan oleh

mengirim pesan pemilu untuk proses-proses yang memiliki pengenal yang lebih tinggi dan menunggu

menjawab pesan di respon. Jika tidak tiba dalam waktu T, proses menganggap dirinya

koordinator dan mengirimkan pesan koordinator untuk semua proses dengan pengidentifikasi rendah

mengumumkan ini. Jika tidak, proses menunggu waktu T lebih lanjut untuk koordinator

pesan tiba dari koordinator baru. Jika tidak datang, itu mulai pemilihan lain.

Jika proses pi menerima pesan koordinator, ia menetapkan electedi variabel terhadap

identifier dari koordinator yang ada di dalamnya dan memperlakukan proses itu sebagai koordinator.

Jika proses menerima pesan pemilu, ia akan mengirimkan kembali pesan jawaban dan

dimulai pemilihan lain - kecuali telah dimulai satu sudah.



Ketika suatu proses mulai menggantikan proses jatuh, ia mulai pemilihan. Jika

memiliki proses identifier tertinggi, maka akan memutuskan bahwa itu adalah koordinator dan

mengumumkan ini ke proses lainnya. Oleh karena itu akan menjadi koordinator, meskipun

koordinator saat berfungsi. Hal ini untuk alasan ini bahwa algoritma disebut

'Pengganggu' algoritma.

Operasi algoritma ditunjukkan pada Gambar 15.8. Ada empat proses,

p1 -p4. Proses p1 mendeteksi kegagalan p4 koordinator dan mengumumkan pemilu

(Tahap 1 pada gambar). Pada menerima pesan pemilu dari p1, p2 memproses dan p3

mengirim pesan jawaban p1 dan mulai pemilihan mereka sendiri; p3 mengirimkan jawaban

pesan ke p2, p3 tapi tidak menerima pesan jawaban dari p4 proses gagal (stage

2). Oleh karena itu memutuskan bahwa itu adalah koordinator. Tapi sebelum dapat mengirimkan

Pesan koordinator, juga gagal (tahap 3). Ketika batas waktu p1 's T berakhir (yang

kita asumsikan terjadi sebelum p2 's batas waktu berakhir), itu menyimpulkan tidak adanya koordinator

pesan dan mulai pemilihan lain. Koordinator Akhirnya, p2 terpilih (tahap 4).

Algoritma ini jelas memenuhi kondisi E2 liveness, dengan asumsi

pengiriman pesan dapat diandalkan. Dan jika tidak ada proses diganti, maka algoritma memenuhi

Kondisi E1. Tidak mungkin bagi dua proses untuk memutuskan bahwa mereka adalah koordinator,

karena proses dengan identifier yang lebih rendah akan menemukan bahwa yang lain ada dan tunduk kepada

saya t.

Tetapi algoritma ini tidak dijamin untuk memenuhi kondisi E1 keselamatan jika proses yang telah jatuh digantikan oleh proses dengan pengidentifikasi yang sama. Sebuah proses yang menggantikan proses jatuh p dapat memutuskan bahwa ia memiliki pengenal tertinggi seperti yang lain Proses (yang telah terdeteksi kecelakaan p ini) memutuskan bahwa ia memiliki pengenal tertinggi. Dua proses karena itu akan mengumumkan diri mereka sebagai koordinator bersamaan. Sayangnya, tidak ada jaminan pada delivery order pesan, dan penerima pesan ini bisa mencapai kesimpulan yang berbeda yang merupakan proses koordinator.

Selain itu, kondisi E1 dapat rusak jika nilai-nilai timeout diasumsikan berubah tidak akurat - yaitu, jika detektor kegagalan proses 'tidak dapat diandalkan. Mengambil contoh hanya diberikan, misalkan baik p3 tidak gagal tetapi hanya berjalan biasa lambat (yaitu, bahwa asumsi bahwa sistem ini sinkron adalah salah), atau bahwa p3 telah gagal tapi kemudian diganti. Sama seperti p2 mengirimkan koordinatornya Pesan, p3 (atau penggantinya) melakukan hal yang sama. p2 menerima pesan koordinator p3 's setelah itu telah dikirim sendiri dan menetapkan elected2 = p3. Karena pesan variabel penundaan transmisi, p1 menerima 'pesan koordinator s setelah p3' p2 dan begitu akhirnya menetapkan elected1 = p2. Kondisi E1 telah rusak. Sehubungan dengan kinerja algoritma, dalam kasus terbaik proses dengan tertinggi kedua identifier pemberitahuan kegagalan koordinator. Kemudian segera bisa memilih sendiri dan mengirim N - 2 pesan koordinator. Waktu proses adalah salah satu pesan. Algoritma bully membutuhkan O N2 pesan dalam kasus terburuk - yaitu, ketika proses dengan identifier terendah pertama mendeteksi kegagalan koordinator. Untuk kemudian N – 1 proses sama sekali mulai pemilihan, masing-masing mengirim pesan ke proses dengan tinggi pengidentifikasi.









15.4 Koordinasi dan kesepakatan dalam komunikasi kelompok





Bab ini mengkaji kunci koordinasi dan kesepakatan masalah yang terkait dengan kelompok

komunikasi - yaitu, bagaimana untuk mencapai keandalan yang diinginkan dan memesan properti

di semua anggota kelompok. Bab 6 diperkenalkan komunikasi kelompok sebagai

contoh teknik komunikasi tidak langsung dimana proses dapat mengirim pesan

ke grup. Pesan ini disebarkan ke semua anggota kelompok dengan tertentu

jaminan dalam hal kehandalan dan pemesanan. Kami secara khusus mencari kehandalan dalam

hal sifat validitas, integritas dan kesepakatan, dan pemesanan dalam hal

FIFO pemesanan, pemesanan kausal dan jumlah pemesanan.

Dalam bab ini, kita mempelajari komunikasi multicast kelompok proses yang

keanggotaan dikenal. Bab 18 akan memperluas penelitian kami ke grup sepenuhnya matang

komunikasi, termasuk manajemen kelompok dinamis yang bervariasi.

model sistem • Sistem yang dipertimbangkan berisi kumpulan proses,

yang dapat berkomunikasi andal lebih satu-ke-satu saluran. Seperti sebelumnya, proses mungkin

gagal hanya dengan menerjang.

Proses adalah anggota kelompok, yang merupakan tujuan dari pesan yang dikirim

dengan operasi multicast. Hal ini biasanya berguna untuk memungkinkan proses untuk menjadi anggota

beberapa kelompok secara bersamaan - misalnya, untuk memungkinkan proses untuk menerima informasi

dari beberapa sumber dengan bergabung beberapa kelompok. Tapi untuk menyederhanakan diskusi kami

memesan properti, kita akan kadang-kadang membatasi proses untuk menjadi anggota paling

satu kelompok pada suatu waktu.

Operasi multicast (g, m) mengirimkan pesan m kepada seluruh anggota kelompok g

proses. Sejalan dengan itu, ada operasi memberikan (m) yang memberikan pesan

dikirim oleh multicast untuk proses pemanggilan. Kami menggunakan istilah memberikan daripada menerima untuk

membuat jelas bahwa pesan multicast tidak selalu diserahkan ke lapisan aplikasi dalam



proses segera setelah diterima di node proses ini. Ini dijelaskan ketika kita



mendiskusikan semantik pengiriman multicast lama.

Setiap pesan m mengusung identifier unik pengirim proses (m) yang dikirim

itu, dan kelompok pengenal kelompok tujuan wisata yang unik (m). Kami berasumsi bahwa proses dilakukan

tidak berbohong tentang asal atau tujuan dari pesan.

Beberapa algoritma menganggap bahwa kelompok ditutup (sebagaimana didefinisikan dalam Bab 6).





15.4.1 multicast Dasar



Hal ini berguna untuk memiliki di pembuangan kami multicast dasar primitif yang jaminan, tidak seperti IP

multicast, bahwa proses yang benar akhirnya akan menyampaikan pesan, asalkan

multicaster tidak crash. Kita sebut primitif B-multicast dan yang sesuai dasar

pengiriman primitif B-memberikan. Kami mengizinkan proses milik beberapa kelompok, dan masing-masing

Pesan ditakdirkan untuk beberapa kelompok tertentu.

Sebuah cara mudah untuk menerapkan B-multicast adalah dengan menggunakan satu satu-ke-terpercaya

kirim operasi, sebagai berikut:

Untuk B-multicast (g, m): untuk setiap proses p g, kirim (p, m);

Pada menerima (m) di p: B-memberikan (m) pada p.

pelaksanaannya dapat menggunakan benang untuk melakukan operasi kirim bersamaan, dalam

berusaha untuk mengurangi total waktu yang dibutuhkan untuk menyampaikan pesan. Sayangnya, seperti

implementasi bertanggung jawab untuk menderita apa yang disebut ack-ledakan jika jumlah

proses besar. Ucapan terima kasih yang dikirim sebagai bagian dari send operasi yang handal yang

jawab tiba dari banyak proses pada waktu yang sama. Proses multicasting ini

buffer cepat aka

n mengisi, dan itu adalah tanggung jawab untuk menjatuhkan pengakuan. Ini karena itu akan

memancarkan kembali pesan, yang mengarah ke lebih banyak lagi pengakuan dan limbah lebih lanjut

bandwidth jaringan. Sebuah layanan multicast dasar lebih praktis dapat dibangun dengan menggunakan IP

multicast, dan kami mengundang pembaca untuk menunjukkan ini dalam Latihan 15.10.



15.4.2 Multicast Handal Bab 6 membahas multicast handal dalam hal validitas, integritas dan kesepakatan. IniBagian didasarkan pada sarasehan ini, menyajikan definisi yang lebih lengkap.Berikut Hadzilacos dan Toueg [1994] dan Chandra dan Toueg [1996], kamimenentukan multicast terpercaya dengan sesuai operasi R-multicast dan R-memberikan.Sifat analog dengan integritas dan validitas yang jelas sangat diinginkan di terpercayapengiriman multicast, tapi kami tambahkan lagi: persyaratan bahwa semua proses yang benar dalamkelompok harus menerima pesan jika salah satu dari mereka tidak. Adalah penting untuk menyadari bahwa ini adalahbukan milik algoritma B-multicast yang didasarkan pada handal satu-ke-satu sendoperasi. pengirim mungkin gagal pada setiap titik sementara hasil B-multicast, sehingga beberapaproses dapat menyampaikan pesan sementara yang lainnya tidak.Sebuah multicast handal adalah salah satu yang memenuhi sifat-sifat berikut:Integritas: Sebuah proses p benar memberikan pesan m paling banyak sekali. Selanjutnya,p groupm dan m disediakan untuk operasi multicast oleh pengirim (m). (Sepertisatu-ke-satu komunikasi, pesan dapat selalu dibedakan dengan urutanjumlah relatif ke pengirim mereka.) Validitas: Jika proses yang benar multicast pesan m, maka pada akhirnya akan memberikan m.Perjanjian: Jika proses benar memberikan pesan m, maka semua proses yang benar lainnyadalam kelompok (m) akhirnya akan memberikan m.Properti integritas adalah analog dengan komunikasi satu-ke-satu yang handal. ItuProperti validitas menjamin liveness untuk pengirim. Hal ini mungkin tampak properti yang tidak biasa,karena asimetris (menyebutkan hanya satu proses tertentu). Tetapi perhatikan bahwavaliditas dan kesepakatan bersama berjumlah persyaratan liveness keseluruhan: jika satuproses (pengirim) akhirnya memberikan pesan m, karena proses yang benar setujupada set pesan yang mereka kirimkan, berikut bahwa m akhirnya akan dikirimkan ke semuaanggota yang benar kelompok. Gambar 15.9 Algoritma multicast Handal pada inisialisasiMenerima: = {};Untuk proses p pesan R-multicast m ke grup gB-multicast (g, m); // Disertakan sebagai tujuanPada B-memberikan (m) pada proses q dengan g = group (m)jika ()kemudianDiterima: =;jika () maka B-multicast (g, m); berakhir jikaR-memberikan m;berakhir jikap gm DiterimaMenerima mq pKeuntungan mengungkapkan kondisi validitas dalam hal self-pengirimankesederhanaan. Apa yang kita butuhkan adalah bahwa pesan disampaikan pada akhirnya oleh beberapa yang benaranggota kelompok.Kondisi kesepakatan terkait dengan atomicity, milik 'semua atau tidak',diterapkan untuk pengiriman pesan ke grup. Jika proses yang multicast pesan crashsebelum itu telah disampaikan, maka ada kemungkinan bahwa pesan tidak akan dikirimkan ke setiapProses dalam kelompok; tetapi jika disampaikan beberapa proses yang benar, maka semua lain yang benarproses akan menyampaikan hal itu. Banyak makalah dalam literatur menggunakan istilah 'atom' untuk memasukkankondisi memesan Total; kita mendefinisikan ini tak lama.Menerapkan multicast handal lebih dari B-multicast • Gambar 15.9 memberikan multicast terpercayaalgoritma, dengan primitif R-multicast dan R-memberikan, yang memungkinkan proses milikbeberapa ditutup kelompok secara bersamaan. Untuk R-multicast pesan, proses Bmulticastspesan untuk proses dalam kelompok tujuan (termasuk dirinya sendiri). Kapanpesan adalah B-disampaikan, penerima pada gilirannya B-multicast pesan ke grup(Jika tidak pengirim asli), dan kemudian R-memberikan pesan. Sejak pesan mungkintiba lebih dari sekali, duplikat dari pesan yang terdeteksi dan tidak disampaikan.Algoritma ini jelas memenuhi properti validitas, karena proses yang benar akanakhirnya B-menyampaikan pesan untuk dirinya sendiri. Dengan properti integritas yang mendasarisaluran komunikasi yang digunakan dalam B-multicast, algoritma juga memenuhi integritasPerjanjian mengikuti dari fakta bahwa setiap proses yang benar B-multicast yangpesan ke proses lainnya setelah itu telah B-disampaikan. Jika proses yang benar tidak Rdeliverpesan, maka ini hanya bisa karena tidak pernah B-disampaikan. Yang pada gilirannyahanya bisa karena tidak ada proses yang benar lain B-disampaikan itu baik; Oleh karena itu tidak ada akanR-mengirimkannya.Algoritma multicast handal yang kita telah dijelaskan benar dalamsistem asynchronous, karena kita tidak membuat waktu asumsi. Tetapi algoritma ini adalahtidak efisien untuk tujuan praktis. Setiap pesan yang dikirim g kali untuk setiap proses.multicast terpercaya over IP multicast • Sebuah realisasi alternatif R-multicast adalah dengan menggunakankombinasi IP multicast, piggybacked pengakuan (yaitu, pengakuanmelekat pesan lain) dan pengakuan negatif. Ini R-multicastprotokol ini didasarkan pada pengamatan bahwa IP komunikasi multicast sering berhasil.Dalam protokol, proses tidak mengirim pesan pengakuan yang terpisah; sebagai gantinya,mereka dukung-dukungan pengakuan dari pesan yang mereka kirim ke grup. prosesmengirim pesan respon yang terpisah hanya ketika mereka mendeteksi bahwa mereka telah melewatkanpesan. Sebuah respon menunjukkan tidak adanya pesan yang diharapkan dikenal sebagai negatifpengakuan.Deskripsi berasumsi bahwa kelompok ditutup. Setiap proses p mempertahankannomor urut Sgp untuk setiap kelompok g mana ia berasal. Nomor urut adalahawalnya nol. Setiap proses juga mencatat Rgq, nomor urut dari pesan terbaruitu telah disampaikan dari proses q yang dikirim ke grup g.Untuk p ke R-multicast pesan ke grup g, itu piggybacks ke pesan yangnilai Sgp dan pengakuan, dari bentuk <q, Rgq>. Sebuah negara pengakuan, untukbeberapa pengirim q, nomor urut dari pesan terbaru dari q ditakdirkan untuk p g yangtelah disampaikan sejak multicast lalu pesan. The multicaster p maka IP-multicast yangpesan dengan nilai piggybacked untuk g, dan kenaikan Sgp per satu.Nilai-nilai piggybacked dalam pesan multicast memungkinkan penerima untuk belajar tentang pesan bahwa mereka belum menerima . Sebuah proses R - memberikan pesan yang ditujukan untukg bantalan nomor urut S dari p jika dan hanya jika S Rg= P + 1 , dan incrementrgp oleh salah satu segera setelah melahirkan . Jika pesan tiba memiliki S Rgp , maka r memilikimenyampaikan pesan sebelum dan membuang itu . Jika S Rgp + 1 , atau jika R Rgq untukpengakuan tertutup < q , R > , maka ada satu atau lebih pesan yang belumbelum menerima ( dan yang mungkin telah dijatuhkan , dalam kasus pertama ) . Ini membuat setiapPesan yang S Rgp + 1 dalam antrian hold - kembali ( Gambar 15.10 ) - antrian sepertisering digunakan untuk memenuhi jaminan pengiriman pesan . Ini meminta pesan hilang olehmengirimkan ucapan terima kasih negatif , baik untuk pengirim asli atau ke q proses dariyang telah menerima pengakuan < q , Rgq > dengan Rgq tidak kurang dari yang dibutuhkanurutan nomor .



Antrian hold-kembali tidak benar-benar diperlukan untuk keandalan, tetapi menyederhanakan

protokol dengan memungkinkan kita untuk menggunakan nomor urut untuk mewakili set disampaikan

pesan. Hal ini juga memberikan kita jaminan delivery order (lihat Bagian 15.4.3).

Properti integritas mengikuti dari deteksi duplikat dan mendasari

sifat IP multicast (yang menggunakan checksum untuk menghapus pesan rusak). Itu

Properti validitas memegang karena IP multicast memiliki properti itu. Untuk kesepakatan kami

membutuhkan, pertama, bahwa proses selalu dapat mendeteksi pesan hilang. Yang pada gilirannya berarti bahwa

itu akan selalu menerima pesan lebih lanjut yang memungkinkan untuk mendeteksi kelalaian. karena ini





Gambar 15.10 The hold-kembali antrian untuk tiba pesan multicast













Pesanpengolahan antrian pengiriman Rintangan antre menyampaikan masuk pesan ketika pengiriman jaminan tersebutbertemu protokol sederhana berdiri, kami menjamin deteksi pesan hilang hanya dalam kasus ini di mana proses yang benar pesan multicast tanpa batas. Kedua, perjanjian Properti mengharuskan selalu ada salinan yang tersedia dari setiap pesan yang dibutuhkan oleh proses yang tidak menerimanya. Oleh karena itu kami berasumsi bahwa proses menyimpan salinan dari pesan mereka telah disampaikan - tanpa batas, dalam protokol yang disederhanakan ini. Tak satu pun dari asumsi yang kami buat untuk memastikan kesepakatan praktis (lihat Latihan

15.15). Namun, kesepakatan praktis dibahas dalam protokol yang kita adalah

berasal: protokol Psync [Peterson et al. 1989], Trans protokol [Melliar-Smith et al.

1990] dan scalable handal protokol multicast [Floyd et al. 1997]. Psync dan Trans juga

memberikan jaminan pengiriman pemesanan lebih lanjut sifat seragam • Definisi perjanjian yang diberikan di atas hanya merujuk pada

perilaku proses yang benar - proses yang tidak pernah gagal. Pertimbangkan apa yang akan terjadidalam algoritma dari Gambar 15.9 jika suatu proses yang tidak benar dan jatuh setelah itu Rdeliveredsebuah pesan. Karena setiap proses yang R-memberikan pesan harus pertama Bmulticastitu, maka semua proses yang benar akan tetap akhirnya menyampaikan pesan.Setiap properti yang memegang atau tidaknya proses yang benar disebut seragammilik. Kami mendefinisikan perjanjian seragam sebagai berikut:Perjanjian seragam: Jika proses, apakah itu benar atau gagal, memberikan pesan m,maka semua proses yang benar dalam kelompok (m) akhirnya akan memberikan m.Perjanjian seragam memungkinkan proses untuk kecelakaan setelah itu telah menyampaikan pesan, sementara masihmemastikan bahwa semua proses yang benar akan menyampaikan pesan. Kami berpendapat bahwaalgoritma Gambar 15.9 memenuhi properti ini, yang lebih kuat dari non-seragamProperti perjanjian didefinisikan di atas.Perjanjian seragam berguna dalam aplikasi dimana proses dapat mengambil tindakanyang menghasilkan inkonsistensi diamati sebelum crash. Misalnya, yangproses adalah server yang mengelola salinan rekening bank, dan yang update keakun dikirim menggunakan multicast dapat diandalkan untuk kelompok server. Jika multicast yang tidakmemenuhi perjanjian seragam, maka klien yang mengakses server sebelum crash mungkinmengamati update yang ada server lain akan memproses.BAGIAN 15,4 KOORDINASI DAN PERJANJIAN DI GROUP KOMUNIKASI 651Sangat menarik untuk dicatat bahwa jika kita membalikkan garis 'R-memberikan m' dan 'jika (q p)maka B-multicast (g, m); berakhir jika 'pada Gambar 15.9, maka algoritma yang dihasilkan tidakmemenuhi perjanjian seragam.Sama seperti ada versi seragam perjanjian, ada juga versi seragamsetiap properti multicast, termasuk validitas dan integritas dan sifat pemesanan yangkita akan menentukan.15.4.3 Memerintahkan multicastAlgoritma multicast dasar Bagian 15.4.1 memberikan pesan ke proses dalamAgar sewenang-wenang, karena penundaan sewenang-wenang dalam satu-ke-satu operasi mengirim mendasari.Kurangnya jaminan pemesanan tidak memuaskan untuk banyak aplikasi. UntukMisalnya, di pembangkit listrik tenaga nuklir itu mungkin penting bahwa peristiwa menandakan ancaman terhadapkondisi keamanan dan acara menandakan tindakan oleh unit kontrol yang diamati dalam yang samamemesan dengan semua proses dalam sistem.Sebagaimana dibahas dalam Bab 6, persyaratan pemesanan umum adalah jumlah pemesanan,pemesanan kausal dan FIFO pemesanan, bersama-sama dengan solusi hybrid (khususnya, totalcausaldan jumlah-FIFO). Untuk menyederhanakan diskusi kita, kita mendefinisikan orderings ini di bawahasumsi bahwa setiap proses milik paling banyak satu kelompok (kemudian kami mendiskusikanimplikasi yang memungkinkan kelompok tumpang tindih):FIFO memesan: Jika masalah proses yang benar multicast (g, m) dan kemudian multicast (g, m),maka setiap proses yang benar yang memberikan m akan memberikan m sebelum m.Kausal pemesanan: Jika multicast (g, m) multicast (g, m), di mana adalahterjadi-sebelum hubungan diinduksi hanya dengan pesan yang dikirim antara anggota g,maka setiap proses yang benar yang memberikan m akan memberikan m sebelum m.Jumlah pemesanan: Jika proses benar memberikan pesan m sebelum memberikan m, makasetiap proses yang benar lainnya yang memberikan m akan memberikan m sebelum m.pemesanan kausal menyiratkan FIFO pemesanan, karena setiap dua multicasts oleh proses yang samaterkait dengan terjadi-sebelumnya. Perhatikan bahwa FIFO pemesanan dan kausal pemesanan hanyaorderings parsial: tidak semua pesan yang dikirim oleh proses yang sama, secara umum; demikian pula,beberapa multicast yang bersamaan (tidak diperintahkan oleh terjadi-sebelum).Gambar 15.11 menggambarkan orderings untuk kasus tiga proses. Dekatpemeriksaan angka menunjukkan bahwa pesan benar-benar memerintahkan disampaikan dalamAgar berlawanan dengan waktu fisik di mana mereka dikirim. Bahkan, definisi totalpemesanan memungkinkan pengiriman pesan ke dipesan sewenang-wenang, asalkan pesanan adalahsama pada proses yang berbeda. Sejak Total pemesanan belum tentu juga FIFO atau kausalmemesan, kita mendefinisikan hibrida FIFO-jumlah pemesanan sebagai salah satu yang pengiriman pesanmematuhi baik FIFO dan jumlah pemesanan; sama, di bawah kausal-Total pesan memesanpengiriman mematuhi baik kausal dan jumlah pemesanan.Definisi multicast memerintahkan jangan menganggap atau menyiratkan keandalan. UntukMisalnya, pembaca harus memeriksa bahwa, bawah total pemesanan, jika proses yang benar p memberikanpesan m dan kemudian memberikan m, maka proses q benar dapat memberikan m tanpa jugamemberikan m atau pesan lain memerintahkan setelah m.Kami juga dapat membentuk hibrida protokol memerintahkan dan dapat diandalkan. A terpercaya benar-benarmemerintahkan multicast sering disebut dalam literatur sebagai multicast atom. Demikian pula                  Gambar 15.11 Total, FIFO dan pemesanan kausal pesan multicast     Perhatikan urutan konsisten benar-benar memerintahkan pesan T1 dan T2, pesan terkait FIFO-F1 dan F2 dan kausal terkait pesan C1 dan C3 - dan pengiriman dinyatakan sewenang-wenangpemesanan pesan   kita dapat membentuk multicast FIFO terpercaya, dapat diandalkan kausal multicast dan versi diandalkanhibrida memerintahkan multicast.Memerintahkan pengiriman pesan multicast, seperti yang akan kita lihat, bisa mahal dihal pengiriman latency dan konsumsi bandwidth. Pemesanan semantik yang kitatelah dijelaskan dapat menunda pengiriman pesan yang tidak perlu. Artinya, ditingkat aplikasi, pesan mungkin tertunda untuk pesan lain yang tidak sebenarnyatergantung. Untuk alasan ini, beberapa telah mengusulkan sistem multicast yang menggunakansemantik pesan khusus aplikasi sendiri untuk menentukan urutan pesanpengiriman [Cheriton dan Skeen 1993, Pedone dan Schiper 1999].Contoh dari papan buletin • Untuk membuat semantik pengiriman multicast lebihbeton, pertimbangkan sebuah aplikasi di mana pengguna mengirim pesan ke papan buletin. Setiappengguna menjalankan proses aplikasi bulletin-board. Setiap topik diskusi memiliki sendirikelompok proses. Ketika pengguna posting pesan ke papan buletin, aplikasi multicast postingan pengguna untuk kelompok yang sesuai. Proses setiap pengguna adalahanggota kelompok untuk topik yang pengguna tertarik, sehingga mereka akan menerimahanya posting tentang topik itu.multicast handal diperlukan jika setiap pengguna untuk menerima setiap postingan akhirnya.Para pengguna juga memiliki memesan persyaratan. Gambar 15.12 Tampilan dari program papan buletin papan buletin: os.interestingItem        Dari                       Subjek23           A.Hanlon              Mach24           G.Joseph               Microkernels25           A.Hanlon               Re: Microkernels26           T.L'Heureux          RPC Kinerja27           M.Walker               Re: MachakhirGambar 15.12 menunjukkan posting karena merekamuncul untuk pengguna tertentu. Minimal, FIFO memesan diinginkan, sejak itu setiappostingan dari pengguna tertentu - 'A.Hanlon', mengatakan - akan diterima dalam urutan yang sama, danpengguna dapat berbicara secara konsisten tentang posting kedua A.Hanlon ini.Perhatikan bahwa pesan-pesan yang subyek 'Re: Microkernels' (25) dan 'Re:Mach '(27) muncul setelah pesan yang mereka lihat. Sebuah multicast kausal memerintahkandiperlukan untuk menjamin hubungan ini. Jika tidak, penundaan pesan sewenang-wenang bisa berartiyang, katakanlah, pesan 'Re: Mach' bisa muncul sebelum pesan asli tentang Mach.Jika pengiriman multicast benar-benar memerintahkan, maka penomoran di kiri yangKolom akan konsisten antara pengguna. Pengguna bisa merujuk jelas, untukMisalnya, untuk 'pesan 24'.Dalam prakteknya, sistem papan buletin USENET mengimplementasikan tidak kausal atauTotal pemesanan. Biaya komunikasi untuk mencapai penataan ini pada skala besarlebih besar daripada keuntungan mereka.Menerapkan FIFO memesan • FIFO-memerintahkan multicast (dengan operasi FO-multicastdan FO-memberikan) dicapai dengan nomor urut, seperti yang kita akan mencapainya untuksatu-ke-satu komunikasi. Kami akan mempertimbangkan hanya kelompok-kelompok non-tumpang tindih. Pembacaharus memverifikasi bahwa protokol multicast handal yang kita definisikan di atas IP multicastdalam Bagian 15.4.2 juga menjamin FIFO memesan, tapi kami akan menunjukkan bagaimana untuk membangunFIFO-memerintahkan multicast di atas setiap multicast dasar yang diberikan. Kami menggunakan variabel Sgpdan Rgq diadakan di proses p dari protokol multicast handal dari Bagian 15.4.2: Sgp adalahhitungan berapa banyak pesan p telah dikirim ke g dan, untuk setiap q, Rgq adalah nomor urutpesan p terbaru telah dikirim dari proses q yang dikirim ke grup g.Untuk p ke FO-multicast pesan ke grup g, itu piggybacks nilai Sgp kepesan, B-multicast pesan untuk g dan kemudian menambahkan Sgp oleh 1. Setelah menerimapesan dari q bantalan nomor urutan S, p cek apakah S Rg= Q + 1. Jika demikian,pesan ini adalah yang berikutnya diharapkan dari q pengirim dan p FO-memberikan itu, pengaturanrgq : = S. Jika S Rg q + 1, ia menempatkan pesan dalam antrian terus-kembali sampai mengintervensipesan telah disampaikan dan S Rgq = + 1.Karena semua pesan dari pengirim yang diberikan disampaikan dalam urutan yang sama, dankarena pengiriman pesan tertunda sampai nomor urut yang telah dicapai,Kondisi untuk FIFO memesan jelas puas. Tapi ini sehingga hanya berdasarkan asumsibahwa kelompok-kelompok yang tidak tumpang tindih.Perhatikan bahwa kita dapat menggunakan implementasi salah B-multicast di protokol ini.Apalagi jika kita menggunakan terpercaya R-multicast primitif bukan B-multicast, maka kitamemperoleh multicast FIFO handal.Menerapkan Total pemesanan • Pendekatan dasar untuk menerapkan jumlah pemesanan adalah untukmenetapkan pengenal benar-benar diperintahkan untuk pesan multicast sehingga setiap proses membuatKeputusan memesan sama berdasarkan pengidentifikasi ini. Algoritma pengiriman sangatmirip dengan yang kita dijelaskan untuk FIFO pemesanan; perbedaannya adalah bahwa proses terusKelompok-spesifik nomor urut bukan proses yang spesifik nomor urut. Kamihanya mempertimbangkan bagaimana untuk benar-benar memesan pesan yang dikirim ke kelompok-kelompok non-tumpang tindih. Kita sebutoperasi multicast TO-multicast dan TO-memberikan.Kami membahas dua metode utama untuk menetapkan pengidentifikasi pesan. Yang pertama dariini adalah untuk proses yang disebut sequencer untuk menetapkan mereka (Gambar 15,13). Sebuah prosesingin TO-multicast pesan m ke grup g menempel pengenal id unik (m) untuk itu.Pesan untuk g dikirim ke sequencer untuk g, sequencer (g), serta untukanggota g. (Sequencer dapat dipilih untuk menjadi anggota g.) Prosessequencer (g) mempertahankan nomor urut sg kelompok tertentu, yang digunakan untuk menetapkanmeningkat dan nomor urut berturut-turut untuk pesan bahwa B-memberikan.Ini mengumumkan urutan angka dengan pesan agar B-multicasting untuk g (lihat Gambar15,13 untuk rincian).Sebuah pesan akan tetap berada di antrian terus-kembali tanpa batas waktu sampai dapat TOdeliveredmenurut nomor urut sesuai. Karena nomor urutdidefinisikan dengan baik (dengan sequencer), kriteria total pemesanan terpenuhi. Selanjutnya,jika proses menggunakan varian FIFO-memerintahkan B-multicast, maka benar-benar memerintahkanmulticast juga kausal memerintahkan. Kami meninggalkan pembaca untuk menunjukkan ini.Masalah yang jelas dengan skema berbasis sequencer adalah bahwa sequencer mungkinmenjadi hambatan dan merupakan titik kritis dari kegagalan. algoritma praktis ada yangmengatasi masalah kegagalan. Chang dan Maxemchuk [1984] pertama menyarankanprotokol multicast menggunakan sequencer (yang mereka sebut situs token). Kaashoek etAl. [1989] mengembangkan protokol berbasis sequencer untuk sistem Amoeba. Iniprotokol memastikan bahwa pesan dalam antrian terus-kembali di f + 1 node sebelum itudisampaikan; sampai dengan kegagalan f sehingga dapat ditoleransi. Seperti Chang dan Maxemchuk, Birman etAl. [1991] juga mempekerjakan situs tanda-holding yang bertindak sebagai sequencer. token dapatlulus dari proses ke proses sehingga, misalnya, jika hanya satu proses mengirimkan benar-benarmulticasts memerintahkan proses yang dapat bertindak sebagai sequencer, menghemat komunikasi.Protokol dari Kaashoek et al. menggunakan multicast berbasis hardware - tersedia padaEthernet, misalnya - bukan diandalkan komunikasi point-to-point. DalamVarian yang paling sederhana dari protokol mereka, proses mengirim pesan yang akan multicast kesequencer, satu-ke-satu. sequencer multicast pesan itu sendiri, sertaidentifier dan nomor urut. Ini memiliki keuntungan bahwa anggota lain dari Gambar 15.13 Jumlah pemesanan menggunakan sequencer 1. Algoritma untuk anggota kelompok pPada inisialisasi:: = 0;Untuk TO-multicast pesan m ke grup gB-multicast (, <m, i>);Pada B-memberikan (<m, i>) dengan g = group (m)Tempat <m, i> dalam antrian hold-kembali;Pada B-memberikan (= < "order", i, S>) dengan g = group ()tunggu sampai <m, i> dalam antrian terus-kembali dan;TO-memberikan m; // (Setelah menghapusnya dari antrian hold-back): =;2. Algoritma untuk sequencer dari gPada inisialisasi:: = 0;Pada B-memberikan (<m, i>) dengan g = group (m)B-multicast (g, < "order", i,>);: =;rgg sequencergmorder morderS = rgrg S + 1sgsgsg sg + 1  kelompok hanya menerima satu pesan per multicast; merugikan adalah peningkatan bandwidthpemanfaatan. Protokol ini dijelaskan dalam penuh di www.cdk5.net/coordination.Metode kedua yang kita periksa untuk mencapai benar-benar memerintahkan multicast adalah salah satudi mana proses kolektif menyetujui penugasan nomor urut untukpesan secara terdistribusi. Sebuah algoritma sederhana - mirip dengan salah satu yang awalnyadikembangkan untuk melaksanakan pengiriman multicast benar-benar memerintahkan untuk toolkit ISIS [Birmandan Joseph 1987a] - ditunjukkan pada Gambar 15.14. Sekali lagi, proses B-multicast nyapesan kepada anggota kelompok. Kelompok ini mungkin terbuka atau tertutup. penerima yangproses mengusulkan nomor urut untuk pesan saat mereka tiba dan kembali ini kepengirim, yang menggunakan mereka untuk menghasilkan angka urut setuju.Setiap q proses dalam kelompok g terus Agq, terbesar nomor urut setuju itu memilikidiamati sejauh untuk kelompok g, dan Pgq, terbesar nomor urut diusulkan sendiri. Itualgoritma untuk proses p multicast pesan m ke grup g adalah sebagai berikut:1. p B-multicast <m, i> untuk g, di mana saya adalah pengenal unik untuk m.2. Setiap balasan proses q ke pengirim p dengan proposal untuk pesan '_____ s setujunomor urut Pgq: = Max (Agq, Pgq) + 1. Pada kenyataannya, kita harus menyertakan prosespengidentifikasi dalam nilai-nilai yang diusulkan Pgq untuk memastikan order total, karena jika tidakproses yang berbeda bisa mengusulkan nilai integer yang sama; tapi demikesederhanaan kita tidak akan membuat eksplisit di sini. Setiap ditunjuk proses sementaranomor urut yang diusulkan untuk pesan dan tempat-tempat dalam antrian terus-punggungnya,yang memerintahkan dengan nomor urut terkecil di depan.  Gambar 15.14 Algoritma ISIS total pemesanan       3. p mengumpulkan semua nomor urut yang diusulkan dan memilih salah satu yang terbesar, yang, sebagaiselanjutnya setuju nomor urut. Kemudian B-multicast <i, a> untuk g. Setiap proses q dig set Agq: = Max (Agq, a) dan menempel ke pesan (yang diidentifikasi oleh i).Ini menata ulang pesan dalam antrian terus-kembali jika nomor urut yang telah disepakatiberbeda dari yang diusulkan. Ketika pesan di depan terus-kembaliantrian telah ditetapkan nomor urut disepakati, ia dipindahkan ke ekorantrian pengiriman. Pesan yang telah ditetapkan urutan yang disepakatiNomor tetapi tidak di kepala antrian terus-kembali belum ditransfer,namun.Jika setiap proses setuju set yang sama nomor urut dan memberikan mereka dalamUrutan yang sesuai, maka jumlah pemesanan puas. Jelas bahwa proses yang benarakhirnya setuju pada set yang sama nomor urut, tapi kami harus menunjukkan bahwa merekamonoton meningkat dan bahwa tidak ada proses yang benar dapat menyampaikan pesan prematur.Asumsikan bahwa m1 pesan telah ditetapkan nomor urut disepakati dan memilikisampai di depan antrian terus-kembali. Dengan konstruksi, pesan yang diterimasetelah tahap ini akan dan harus disampaikan setelah m1: itu akan memiliki mengusulkan lebih besarnomor urut dan dengan demikian lebih besar sepakat nomor urut dari m1. Jadi mari m2 berupaPesan lain yang belum diberikan nomor urut disepakati tetapi yang ada diantrian yang sama. Kami memiliki:agreedSequence (m2) proposedSequence (m2)oleh algoritma hanya diberikan. Sejak m1 adalah di depan antrian:proposedSequence (m2)> agreedSequence (m1)Karena itu:agreedSequence (m2)> agreedSequence (m1)dan jumlah pemesanan terjamin.Algoritma ini memiliki latency lebih tinggi daripada algoritma multicast berbasis sequencer:tiga pesan yang dikirim secara serial antara pengirim dan grup sebelum pesan dapatdisampaikan.Perhatikan bahwa urutan keseluruhan dipilih oleh algoritma ini tidak juga dijamin akankausal atau FIFO-memerintahkan: dua pesan yang disampaikan dalam dasarnya sewenang-wenangtotal order, dipengaruhi oleh keterlambatan komunikasi.Untuk pendekatan lain untuk menerapkan jumlah pemesanan, lihat Melliar-Smith et al.[1990], Garcia-Molina dan Spauster [1991] dan Hadzilacos dan Toueg [1994].Menerapkan kausal memesan • Selanjutnya kita memberikan algoritma untuk non-tumpang tindih ditutupkelompok berdasarkan yang dikembangkan oleh Birman et al. [1991], ditampilkan di Gambar 15.15 memesan kausal menggunakan cap waktu vektorAlgoritma untuk anggota kelompok ()pada inisialisasi: = 0 ();pesan ke CO-multicast m ke grup g: =;B-multicast (g, <, m>);Pada B-memberikan (<, m>) dari (), dengan g = group (m)Tempat <, m> dalam antrian hold-kembali;menunggu sampai dan ();CO-memberikan m; // Setelah mengeluarkannya dari antrian terus-kembali: =;pi i = 1 2 NVig j j = 1 2 NVig i Vig i + 1VigVjg pj j iVjgVjg j Vig = j + 1 Vjg k Vig k k jVig j Vig j + 1Gambar 15.15, di manaoperasi multicast kausal yang dipesan CO-multicast dan CO-memberikan. Itualgoritma memperhitungkan terjadi-sebelum hubungan hanya seperti yang ditetapkan olehpesan multicast. Jika proses mengirim pesan satu-ke-satu satu sama lain, makaini tidak akan diperhitungkan.Setiap pi proses (i = 1 2 N) mempertahankan timestamp vektor sendiri (lihatBagian 14.4). Entri dalam timestamp menghitung jumlah pesan multicastdari setiap proses yang terjadi-sebelum pesan berikutnya yang akan multicast.Untuk CO-multicast pesan ke grup g, proses menambahkan 1 untuk masuk dalamtimestamp dan B-multicast pesan bersama dengan timestamp untuk g.Ketika proses pi B-memberikan pesan dari pj, itu harus menempatkannya di hold-kembaliantrian sebelum dapat CO-menyampaikannya - yaitu, sampai ia yakin bahwa itu telah disampaikan setiappesan yang kausal mendahuluinya. Untuk membangun ini, pi menunggu sampai (a) itu telah disampaikanpesan sebelumnya yang dikirim oleh pj, dan (b) itu telah disampaikan pesan bahwa PJ memilikidisampaikan pada saat itu multicast pesan. Kedua kondisi tersebut dapat dideteksidengan memeriksa cap waktu vektor, seperti yang ditunjukkan pada Gambar 15.15. Perhatikan bahwa proses dapatsegera CO-menyerahkan kepada dirinya sendiri setiap pesan yang CO-multicast, meskipun hal ini tidakdijelaskan pada Gambar 15.15.Setiap proses update timestamp vektor pada menyampaikan pesan apapun, untukmempertahankan hitungan pesan kausal preseden. Hal ini dilakukan dengan incrementing j yangmasuk dalam timestamp oleh satu. Ini adalah optimalisasi operasi gabungan yang munculdalam aturan untuk memperbarui jam vektor dalam Bagian 14.4. Kita bisa membuat optimasi diMengingat kondisi pengiriman algoritma Gambar 15.15, yang menjamin bahwahanya entri j akan meningkat.Kami menguraikan bukti kebenaran algoritma ini sebagai berikut. Seandainyamulticast (g, m) multicast (g, m). Mari V dan V menjadi cap vektor m danm, masing-masing. Hal ini mudah untuk membuktikan secara induktif dari algoritma yangV V. Secara khusus, jika proses pk multicast m, maka Vk Vk.Pertimbangkan apa yang terjadi ketika beberapa proses yang benar pi B-memberikan m (sebagai lawanuntuk CO-menyampaikannya) tanpa terlebih dahulu CO-memberikan m. Dengan algoritma, Vik dapat meningkatkanhanya ketika pi memberikan pesan dari pk, ketika meningkat dengan 1. Tapi pi belummenerima m, dan karena itu Vik tidak dapat meningkat melebihi Vk - 1. Oleh karena itu tidakmungkin bagi pi untuk CO-memberikan m, karena ini akan mengharuskan Vik Vk, danOleh karena itu Vik Vk.pembaca harus memeriksa bahwa jika kita mengganti primitif R-multicast terpercaya ditempat B-multicast, maka kita mendapatkan multicast yang handal dan kausalmemerintahkan.Selain itu, jika kita menggabungkan protokol untuk kausal multicast dengan sequencerbased yangprotokol untuk pengiriman benar-benar memerintahkan, maka kita mendapatkan pengiriman pesan yang baiktotal dan kausal. sequencer memberikan pesan sesuai dengan urutan kausal danmulticast nomor urut untuk pesan dalam urutan yang menerima mereka.Proses dalam kelompok tujuan tidak menyampaikan pesan sampai mereka telah menerimapesan perintah dari sequencer dan pesan yang berikutnya dalam urutan pengiriman.Sejak sequencer memberikan pesan agar kausal, dan karena semua lainnyaproses menyampaikan pesan dalam urutan yang sama seperti sequencer, pemesanan ini memangbaik total dan kausal.kelompok yang tumpang tindih • Kami telah dianggap hanya kelompok-kelompok non-tumpang tindih dalamsebelumnya definisi dan algoritma untuk FIFO, total dan kausal semantik pemesanan. Inimenyederhanakan masalah, tetapi tidak memuaskan, karena dalam proses umum harusanggota beberapa kelompok yang tumpang tindih. Misalnya, proses mungkin tertarik dalamperistiwa dari berbagai sumber dan dengan demikian bergabung satu set yang sesuai dari acara-distribusikelompok.Kami dapat memperpanjang definisi memesan perintah global yang [Hadzilacos dan Toueg1994], di mana kita harus mempertimbangkan bahwa jika pesan m adalah multicast untuk g, dan jika pesanm adalah multicast untuk g, maka kedua pesan yang ditujukan kepada anggota g g:FIFO pemesanan global: Jika multicast masalah proses yang benar (g, m) dan kemudianmulticast (g, m), maka setiap proses yang benar dalam g g yang memberikan m akan memberikanm sebelum m.kausal pemesanan global: Jika multicast (g, m) multicast (g, m), di mana adalahterjadi-sebelum hubungan diinduksi oleh rantai pesan multicast, maka setiapproses yang benar dalam g g yang memberikan m akan memberikan m sebelum m. Berpasangan Total pemesanan: Jika proses benar memberikan pesan m dikirim ke g sebelumMemberikan m dikirim ke g, maka setiap proses yang benar di g g yang memberikan m akanmemberikan m sebelum m.Global total pemesanan: Mari < 'menjadi hubungan memesan antara peristiwa pengiriman.Kami mengharuskan '<' taat Total pemesanan berpasangan dan bahwa itu adalah asiklik - di bawahberpasangan Jumlah pemesanan, '<' tidak asiklik secara default.Salah satu cara untuk melaksanakan perintah ini akan multicast setiap pesan m keSekelompok semua proses dalam sistem. Setiap proses baik membuang atau memberikanpesan menurut apakah itu milik kelompok (m). Ini akan menjadi tidak efisien danimplementasi tidak memuaskan: multicast harus melibatkan sedikitnya proses mungkindi luar anggota kelompok tujuan. Alternatif dieksplorasi di Birman et al.[1991], Garcia-Molina dan Spauster [1991], Hadzilacos dan Toueg [1994], Kindberg[1995] dan Rodrigues et al. [1998].Multicast dalam sistem sinkron dan asynchronous • Pada bagian ini, kita telah dijelaskanalgoritma untuk multicast unordered terpercaya, (terpercaya) FIFO-memerintahkan multicast, (terpercaya)kausal memerintahkan multicast dan benar-benar memerintahkan multicast. Kami juga menunjukkan bagaimanamencapai multicast yang baik benar-benar dan kausal memerintahkan. Kami meninggalkan pembaca untukmenyusun algoritma untuk primitif multicast yang jaminan baik FIFO dan jumlahpemesanan. Semua algoritma yang kita telah dijelaskan bekerja dengan benar di asynchronoussistem.Kami tidak, bagaimanapun, memberikan suatu algoritma yang menjamin handal dan benar-benarmemerintahkan pengiriman. Mengherankan meskipun mungkin tampak, sementara mungkin dalam sinkron dengansistem, protokol dengan jaminan ini tidak mungkin dalam asynchronous didistribusikanSistem - bahkan salah satu yang telah di terburuk mengalami kegagalan proses kecelakaan tunggal. Kami kembali ketitik ini pada bagian berikutnya. 15.5 Konsensus dan masalah terkait  Bagian ini memperkenalkan masalah konsensus [Pease et al. 1980, Lamport et al.1982] dan masalah yang terkait jenderal Bizantium dan konsistensi interaktif. Kamilihat ini secara kolektif sebagai masalah perjanjian. Secara kasar, masalahnya adalahuntuk proses untuk menyepakati nilai setelah satu atau lebih dari proses telah mengusulkan apanilai yang seharusnya.Misalnya, di Bab 2 kita menggambarkan situasi di mana dua tentara harusmemutuskan secara konsisten untuk menyerang musuh bersama atau mundur. Demikian pula, kita mungkin memerlukanbahwa semua proses yang benar mengendalikan mesin pesawat ruang angkasa harus memutuskan apakah'Lanjutkan' atau 'membatalkan' setelah masing-masing telah mengusulkan satu tindakan atau yang lain, dan dalam suatu transaksiuntuk mentransfer dana dari satu rekening ke rekening lain proses yang terlibat harus konsistensetuju untuk melakukan debit masing-masing dan kredit. Dalam mutual exclusion, proses setujuyang proses dapat memasuki critical section. Dalam pemilihan, proses menyepakatiyang merupakan proses terpilih. Dalam multicast benar-benar memerintahkan, proses setuju padaurutan pengiriman pesan.Protokol ada yang disesuaikan dengan tipe-tipe individu perjanjian. Kamidijelaskan beberapa dari mereka di atas, dan Bab 16 dan 17 memeriksa transaksi. Tapi ituberguna bagi kita untuk mempertimbangkan bentuk yang lebih umum dari kesepakatan, dalam pencarian untuk umumkarakteristik dan solusi.Bagian ini mendefinisikan konsensus yang lebih tepat dan menghubungkannya dengan tiga terkaitmasalah kesepakatan: jenderal Bizantium, konsistensi interaktif dan benar-benar memerintahkanmulticast. Kami pergi untuk memeriksa keadaan apa masalah dapat diselesaikan,dan untuk membuat sketsa beberapa solusi. Secara khusus, kita membahas kemustahilan terkenalHasil Fischer et al. [1985], yang menyatakan bahwa dalam sistem asynchronous koleksiproses yang mengandung hanya satu proses yang rusak tidak dapat dijamin untuk mencapaikonsensus. Akhirnya, kami mempertimbangkan bagaimana itu adalah bahwa algoritma praktis ada meskipunHasil kemustahilan.  15.5.1 Model Sistem dan masalah definisi Model sistem kami meliputi kumpulan proses pi (i = 1 2 N) berkomunikasimelalui pesan lewat. Kebutuhan penting yang berlaku dalam banyak situasi praktisadalah untuk konsensus untuk dicapai bahkan di hadapan kesalahan. Kami berasumsi, seperti sebelumnya,komunikasi yang handal tapi itu proses mungkin gagal. Pada bagian ini kita mempertimbangkanBizantium (sewenang-wenang) kegagalan proses, serta kegagalan kecelakaan. Kita kadang-kadang menentukanasumsi bahwa sampai beberapa nomor f proses N yang rusak - yaitu, mereka menunjukkanbeberapa jenis tertentu kesalahan; sisa proses yang benar.Jika kegagalan sewenang-wenang dapat terjadi, maka faktor lain dalam menentukan sistem kamiapakah proses digital menandatangani pesan yang mereka kirim (lihat Bagian 11.4). Jikaproses menandatangani pesan mereka, maka proses rusak terbatas dalam bahaya yang dapat dilakukan.Secara khusus, selama algoritma kesepakatan itu tidak dapat membuat klaim palsu tentangnilai-nilai bahwa proses yang benar telah dikirim ke sana. Relevansi penandatanganan pesan akanmenjadi lebih jelas ketika kita membahas solusi untuk masalah jenderal Bizantium. Olehdefault, kita mengasumsikan bahwa penandatanganan tidak terjadi.Definisi masalah konsensus • Untuk mencapai konsensus, setiap proses pi dimulai dinegara bimbang dan mengusulkan nilai vi tunggal, yang diambil dari satu set D(I = 1 2 N). Proses berkomunikasi dengan satu sama lain, bertukar nilai.Setiap proses kemudian menetapkan nilai variabel keputusan, di. Dalam melakukan hal itu memasukimemutuskan negara, di mana ia mungkin tidak lagi berubah di (i = 1 2 N). Gambar 15.16menunjukkan tiga proses yang terlibat dalam algoritma konsensus. Dua proses mengusulkan'Lanjutkan' dan yang ketiga mengusulkan 'batalkan' tapi kemudian crash. Kedua proses yang tetapmengoreksi setiap memutuskan 'lanjutkan'.Persyaratan dari algoritma konsensus adalah bahwa kondisi berikutharus terus untuk setiap pelaksanaan itu:Pemutusan: Akhirnya setiap proses yang benar menetapkan variabel keputusan.Kesepakatan: Nilai Keputusan semua proses yang benar adalah sama: jika pi dan pj yangyang benar dan telah memasuki negara memutuskan, maka di = dj (i j = 1 2 N).Integritas: Jika proses yang benar semua mengusulkan nilai yang sama, maka setiap yang benarproses di negara memutuskan memilih nilai tersebut.Variasi pada definisi integritas mungkin tepat, sesuai denganaplikasi. Misalnya, tipe lemah integritas akan untuk nilai keputusan untuk Gambar 15.16 Konsensus selama tiga proses  P2P3 (crash)P1algoritma konsensusv1 = melanjutkanv3 = batalkanv2 = melanjutkand1: = melanjutkan d2: = melanjutkan sama nilai bahwa beberapa proses yang benar diusulkan - belum tentu semua dari mereka. Kita gunakandefinisi di atas kecuali dinyatakan lain. Integritas juga dikenal sebagai validitas diliteratur.Untuk membantu dalam memahami bagaimana rumusan masalah diterjemahkan ke dalamalgoritma, mempertimbangkan sistem di mana proses tidak bisa gagal. Hal ini kemudian mudah untukmemecahkan konsensus. Sebagai contoh, kita dapat mengumpulkan proses ke dalam kelompok dan masing-masingProses andal multicast nilainya diusulkan kepada anggota kelompok. setiap prosesmenunggu sampai telah mengumpulkan semua nilai N (termasuk sendiri). Kemudian mengevaluasi fungsimajorityv1 v2 vN, yang mengembalikan nilai yang terjadi paling sering di antara nyaargumen, atau nilai khusus D jika tidak ada mayoritas ada. Penghentian dijamindengan keandalan operasi multicast. Perjanjian dan integritas dijamin olehdefinisi mayoritas dan properti integritas dari multicast handal. setiap prosesmenerima set yang sama nilai-nilai yang diusulkan, dan setiap proses mengevaluasi fungsi yang samadari nilai-nilai. Jadi mereka semua harus setuju, dan jika setiap proses mengusulkan nilai yang sama,maka mereka semua memutuskan nilai ini.Catatan mayoritas yang hanya satu fungsi mungkin bahwa proses bisa digunakan untukmenyepakati nilai dari nilai-nilai kandidat. Misalnya, jika nilai-nilai yang diperintahkan,maka fungsi minimum dan maksimum mungkin tepat.Jika proses dapat kecelakaan ini memperkenalkan komplikasi mendeteksi kegagalan, dan itutidak segera jelas bahwa lari dari algoritma konsensus dapat mengakhiri. Bahkan, jikasistem ini asynchronous, maka tidak mungkin; kita akan kembali ke titik ini tak lama.Jika proses dapat gagal dalam sewenang-wenang (Bizantium) cara, maka proses rusak bisa diPrinsip mengkomunikasikan nilai-nilai acak untuk yang lain. Hal ini mungkin tampak tidak mungkin dalam prakteknya,tetapi tidak melampaui batas-batas kemungkinan untuk proses dengan bug gagal dengan cara ini.Selain itu, kesalahan mungkin tidak disengaja, tetapi hasil dari nakal atau jahatoperasi. Seseorang dengan sengaja bisa membuat proses mengirim nilai yang berbeda untuk berbedarekan-rekan dalam upaya untuk menggagalkan orang lain, yang mencoba untuk mencapai konsensus. Seandainyainkonsistensi, proses yang benar harus membandingkan apa yang telah mereka terima dengan apa yang lainnyaproses mengaku telah menerima. Bizantium jenderal masalah • Dalam pernyataan resmi dari para jenderal BizantiumMasalah [Lamport et al. 1982], tiga atau lebih jenderal yang setuju untuk menyerang atau mundur.Satu, komandan, mengeluarkan perintah. Yang lain, letnan ke komandan, harusmemutuskan apakah akan menyerang atau mundur. Tapi satu atau lebih dari para jenderal mungkin 'berbahaya'- Yaitu, rusak. Jika komandan adalah berbahaya, ia mengusulkan menyerang satu umumdan mundur ke yang lain. Jika seorang letnan adalah berbahaya, ia mengatakan salah satu dari teman-temannya bahwaKomandan menyuruhnya untuk menyerang dan lain bahwa mereka mundur.Bizantium jenderal masalah berbeda dari konsensus bahwa ygProses memasok nilai yang yang lain untuk menyepakati, bukan masing-masingmengusulkan nilai. Persyaratan adalah:Pemutusan: Akhirnya setiap proses yang benar menetapkan variabel keputusan.Kesepakatan: Nilai Keputusan semua proses yang benar adalah sama: jika pi dan pj yangyang benar dan telah memasuki negara memutuskan, maka di = dj (i j = 1 2 N).Integritas: Jika komandan benar, maka semua proses yang benar memutuskan nilaibahwa komandan yang diusulkan.Perhatikan bahwa, untuk masalah jenderal Bizantium, integritas berarti kesepakatan ketikaKomandan benar; tapi komandan tidak perlu benar.Konsistensi interaktif • Masalah konsistensi interaktif adalah varian lain darikonsensus, di mana setiap proses mengusulkan nilai tunggal. Tujuan dari algoritma ini adalahuntuk proses yang benar untuk menyepakati vektor nilai, satu untuk setiap proses. Kami memanggilini 'vektor keputusan'. Misalnya, tujuan bisa untuk masing-masing satu set prosesuntuk memperoleh informasi yang sama tentang negara mereka masing-masing.Persyaratan untuk konsistensi interaktif adalah:Pemutusan: Akhirnya setiap proses yang benar menetapkan variabel keputusan.Kesepakatan: Vektor keputusan dari semua proses yang benar adalah sama.Integritas: Jika pi benar, maka semua proses yang benar memutuskan vi sebagai engankomponen vektor mereka.Berkaitan konsensus untuk masalah lain • Meskipun itu adalah umum untuk mempertimbangkanjenderal Bizantium masalah dengan kegagalan proses sewenang-wenang, sebenarnya masing-masing tigamasalah - konsensus, jenderal Bizantium dan konsistensi interaktif - bermaknadalam konteks baik kegagalan sewenang-wenang atau kecelakaan. Demikian pula, masing-masing dapat dibingkaidengan asumsi baik sinkron atau sistem asynchronous.Kadang-kadang mungkin untuk mendapatkan solusi untuk satu masalah menggunakan solusi untuklain. Ini adalah properti yang sangat berguna, baik karena meningkatkan pemahaman kita tentangmasalah dan karena dengan menggunakan kembali solusi kita berpotensi dapat menghematupaya pelaksanaan dan kompleksitas.Misalkan terdapat solusi untuk konsensus (C), jenderal Bizantium (BG) dankonsistensi interaktif (IC) sebagai berikut:Ci v1 v2 VN mengembalikan nilai keputusan pi dalam menjalankan solusi untukmasalah konsensus, di mana v1 v2 VN adalah nilai-nilai yang proses yang diusulkan.BGij v mengembalikan nilai keputusan pi dalam menjalankan solusi untuk Byzantinejenderal masalah, di mana pj, komandan, mengusulkan nilai v.ICiv1 v2 vNjmengembalikan nilai j dalam vektor keputusan pi di lari darisolusi untuk masalah konsistensi interaktif, di mana v1 v2 VN adalah nilai-nilaibahwa proses yang diusulkan.Definisi Ci, BGI dan ICI menganggap bahwa proses rusak mengusulkan satunilai nosional, meskipun mungkin telah memberikan nilai yang diusulkan berbeda untuk masing-masingproses lainnya. Ini hanya kenyamanan: solusi tidak akan bergantung pada apapun sepertinilai nosional.Hal ini dimungkinkan untuk membangun solusi dari solusi untuk masalah lainnya. Kami memberikantiga contoh:IC dari BG: Kami membangun sebuah solusi untuk IC dari BG dengan menjalankan BG N kali, sekalidengan masing-masing pi proses (i j = 1 2 N) bertindak sebagai komandan:Ici v1 v2 VN j BGI j vj = (i j = 1 2 N)C dari IC: Untuk kasus di mana mayoritas proses yang benar, kita membangunsolusi untuk C dari IC dengan menjalankan IC untuk menghasilkan vektor dari nilai-nilai pada setiap proses,kemudian menerapkan fungsi yang sesuai pada nilai-nilai vektor untuk menurunkan nilai tunggal:Ci v1 VN mayoritas ICI v1 VN 1 ICI v1 VN = Ndi mana i = 1 2N dan mayoritas adalah seperti yang didefinisikan di atas.BG dari C: Kami membangun sebuah solusi untuk BG dari C sebagai berikut:• Komandan pj mengirimkan nilainya diusulkan v untuk dirinya sendiri dan masing-masingproses tersisa.• Semua proses berjalan C dengan nilai v1 v2 VN yang mereka terima (pj mungkinsalah).• Mereka berasal BGij v Ci v1 v2 VN = (i = 1 2 N).pembaca harus memeriksa bahwa penghentian, perjanjian dan integritas kondisidiawetkan dalam setiap kasus. Fischer [1983] menghubungkan tiga masalah secara lebih rinci.Dalam sistem dengan kegagalan kecelakaan, konsensus adalah setara dengan memecahkan handal danbenar-benar memerintahkan multicast: diberi solusi untuk satu, kita dapat memecahkan lainnya. menerapkankonsensus dengan handal dan benar-benar memerintahkan operasi multicast RTO-multicast adalahmudah. Kami mengumpulkan semua proses menjadi kelompok, g. Untuk mencapai konsensus, setiapProses pi melakukan RTO-multicast (g, vi). Kemudian setiap proses pi memilih di = mi,mana mi adalah nilai pertama yang pi RTO-memberikan. Properti terminasi berikut darikeandalan multicast tersebut. Perjanjian dan integritas sifat mengikuti darikehandalan dan jumlah pemesanan pengiriman multicast. Chandra dan Toueg [1996]menunjukkan bagaimana diandalkan dan benar-benar memerintahkan multicast dapat diturunkan dari konsensus.  15.5.2 Konsensus dalam sistem sinkron Bagian ini menjelaskan suatu algoritma untuk memecahkan konsensus dalam sistem sinkron,meskipun didasarkan pada bentuk modifikasi dari persyaratan integritas. Algoritma menggunakanhanya sebuah protokol multicast dasar. Ini mengasumsikan bahwa hingga f dari N proses pameran kecelakaankegagalan. Untuk mencapai konsensus, setiap proses yang benar Globe mengumpulkan diusulkan nilai-nilai dari yang lainproses. algoritma hasil di f + 1 putaran, di masing-masing yang benarmemproses B-multicast nilai antara mereka. Pada sebagian besar proses f mungkin macet, olehanggapan. Paling buruk, semua crash f akan terjadi selama putaran, tetapi algoritmamenjamin bahwa pada akhir putaran semua proses yang benar yang selamat akanberada dalam posisi untuk setuju.Algoritma, yang ditunjukkan pada Gambar 15.17 Gambar 15,17 Konsensus dalam sistem sinkron Algoritma untuk proses; hasil algoritma di putaranpada inisialisasi: =; = {};Dalam putaran r ()B-multicast (g,); // Kirim hanya nilai yang belum dikirim: =;sementara (di babak r){Pada B-memberikan () dari beberapa: =;}setelah putaranmenetapkan;pi g f + 1Valuesi1 vi Valuesi01 r f + 1Valuesir Valuesir - 1 -Valuesir + 1 ValuesirVj pjValuesir + 1 Valuesir + 1 Vj f + 1di minimum Valuesif + 1 =   , Didasarkan pada bahwa dengan Dolev dan Kuat[1983] dan presentasi oleh Attiya dan Welch [1998]. bentuk mereka modifikasi dariPersyaratan integritas berlaku untuk nilai-nilai yang diusulkan dari semua proses, bukan hanya yang benaryang: jika semua proses, apakah benar atau tidak, mengusulkan nilai yang sama, maka setiap yang benarproses di negara memutuskan akan memilih nilai tersebut. Mengingat bahwa algoritma mengasumsikankegagalan kecelakaan paling buruk, nilai-nilai yang diusulkan dari proses yang benar dan non-benar akantidak diharapkan untuk berbeda, setidaknya tidak atas dasar kegagalan. bentuk revisiintegritas memungkinkan penggunaan yang nyaman dari fungsi minimum untuk memilih nilai keputusandari yang diusulkan.Variabel Valuesir memegang seperangkat nilai-nilai yang diusulkan dikenal untuk memproses pi dimulai dari putaran r. Setiap proses multicast set nilai-nilai yang belum dikirimputaran sebelumnya. Ia kemudian mengambil pengiriman pesan multicast serupa dari lainnyamemproses dan mencatat nilai-nilai baru. Meskipun ini tidak ditampilkan pada Gambar 15.17, yangdurasi putaran dibatasi dengan menetapkan batas waktu berdasarkan waktu maksimum untukproses yang benar untuk multicast pesan. Setelah f + 1 putaran, setiap proses memilihnilai minimum telah menerima sebagai nilai keputusan.Penghentian jelas dari kenyataan bahwa sistem ini sinkron. Untuk memeriksakebenaran algoritma, kita harus menunjukkan bahwa setiap proses tiba di set yang samanilai-nilai pada akhir babak final. Perjanjian dan integritas (dalam bentuk yang dimodifikasi) akankemudian ikuti, karena proses menerapkan fungsi minimum untuk set ini. Asumsikan, sebaliknya, bahwa dua proses berbeda dalam set terakhir mereka nilai-nilai.Tanpa kehilangan umum, beberapa proses pi benar memiliki nilai v yang lainbenar proses pj (i j) tidak miliki. Satu-satunya penjelasan untuk pi yang memilikidiusulkan nilai v pada akhir yang pj tidak memiliki adalah bahwa setiap proses ketiga, pk, mengatakan,yang berhasil mengirimkan v ke pi jatuh sebelum v bisa dikirim ke pj. Pada gilirannya, setiapProses pengiriman v di babak sebelumnya harus jatuh, untuk menjelaskan mengapa pk memilikiv di babak itu, tetapi pj tidak menerimanya. Melanjutkan dengan cara ini, kita harus mengandaikan setidaknyasatu kecelakaan di setiap putaran sebelumnya. Tapi kita telah mengasumsikan bahwa paling f crashdapat terjadi, dan ada f + 1 putaran. Kami telah tiba di kontradiksi.Ternyata algoritma untuk mencapai konsensus meskipun hingga kegagalan kecelakaan fmembutuhkan setidaknya f + 1 putaran pertukaran pesan, tidak peduli bagaimana itu dibangun[Dolev dan Kuat 1983]. Ini lebih rendah terikat juga berlaku dalam kasus kegagalan Bizantium[Fischer dan Lynch 1982].     15.5.3 Para jenderal Bizantium masalah dalam sistem sinkron Sekarang kita membahas Bizantium masalah jenderal dalam sistem sinkron. tidak sepertialgoritma untuk konsensus dijelaskan pada bagian sebelumnya, di sini kita mengasumsikan bahwaproses dapat menunjukkan kegagalan sewenang-wenang. Artinya, proses yang salah dapat mengirim pesan apapundengan nilai setiap saat; dan mungkin menghilangkan untuk mengirim pesan apapun. Sampai f dari Nproses mungkin rusak. proses yang benar dapat mendeteksi adanya pesan melaluitimeout; tetapi mereka tidak dapat menyimpulkan bahwa pengirim telah jatuh, karena mungkin diamuntuk beberapa waktu dan kemudian mengirim pesan lagi.Kami berasumsi bahwa saluran komunikasi antara pasangan proses yangpribadi. Jika proses bisa memeriksa semua pesan bahwa proses lain yang dikirim, makabisa mendeteksi inkonsistensi dalam apa proses rusak mengirimkan ke proses yang berbeda.asumsi default kita keandalan saluran berarti bahwa tidak ada proses yang salah bisa menyuntikkanpesan ke dalam saluran komunikasi antara proses yang benar.Lamport et al. [1982] dianggap kasus tiga proses yang mengirimkan unsignedpesan satu sama lain. Mereka menunjukkan bahwa tidak ada solusi yang menjamin untuk memenuhikondisi masalah jenderal Bizantium jika satu proses diperbolehkan untuk gagal. Merekaumum hasil ini menunjukkan bahwa tidak ada solusi ada jika N 3f. Kami akan menunjukkanhasil ini tak lama. Mereka melanjutkan untuk memberikan suatu algoritma yang memecahkan Bizantiummasalah jenderal dalam sistem sinkron jika N 3f + 1, untuk unsigned (mereka menyebutnya'Lisan') pesan.Ketidakmungkinan dengan tiga proses • Gambar 15.18 menunjukkan dua skenario di mana hanya satudari tiga proses rusak. Dalam konfigurasi kiri salah satu letnan, p3, adalahsalah; di sebelah kanan komandan, p1, rusak. Masing-masing skenario pada Gambar 15.18 menunjukkandua putaran pesan: nilai komandan mengirimkan, dan nilai-nilai yangletnan kemudian mengirim satu sama lain. Awalan numerik berfungsi untuk menentukansumber pesan dan untuk menunjukkan putaran yang berbeda. Membaca ':' simbol dalam pesansebagai 'kata'; misalnya, '3: 1: u' adalah pesan '3 kata 1 kata u'.Dalam skenario kiri, komandan benar mengirimkan nilai yang sama v untuk setiapdari dua proses lainnya, dan p2 benar gema ini untuk p3. Namun, p3 mengirimkannilai u v ke p2. Semua p2 tahu pada tahap ini adalah bahwa ia telah menerima nilai-nilai yang berbeda; saya ttidak bisa membedakan mana yang dikirim oleh komandan. Gambar 15.18 Tiga jenderal Bizantium    proses rusak ditampilkan dalam abu-abu p1 (Komandan)p2 p31: v 1: v2: 1: v3: 1: up1 (Komandan)p2 p31: w 1: x2: 1: w3: 1: xDalam skenario sebelah kanan, komandan rusak dan mengirimkan nilai-nilai yang berbeda-beda untukletnan. Setelah p3 telah benar menggema nilai x yang diterima, p2 adalah disituasi yang sama seperti di saat p3 sudah rusak: mereka telah menerima dua nilai yang berbeda.Jika ada solusi, maka proses p2 terikat untuk memutuskan nilai v ketikaKomandan benar, dengan kondisi integritas. Jika kita menerima bahwa tidak ada algoritma dapatmungkin membedakan antara dua skenario, p2 harus juga memilih nilai yang dikirim olehkomandan dalam skenario sebelah kanan.Berikut persis alasan yang sama untuk p3, dengan asumsi bahwa itu adalah benar, kitadipaksa untuk menyimpulkan (dengan simetri) yang p3 juga memilih nilai yang dikirim oleh komandansebagai nilai keputusan. Tapi ini bertentangan dengan kondisi perjanjian (komandan mengirimkannilai-nilai yang berbeda jika rusak). Jadi tidak ada solusi yang mungkin.Perhatikan bahwa argumen ini bersandar pada intuisi kita bahwa tidak ada yang dapat dilakukan untuk meningkatkanpengetahuan umum yang benar melampaui tahap pertama, di mana ia tidak bisa membedakan mana prosesrusak. Hal ini dimungkinkan untuk membuktikan kebenaran intuisi ini [Pease et al. 1980].kesepakatan Bizantium dapat dihubungi untuk tiga jenderal, dengan salah satu dari mereka rusak, jikajenderal digital menandatangani pesan mereka.Ketidakmungkinan dengan N 3f • Pease et al. umum hasil ketidakmungkinan dasar untuktiga proses, untuk membuktikan bahwa tidak ada solusi yang mungkin jika N 3f. Secara garis besar, argumenadalah sebagai berikut. Asumsikan bahwa ada solusi dengan N 3f. Biarkan masing-masing tiga proses p1,p2 dan p3 menggunakan solusi untuk mensimulasikan perilaku n1, n2 dan n3 jenderal,masing-masing, di mana n1 + n2 + n3 = N dan n1 n2 n3 N / 3. Asumsikan, lebih jauh lagi, bahwasalah satu dari tiga proses rusak. Orang-orang dari p1, p2 dan p3 yang mensimulasikan benarjenderal yang benar: mereka mensimulasikan interaksi jenderal mereka sendiri secara internal dan mengirimpesan dari jenderal mereka dengan yang disimulasikan oleh proses lainnya. Proses rusak inijenderal simulasi yang rusak: pesan yang mengirimkan sebagai bagian dari simulasi dengandua proses lainnya mungkin palsu. Sejak N 3f dan n1 n2 n3 N / 3, paling fjenderal simulasi yang rusak.Karena algoritma bahwa proses berjalan diasumsikan benar,simulasi berakhir. Para jenderal simulasi yang benar (dalam dua proses yang benar)setuju dan memenuhi properti integritas. Tapi sekarang kita memiliki sarana untuk dua yang benarproses dari tiga untuk mencapai konsensus: setiap memutuskan pada nilai yang dipilih oleh semuajenderal simulasi mereka. Hal ini bertentangan mengakibatkan ketidakmungkinan untuk tiga proses,dengan satu rusak.BAGIAN 15,5 KONSENSUS DAN TERKAIT MASALAH 667Solusi dengan satu proses yang rusak • Tidak ada ruang yang cukup untuk menggambarkan sepenuhnyaalgoritma Pease et al. yang memecahkan Bizantium masalah jenderal di sinkron satusistem dengan N 3f + 1. Sebaliknya, kami memberikan operasi algoritma untuk kasusN 4, f = 1 dan menggambarkan untuk N = 4, f = 1.Para jenderal yang benar mencapai kesepakatan dalam dua putaran pesan:• Pada putaran pertama, komandan mengirimkan nilai untuk masing-masing letnan.• Di babak kedua, masing-masing letnan mengirimkan nilai yang diterima untuk rekan-rekan.Seorang letnan menerima nilai dari komandan, ditambah N - 2 nilai dari rekan-rekan. Jikakomandan rusak, maka semua letnan yang benar dan masing-masing akan berkumpulpersis set nilai-nilai yang komandan dikirim. Jika tidak, salah satu letnanrusak; masing-masing rekan-rekan yang benar menerima N - 2 salinan dari nilai yang komandanmengirim, ditambah nilai yang letnan rusak dikirim ke sana.Dalam kedua kasus, letnan yang benar hanya perlu menerapkan fungsi mayoritas sederhanake set nilai-nilai yang mereka terima. Sejak N 4, N - 2 2. Oleh karena itu, mayoritasFungsi akan mengabaikan nilai apapun yang seorang letnan yang salah dikirim, dan akan menghasilkan nilaibahwa komandan dikirim jika komandan benar.Kami sekarang menggambarkan algoritma yang baru saja kita digariskan untuk kasus empatjenderal. Gambar 15.19 menunjukkan dua skenario sama dengan yang di angka 15,18, tetapi dalam hal inikasus ada empat proses, salah satunya adalah rusak. Gambar 15.19 Empat jenderal Bizantium    proses rusak ditampilkan dalam abu-abu     p1 (Komandan)p2 p31: v 1: v2: 1: v3: 1: up41: v4: 1: v2: 1: v 3: 1: w4: 1: vp1 (Komandan)p2 p31: u 1: w2: 1: u3: 1: wp41: v4: 1: v2: 1: u 3: 1: w4: 1: vSeperti pada Gambar 15.18, di kiri yangkonfigurasi salah satu letnan, p3, rusak; di sebelah kanan, komandan, p1, adalahsalah.               Dalam kasus kiri, dua proses letnan benar setuju, memutuskan padaNilai komandan:p2 memutuskan majorityv u v = vp4 memutuskan majorityv v w = vDalam kasus sebelah kanan komandan rusak, tapi tiga proses yang benar setuju:p2, p3 dan p4 memutuskan majorityu v w = (nilai khusus berlakudi mana tidak ada mayoritas nilai-nilai yang ada).               Algoritma memperhitungkan fakta bahwa proses yang salah dapat menghilangkan untuk mengirim pesan.Jika proses yang benar tidak menerima pesan dalam batas waktu yang sesuai (sistemadalah sinkron), itu berlangsung seolah-olah proses yang rusak telah mengirim nilai .Diskusi • Kita dapat mengukur efisiensi solusi untuk para jenderal Bizantiummasalah - atau masalah perjanjian lain - dengan bertanya:• Berapa banyak putaran pesan yang dibutuhkan? (Ini merupakan faktor dalam berapa lama waktu yang dibutuhkan untukalgoritma untuk mengakhiri.)• Berapa banyak pesan yang dikirim, dan apa ukuran? (Ini mengukur totalpemanfaatan bandwidth dan memiliki dampak pada waktu eksekusi.)Dalam kasus umum (f 1) Lamport et al. [1982] algoritma untuk pesan unsignedmengoperasikan lebih f + 1 putaran. Di setiap putaran, proses mengirim ke subset dari yang lainmemproses nilai-nilai yang diterima di babak sebelumnya. Algoritma ini sangat mahal:itu melibatkan pengiriman O Nf + 1 pesan.Fischer dan Lynch [1982] membuktikan bahwa solusi deterministik konsensusdengan asumsi kegagalan Bizantium (dan karenanya untuk masalah jenderal Bizantium, sebagai Bagian15.5.1 menunjukkan) akan mengambil minimal f + 1 putaran pesan. Jadi tidak ada algoritma dapat beroperasilebih cepat dalam hal ini daripada Lamport et al. Tetapi sudah ada perbaikan dikompleksitas pesan, misalnya Garay dan Musa [1993].Beberapa algoritma, seperti yang dari Dolev dan Kuat [1983], mengambil keuntungan daripesan ditandatangani. Dolev dan Strong algoritma lagi mengambil f + 1 putaran, tetapijumlah pesan yang dikirim hanya O N2 .Kompleksitas dan biaya solusi menyarankan bahwa mereka hanya berlakudi mana ancaman besar. Solusi yang didasarkan pada pengetahuan yang lebih rinci dariModel kesalahan mungkin lebih efisien [Barborak et al. 1993]. Jika pengguna yang jahat adalahsumber ancaman, maka sistem untuk melawan mereka cenderung menggunakan tanda tangan digital; sebuahsolusi tanpa tanda tangan tidak praktis.15.5.4 Ketidakmungkinan dalam sistem asynchronousKami telah menyediakan solusi untuk konsensus dan Bizantium masalah jenderal (danmaka, oleh derivasi, konsistensi interaktif). Namun, semua solusi ini mengandalkanpada sistem yang sinkron. Algoritma menganggap bahwa pertukaran pesanberlangsung di putaran, dan bahwa proses berhak waktu dan menganggap bahwa rusakProses tidak mengirim mereka pesan dalam putaran, karena delay maksimum memilikitelah terlampaui.Fischer et al. [1985] membuktikan bahwa tidak ada algoritma dapat menjamin untuk mencapai konsensus disistem asynchronous, bahkan dengan satu proses kegagalan kecelakaan. Dalam sebuah asynchronoussistem, proses dapat menanggapi pesan di kali sewenang-wenang, sehingga proses jatuh adalahdibedakan dari satu lambat. Buktinya mereka, yang berada di luar cakupan buku ini,melibatkan menunjukkan bahwa selalu ada beberapa kelanjutan dari pelaksanaan proses 'yangmenghindari konsensus yang tercapai.Kami segera tahu dari hasil Fischer et al. bahwa tidak ada jaminansolusi dalam sistem asynchronous untuk masalah jenderal Bizantium, untuk interaktifkonsistensi atau untuk benar-benar memerintahkan dan multicast handal. Jika ada solusi tersebutkemudian, dengan hasil Bagian 15.5.1, kita akan memiliki solusi untuk konsensus -bertentangan dengan hasil kemustahilan.Perhatikan kata 'jaminan' dalam laporan hasil kemustahilan. Hasiltidak berarti bahwa proses tidak pernah dapat menjangkau didistribusikan konsensus dalam asynchronoussistem jika ada yang rusak. Hal ini memungkinkan bahwa konsensus dapat dicapai dengan beberapa probabilitaslebih besar dari nol, mengkonfirmasikan apa yang kita ketahui dalam praktek. Misalnya, meskipun faktabahwa sistem kami sering efektif asynchronous, sistem transaksi telahmencapai konsensus secara teratur selama bertahun-tahun.Salah satu pendekatan untuk bekerja di sekitar hasil ketidakmungkinan adalah untuk mempertimbangkan sebagiansistem sinkron, yang cukup lemah dari sistem sinkron menjadiberguna sebagai model sistem praktis, dan cukup kuat dari asynchronoussistem untuk konsensus untuk dipecahkan di dalamnya [Dwork et al. 1988]. Pendekatan yangdi luar cakupan buku ini. Namun, sekarang kita akan menguraikan tiga teknik lain untukbekerja di sekitar hasil kemustahilan: kesalahan masking, dan mencapai konsensus olehmengeksploitasi detektor kegagalan dan dengan mengacak aspek perilaku proses '.Masking kesalahan • Teknik pertama adalah untuk menghindari hasil ketidakmungkinan sama sekali denganmasking setiap kegagalan proses yang terjadi (lihat Bagian 2.4.2 untuk pengenalan kesalahanmasking). Misalnya, sistem transaksi menggunakan penyimpanan persisten, yang bertahankegagalan kecelakaan. Jika proses crash, maka restart (otomatis, atau olehadministrator). Proses ini menempatkan informasi yang cukup dalam penyimpanan persisten di kritispoin dalam program sehingga jika harus crash dan restart, ia akan menemukan data yang cukupuntuk dapat melanjutkan dengan benar dengan tugasnya terganggu. Dengan kata lain, ia akan berperilakuseperti proses yang benar, tapi itu kadang-kadang membutuhkan waktu yang lama untuk melakukanpengolahan langkah.Tentu saja, kesalahan masking umumnya berlaku dalam desain sistem. Bab 16membahas bagaimana sistem transaksional memanfaatkan penyimpanan persisten. Bab 18menjelaskan bagaimana kegagalan proses juga dapat ditutupi oleh mereplikasi komponen software.Konsensus menggunakan detektor kegagalan • Metode lain untuk menghindari yangHasil kemustahilan adalah dengan menggunakan detektor kegagalan. Beberapa sistem praktis mempekerjakan'Sempurna dengan desain' detektor kegagalan untuk mencapai konsensus. Tidak ada detektor kegagalan dalamsistem asynchronous yang bekerja semata-mata oleh pesan lewat benar-benar dapat menjadi sempurna.Namun, proses bisa setuju untuk menganggap sebuah proses yang tidak merespon selama lebih dari satuwaktu dibatasi telah gagal. Sebuah proses tidak responsif tidak mungkin benar-benar telah gagal, tapiproses tersisa bertindak seolah-olah itu dilakukan. Mereka membuat kegagalan 'gagal-diam' olehmembuang pesan berikutnya apapun yang mereka lakukan sebenarnya menerima dari proses 'gagal'.Dengan kata lain, kita telah secara efektif berubah sistem asynchronous menjadi sinkron sebuahsatu. Teknik ini digunakan dalam sistem ISIS [Birman 1993].Metode ini bergantung pada detektor kegagalan biasanya menjadi akurat. Ketika ituakurat, maka sistem harus melanjutkan tanpa anggota kelompok yang lain bisaberpotensi telah memberikan kontribusi untuk efektivitas sistem. Sayangnya, membuatKegagalan detektor cukup akurat melibatkan menggunakan nilai batas waktu yang panjang, memaksaproses menunggu waktu yang relatif lama (dan tidak melakukan pekerjaan yang bermanfaat) sebelum menyimpulkanbahwa proses telah gagal. Masalah lain yang muncul untuk pendekatan ini adalah jaringanpartisi, yang kita bahas dalam Bab 18.Sebuah pendekatan yang sangat berbeda adalah dengan menggunakan detektor kegagalan tidak sempurna, dan untuk mencapaikonsensus sementara memungkinkan proses diduga berperilaku benar bukan termasukmereka. Chandra dan Toueg [1996] menganalisis sifat yang detektor kegagalan keharusanmiliki untuk memecahkan masalah konsensus dalam sistem asynchronous. mereka menunjukkankonsensus yang dapat diselesaikan dalam sistem asynchronous, bahkan dengan kegagalan tidak dapat diandalkandetektor, jika kurang proses dari N 2 kecelakaan dan komunikasi dapat diandalkan. terlemahjenis detektor kegagalan yang ini begitu disebut detektor kegagalan akhirnya lemah. Ini adalah salah satu yang baik: Akhirnya lemah lengkap: Setiap proses yang rusak akhirnya dicurigai permanen oleh beberapa proses yang benar.Akhirnya lemah akurat: Setelah beberapa titik waktu, setidaknya satu proses yang benar adalah tidak pernah diduga oleh proses yang benar. Chandra dan Toueg menunjukkan bahwa kita tidak bisa menerapkan detektor kegagalan akhirnya lemah dalam sistem asynchronous dengan pesan lewat saja. Namun, kami menggambarkan detektor kegagalan berbasis pesan dalam Bagian 15.1 yang menyesuaikan nilai batas waktu yang sesuaiuntuk mengamati waktu respon. Jika proses atau koneksi untuk itu sangat lambat, maka nilai timeout akan tumbuh sehingga kasus palsu mencurigai proses menjadi langka. Dalamkasus banyak sistem nyata, algoritma ini berperilaku cukup erat dengan akhirnyadetektor kegagalan lemah untuk tujuan praktis.Chandra dan Toueg ini algoritma konsensus memungkinkan diduga palsu proses untuk melanjutkan operasi normal mereka dan memungkinkan proses yang telah diduga mereka untuk menerima pesan dari mereka dan memproses pesan yang biasanya. Hal ini membuat hidup aplikasi programmer rumit, tetapi memiliki keuntungan bahwa benar proses tidak disia-siakan oleh yang palsu dikecualikan. Selain itu, timeout untuk mendeteksi kegagalan dapat diatur kurang konservatif dibandingkan dengan pendekatan ISIS. Konsensus menggunakan pengacakan • Hasil Fischer et al. [1985] tergantung pada apa kita dapat mempertimbangkan untuk menjadi 'musuh'. Ini adalah 'karakter' (sebenarnya, hanya koleksi peristiwa acak) yang dapat memanfaatkan fenomena sistem asynchronous sehingga untuk foil upaya proses 'untuk mencapai konsensus. musuh memanipulasi jaringan untuk menunda pesan sehingga mereka tiba pada waktu yang salah, dan juga memperlambat atau mempercepat proses cukup sehingga mereka berada dalam keadaan 'salah' ketika mereka menerima pesan. Teknik ketiga yang membahas hasil ketidakmungkinan adalah untuk memperkenalkan unsur kebetulan dalam perilaku proses ', sehingga musuh tidak bisa latihan nya menggagalkan strategi efektif. Konsensus mungkin masih belum dicapai dalam beberapa kasus, tetapi Metode ini memungkinkan proses untuk mencapai konsensus dalam waktu yang diharapkan terbatas. SEBUAHalgoritma probabilistik yang memecahkan konsensus bahkan dengan kegagalan Bizantium dapat ditemukandi Canetti dan Rabin [1993].    15.6 Ringkasan Kami memulai bab ini dengan membahas kebutuhan untuk proses untuk mengakses sumber daya bersamadalam kondisi mutual exclusion. Kunci tidak selalu dilaksanakan oleh serveryang mengelola sumber daya bersama, dan terpisah didistribusikan layanan saling pengecualian adalah kemudian diperlukan. Tiga algoritma dianggap bahwa mencapai saling pengecualian: satu mempekerjakan server pusat, algoritma berbasis cincin dan algoritma berbasis multicast menggunakan jam logis. Tak satu pun dari mekanisme ini dapat menahan kegagalan seperti yang kita dijelaskanmereka, meskipun mereka dapat dimodifikasi untuk mentolerir beberapa kesalahan. Berikutnya kami menjelajahi pemilu, mengingat algoritma berbasis cincin dan pengganggu algoritma, tujuan umum yang adalah untuk memilih proses unik dari himpunan - bahkan jika beberapa pemilu berlangsung secara bersamaan. Algoritma bully dapat digunakan, untuk Misalnya, untuk memilih server baru kali menguasai, atau server kunci baru, ketika sebelumnya gagal. Bagian berikut dijelaskan koordinasi dan kesepakatan dalam kelompok komunikasi. Ini dibahas multicast handal, di mana proses yang benar menyepakatiset pesan yang akan disampaikan, dan multicast dengan FIFO, kausal dan jumlah pengiriman pemesanan. Kami memberikan algoritma untuk multicast handal dan untuk ketiga jenis pengiriman pemesanan.               Akhirnya, kita menggambarkan tiga masalah konsensus, jenderal Bizantium dan konsistensi interaktif. Kami mendefinisikan kondisi untuk solusi mereka dan kami menunjukkan hubungan antara masalah ini - termasuk hubungan antara konsensus dan dapat diandalkan, benar-benar memerintahkan multicast. Solusi ada di sistem sinkron, dan kami dijelaskan beberapa dari mereka. Faktanya, solusi yang ada bahkan ketika kegagalan sewenang-wenang yang mungkin.Kami diuraikan bagian dari solusi untuk masalah jenderal Bizantium dari Lamport et al. [1982]. algoritma yang lebih baru memiliki kompleksitas yang lebih rendah, namun tidak ada prinsip dapat lebih baik f ​​+ 1 putaran diambil oleh ini algoritma, kecuali pesan yang ditandatangani secara digital.               Bab ini berakhir dengan menggambarkan hasil mendasar dari Fischer et al. [1982] tentang ketidakmungkinan menjamin konsensus dalam sistem asynchronous. Kami dibahas bagaimana itu adalah bahwa, meskipun demikian, sistem teratur jangan mencapai kesepakatan dalam sistem asynchronous.LATIHAN15.1 Apakah mungkin untuk menerapkan baik handal atau tidak dapat diandalkan (proses) detektor kegagalanmenggunakan saluran komunikasi tidak dapat diandalkan? halaman 63215.2 Jika semua proses client adalah satu-ulir, kondisi pengecualian saling ME3, yang menentukan entri dalam rangka terjadi-sebelumnya, yang relevan? halaman 63515.3 Buatlah rumus untuk throughput maksimum sistem pengecualian saling segisinkronisasi delay. halaman 63515.4 Dalam algoritma server pusat untuk saling pengecualian, menggambarkan situasi di mana dua Permintaan tidak diproses agar terjadi-sebelumnya. halaman 63615,5 Beradaptasi algoritma server pusat untuk saling pengecualian untuk menangani kegagalan kecelakaan dari setiap client (di setiap negara), dengan asumsi bahwa server benar dan diberikan kegagalan terpercaya detektor. Mengomentari apakah sistem yang dihasilkan adalah kesalahan-toleran. Apa yang akan terjadi jika klien yang memiliki lanjutan token salah diduga telah gagal? Halaman 63615,6 Berikan eksekusi contoh algoritma berbasis cincin untuk menunjukkan bahwa proses tidak tentu diberikan masuk ke bagian kritis dalam rangka terjadi-sebelumnya. halaman 63715.7 Dalam sistem tertentu, setiap proses biasanya menggunakan bagian kritis berkali-kali sebelumnya proses lain memerlukan itu. Jelaskan mengapa Ricart dan Agrawala ini multicast berbasis saling algoritma pengecualian tidak efisien untuk kasus ini, dan menjelaskan bagaimana meningkatkan nya kinerja. Apakah adaptasi Anda memenuhi kondisi liveness ME2? halaman 63915.8 Dalam algoritma pengganggu, proses pemulihan dimulai pemilu dan akan menjadi baru Koordinator jika memiliki pengenal yang lebih tinggi daripada incumbent saat ini. Apakah ini diperlukan Fitur dari algoritma? halaman 64415,9 Menyarankan bagaimana beradaptasi algoritma pengganggu untuk menangani partisi jaringan sementara (Komunikasi lambat) dan proses yang lambat. halaman 64615.10 Merancang sebuah protokol untuk multicast dasar over IP multicast. halaman 64715.11 Bagaimana, jika sama sekali, harus definisi integritas, perjanjian dan validitas untuk diandalkan multicast mengubah untuk kasus kelompok terbuka? halaman 64715.12 Jelaskan mengapa membalik urutan garis 'R-memberikan m' dan 'jika (q p) maka Bmulticast ( g, m); berakhir jika 'pada Gambar 15.9 membuat algoritma tidak lagi memenuhi seragam perjanjian. Apakah algoritma multicast handal berbasis IP multicast memuaskan seragam perjanjian? halaman 64815.13 Jelaskan apakah algoritma untuk multicast terpercaya over IP multicast bekerja untuk terbuka baik kelompok sebagai tertutup. Diberikan algoritma untuk kelompok tertutup, bagaimana, sederhana, kita bisa berasal algoritma untuk kelompok terbuka? halaman 64915.14 Jelaskan bagaimana beradaptasi algoritma untuk multicast terpercaya over IP multicast untuk menghilangkan antrian terus-kembali - sehingga menerima pesan yang tidak duplikat dapat disampaikan segera, tetapi tanpa jaminan pemesanan. Petunjuk: Penggunaan set nomor urut untuk mewakili pesan yang telah disampaikan sejauh ini. halaman 64915.15 Pertimbangkan bagaimana untuk mengatasi asumsi praktis kami buat dalam rangka memenuhi validitas dan perjanjian properti untuk protokol multicast handal berbasis IP multicast. Petunjuk: menambahkan sebuah aturan untuk menghapus pesan yang dipertahankan ketika mereka telah disampaikan di mana-mana, dan mempertimbangkan menambahkan pesan boneka 'detak jantung', yang tidak pernah dikirim ke aplikasi, tetapi protokol mengirimkan jika aplikasi tidak memiliki pesan untuk mengirim. halaman 64915.16 Tunjukkan bahwa algoritma multicast FIFO-memerintahkan tidak bekerja untuk tumpang tindih kelompok,dengan mempertimbangkan dua pesan yang dikirim dari sumber yang sama untuk dua kelompok yang tumpang tindih, danmempertimbangkan proses di persimpangan kelompok-kelompok. Beradaptasi protokol bekerja untukkasus ini. Petunjuk: proses harus mencakup dengan pesan mereka urutan terbarujumlah pesan yang dikirim ke semua kelompok. halaman 654LATIHAN 67315,17 Tunjukkan bahwa, jika multicast dasar yang kami gunakan dalam algoritma dari Gambar 15.13 jugaFIFO-memerintahkan, maka resultan benar-memerintahkan multicast juga kausal memerintahkan. Apakah itukasus bahwa setiap multicast yang baik FIFO-memerintahkan dan benar-benar memerintahkan adalah demikiankausal memerintahkan? halaman 65515,18 Sarankan bagaimana beradaptasi protokol multicast kausal memerintahkan untuk menangani tumpang tindihkelompok. halaman 65715.19 Dalam membahas algoritma pengecualian saling Maekawa, kami mencontohkan tigahimpunan bagian dari satu set tiga proses yang dapat menyebabkan kebuntuan. Gunakan subset ini sebagaikelompok multicast untuk menunjukkan bagaimana total pemesanan berpasangan belum tentu asiklik.halaman 65815.20 Membangun solusi untuk diandalkan, multicast benar-benar memerintahkan dalam sistem sinkron, menggunakansebuah multicast handal dan solusi untuk masalah konsensus. halaman 65915.21 Kami memberikan solusi untuk konsensus dari solusi untuk diandalkan dan benar-benar memerintahkan multicast,yang melibatkan memilih nilai pertama yang akan disampaikan. Jelaskan dari prinsip pertamamengapa, dalam sistem asynchronous, kita bisa tidak bukan berasal solusi dengan menggunakanhandal tetapi tidak benar-benar memesan Layanan multicast dan fungsi 'mayoritas'. (Catat itu,jika kita bisa, ini akan bertentangan dengan hasil ketidakmungkinan Fischer et al. ! [1985]) Petunjuk:pertimbangkan lambat proses / gagal. halaman 66315.22 Pertimbangkan algoritma yang diberikan pada Gambar 15,17 konsensus dalam sistem sinkron,yang menggunakan definisi integritas berikut: jika semua proses, apakah benar atau tidak,mengusulkan nilai yang sama, maka setiap proses yang benar di negara memutuskan akan memilih yangnilai. Sekarang pertimbangkan sebuah aplikasi di mana proses yang benar dapat mengusulkan berbedahasil, misalnya, dengan menjalankan algoritma yang berbeda untuk menentukan tindakan untuk mengambil dalam kontroloperasi sistem. Menyarankan modifikasi yang sesuai dengan definisi integritas dandemikian algoritma. halaman 66415.23 Tunjukkan bahwa kesepakatan Bizantium dapat dihubungi untuk tiga jenderal, dengan salah satu dari merekarusak, jika para jenderal digital menandatangani pesan mereka. halaman 665 .