Mesaj Sıralaması ve Çoklu Yayın (Multicast)
Grup iletişimi, belirli bir güvenilirlik ve sıralama garantileriyle (FIFO'dan nedensel sıraya ve toplam sıraya kadar) bir mesajı bir dizi sürece iletmektedir.
Tanım
Çoklu yayın (multicast), bir süreç grubunun her üyesine tek bir mesajı iletmektedir; sıralama garantileri, mesajların göreceli teslimat sırasını kısıtlamaktadır. FIFO, gönderici başına sırayı korurken, nedensel sıralama 'önce-gerçekleşen' (happened-before) sırasını korumakta ve toplam sıralama ise tüm mesajları her üyeye aynı sırada teslim etmektedir.
Kapsam
Bu konu, güvenilir çoklu yayını (multicast) ve teslimat sıralamalarının hiyerarşisini (FIFO, nedensel ve toplam (atomik)) ele almaktadır. Ayrıca, bu sıralamaların sıra numaraları, mantıksal saatler ve sıralayıcı veya belirteç (token) şemaları kullanılarak nasıl uygulandığı ve sıralı çoklu yayını tutarlı grup üyeliği değişiklikleriyle bütünleştiren sanal eşzamanlılık (virtual-synchrony) modeli incelenmektedir. Toplam sıralı (atomik) yayın, uzlaşma (consensus) ile güç açısından eşdeğer olduğu gösterilmektedir.
Temel sorular
- Bir uygulama, grup iletişiminden hangi güvenilirlik ve sıralama garantilerini talep etmektedir?
- Nedensel ve toplam teslimat sıralamaları verimli bir şekilde nasıl uygulanmaktadır?
- Toplam sıralı yayın neden uzlaşma (consensus) ile eşdeğerdir?
Temel kuramlar
- Sıralama hiyerarşisi
- Teslimat sıralamaları bir hiyerarşi oluşturmaktadır: FIFO, nedensel sıralamadan daha zayıf olup, nedensel sıralama da toplam sıralamadan daha zayıftır. Her biri, gönderici başına sıra numaraları, vektör zaman damgaları veya küresel olarak üzerinde anlaşılmış bir sıra gibi ek meta verilerle sağlanmaktadır.
- Sanal eşzamanlılık (Virtual synchrony)
- Sanal eşzamanlılık, grup üyeliği değişikliklerini ve çoklu yayın mesajlarını tüm üyelere tutarlı bir sırada sunarak, süreçlerin aynı olay dizisini ve görünüm değişikliklerini görmesini sağlamakta ve böylece replike hizmetlerin oluşturulmasını basitleştirmektedir.
- Atomik yayın uzlaşmaya eşittir
- Toplam sıralı (atomik) yayın ve uzlaşma (consensus) birbirine indirgenebilir; bu nedenle, birine yönelik herhangi bir çözüm diğerine de bir çözüm sağlamakta ve her ikisi de asenkronluk ve arızalar altında aynı çözülebilirlik sınırlarını paylaşmaktadır.
Klinik önem
Sıralı, güvenilir çoklu yayın, durum makinesi replikasyonu (state-machine replication), yayın-abone sistemleri (publish-subscribe systems) ve replike veritabanlarının temelini oluşturmaktadır; bu sistemlerde her bir kopya (replica), tutarlılığı sürdürmek için aynı güncellemeleri aynı sırada uygulamak zorundadır.
Tarihçe
Birman ve Joseph, 1980'lerde ISIS sistemi aracılığıyla sanal eşzamanlılığı (virtual synchrony) ve sıralı çoklu yayını tanıtmışlardır; atomik yayın (atomic broadcast) ile uzlaşma (consensus) arasındaki ilişki 1990'larda açıklığa kavuşturulmuş ve Defago, Schiper ve Urban'ın 2004 tarihli araştırması, birçok toplam sıralı algoritmayı sistematize etmiştir.
Öne çıkan isimler
- Kenneth Birman
- Thomas Joseph
- Andre Schiper
- Leslie Lamport
İlgili konular
Temel eserler
- birman1987
- defago2004
- lamport1978
Sıkça sorulan sorular
- Nedensel sıralama ile toplam sıralama arasındaki fark nedir?
- Nedensel sıralama yalnızca nedensel olarak ilişkili mesajları kısıtlamakta, eşzamanlı mesajların farklı süreçlerde farklı sıralarda teslim edilmesine izin vermektedir. Toplam sıralama ise her sürecin tüm mesajları aynı sırada teslim etmesini gerektirmekte olup, bu durum kesinlikle daha güçlüdür ve uzlaşma kadar zordur.