Çiftçilerin yemeği ne kadar karmaşık?
Yazar Wang Zhuo
Baş Editör | Zhong Peiyi
Bu makale, Kodlayıcı Devir (ID: kodlama) yetkisiyle çoğaltılmıştır.
Da Pang Zhang'ın departmanı arka arkaya üç ay fazla mesai yaptı ve sistem nihayet çevrimiçiydi!
Yönetici, herkesi tedavi etmek için bir bölüm yemeği düzenlemeyi planlıyor. Hangi restorana gideceğimi tartışmak için herkese bırakıyorum.
Beklenmedik bir şekilde, bu grup insan tartışıyor ve kimse kim olduğunu söyleyemez. Aralarında tartışma, en şiddetli Zhang Dafang ve Liu Shouzi, Zhang Dafang güveç yemek istiyor, Liu Shouzi barbekü yemek istiyor ve diğerleri Üç çalışan beceriksiz ve kimin dinlediğini bilmiyor.
Yönetici bu yakıt verimli olmayan lamba grubunu görünce birden bir yol düşündü ve şöyle dedi: "Ses çıkarma! Hepimiz program yazıyoruz, bu sorunu çözmek için bir algoritma kullanalım."
Herkes algoritmayı duyduğunda, hemen ilgilenmeye başladılar: "Hangi algoritma?"
"Bu ünlü Paxos. Biraz karmaşık. Herkes sadece öğrenmek istiyor. Bu sefer yemeğe çıkıyoruz, ancak Zhang Dafang ve Liu Shouzi'nin farklı fikirleri var. Hala bir tane seçmemiz gerekiyor. Bu bir fikir birliği. Bu fikir birliği. İnsanların yarısından fazlası aynı fikirde olduğu sürece. "
"Başlamadan önce birkaç gereksinimden bahsedeyim. Amacımız birlikte yemek. Yani Zhang Dafang, Xiao A'ya güveç yemesini, Xiao B'ye barbekü yemesini ve Xiao C'ye yemek yemesini söyleyemezsiniz. Böyle yaparsan seni maaşla cezalandırırım! "
Zhang Da Pang bir gülümsemeyle hemfikirdi.
"Ve sen, Shou Liu, Xiao A, Xiao B veya Xiao C, Zhang Dafang'ın fikrine zaten katılıyorsa, karalama yapmayın, fikriniz konusunda ısrar etmeyi bırakın, sadece gidin ve yiyin."
Liu Shouzi de başını salladı.
"Son olarak, Küçük A, Küçük B ve Küçük C, siz üçünüz. Bir kişinin teklifine katılıyorsanız, ileri geri dönmeyin. Hangi restoranı yemek istediğinize karar verirseniz, değiştirmeyin!"
Beşi Zhang Dafang, yöneticinin bu gereksinimleri söylediğini duydu ve sessizce hatırladı.
Yönetici şöyle devam etti: "Spesifik algoritma zor değil. İki aşama var:
1. Kendiniz için inceleme aşaması Bu aşamanın amacı "konuşma hakkı" için rekabet etmektir. Ancak çoğu insan sizin "konuşmanızı" dinlemeyi kabul ettiğinde bir sonraki aşamaya geçebilirsiniz;
2. Onay aşaması: Hangi restoranı yiyeceğinizi belirleyin.
Yönetici konuşurken algoritmanın belirli adımlarını açıkladı Zhang Dafaang ve Liu Shouzi ona baktı, çok basitti! Oynamaya başlamak için sabırsızlanıyorum.
Yönetici gizlice gülümsedi: Basit! Humph! Oynadıktan sonra ikinizin de atması yeterli olacak!
İlk oyun
İnceleme aşaması
Big Fat Zhang daha akıllı. Küçük A, Küçük B ve Küçük C'nin dağınık saçlarını ve standart ekose gömleği görünce henüz kız arkadaşı olmadığını biliyor.
Bu üç kişinin onları dinlemesi için Zhang Dapang bir fikir ortaya attı: Teklifimi dinleyin, her birinize bir kızla tanıştıracağım!
Küçük A ve Küçük B bunu duyduklarında çok mutlular.Büyük Kardeş Zhang tek sorunu çözer ve Büyük Kardeş Zhang'ı dinler!
Aynı zamanda ikisi not defterine yazdı: bir kızı tanıtın, otel teklifini kabul edebilirim!
Zhang Da çok mutlu. 3 kişinin desteğini çok kolay kazandım. Küçük A ve Küçük B artı ben (kendime karşı bölünmüş bir kişiliğim yok) zaten çoğunlukta. Little C kabul etsin ya da etmesin, ben varım Bir söz söyleyin.
Oteli belirle
Zhang Dafang, Küçük A ve Küçük B'ye, güveç yemesi için bir kızı tanıtacağımı söyledi!
Hem Küçük A hem de Küçük B aynı fikirdedir ve not defterine yazın: Bir kızı güveç yemeye tanıtın.
Sonuçları aldıktan sonra Zhang Dapang, Paxos algoritmasının uygulandığını biliyordu ve mutlu bir şekilde şunu duyurdu: "Tamam, bir fikir birliğine vardık ve güveç yemeye gidebiliriz!"
İkinci oyun
Liu Shouzi şaşkına döndü: "Zhang Dafaang, çok hızlı başladınız. Bunu böyle yaparsınız, bu hiç de anlamsız. Hayır, tekrar oynayalım!"
Zhang Dafang, "Sorun değil, hala başaramayacağından korkuyorum?" Dedi.
Bununla birlikte, aceleyle Küçük A, Küçük B ve Küçük C ile temasa geçti: Size beni destekleyecek bir kızla tanıştırmak istiyorum.
Küçük A ve Küçük B aynı fikirdedir ve not defterlerine yazın: bir kızı tanıtın, otel teklifini kabul edebilirim!
Sonuç olarak, Küçük C dedi, Zhang Dafaang, sen gerçek değilsin, Liu Shouzi bana iki kızı tanıtmamı söyledi!
Xiao C'nin Liu Shouzi'nin sözlerini çoktan dinlediği ortaya çıktı, bu yüzden kitap şunu hatırladı: iki kızı tanıtın, otel teklifini kabul edebilirim!
Zhang Da Pangxin, bu zayıf Liu'nun aptal olmadığını ve insanları bu şekilde nasıl kazanacağını bildiğini söyledi.
Ama Küçük A ve Küçük B onlara söz verdiğinden beri, Zhang Dapang çoğunluğun rızasına sahip olduğunu biliyordu!
Acele edin ve onlara nerede yemek yiyeceklerini söyleyin, bu birkaç duvarın kaçmasına izin vermeyin! Sonra kızın iletişim bilgilerini bulmak için küçük bir şarkı mırıldanıyor.
İletişim bilgilerini bulduktan sonra, Zhang Dapang, otel anlaşmazlığını tamamen sona erdirmeye hazır olarak ikinci aşamaya girdi.
Xiao A, güveç teklifini başarıyla kabul etti ve kaydetti: güveç yemesi için bir kızı tanıttı.
Beklemediğim şey, Küçük B'nin çoktan geri dönmüş olmasıydı: Zhang Dafang, sen gerçek değilsin, Liu Shouzi bana iki kızı tanıtmamı söyledi!
Zhang Dafang, kendi kendine bunun gerçekten beceriksiz olduğunu düşündü ve kan araştırmasının ilk aşamasının yeniden başlaması gerektiği görüldü.
Bahisleri artırın! Her birini üç kızla tanıştırın! Yeterince emin, Xiao A ve Xiao B tekrar suya karşı döndüler ve neşeyle kendilerini desteklediler.
Aynı zamanda Liu Shouzi mutlu bir şekilde "iki kızı tanıtarak" çoğunluğun desteğini kazandığını ve restoranı belirlemek için ikinci aşamaya girebileceğini düşündü.
Ama Xiao B ile temasa geçtiğinde, üzücü bir şekilde Zhang Dafang'ın pazarlık kozunu (3 kız) yükseltmiş olduğunu gördü. Küçük B'yi tekrar uzaklaştırıyorum!
Liu Shouzi aceleyle adres defterini aradı, daha fazla iletişim bilgisi bulmak için hazırlandı ve onları 4 kızla tanıştırdı.
Zhang Da Pang boşta değildi ve hemen ikinci aşamaya girdi ve oteli başarıyla tanımladı.
Bu noktada Zhang Dafang'ın Paxos algoritması uygulandı ve çoğu insanın güveç yemeyi kabul ettiğini biliyor.
Liu Shouzi, avantajı yeniden kazanmaya çalışarak bir kez daha kan araştırması başlattı, ancak Xiao A ve Xiao B'nin güveç yeme teklifini kabul ettiğini gördü.
"Liu Shouzi, size gerçekten söz vermek istiyoruz, ancak güveç yeme önerisini çoktan kabul ettik ve değiştiremeyiz. Ancak, size saygı göstermek için gelecekte bize güveç vermemiz gerektiğini belirleyeceğiz. 4 kız. "
Liu Shouzi, yöneticinin önceki kuralını düşündü: "Birisi restoranın teklifini kabul ederse, artık yazamaz, sadece gidip yemek yiyin!"
İçini çekti ve ikinci aşamaya girdi, restoranı doğruladı, ama emin olduğu şey aynı zamanda "güveç yemek" idi.
Liu Shouzi'nin Paxos algoritması da uygulandı ve sonunda güveç yemek için bir anlaşmaya vardı.
sonuç olarak
Bu Temel Paxos algoritmasını anlarsanız çok basit bulacağınızı ancak aklınızdan geçenleri tarif etmenin zor olduğunu buldum, çünkü her katılımcının durumu sürekli değişiyor ve çok fazla detay var. Çok fazla dal.
Bu yüzden bu küçük oyun aracılığıyla Temel Paxos algoritmasını açıkladım.Dürüst olmak gerekirse, çok katı değil.Örneğin, Little A, Little B ve Little C için daha fazla "rüşvetle" Kabul Et mesajını alırsanız, restoran belirlenmiş olsa bile, yine de değiştirebilirsiniz. Evet, oyunda bundan bahsedilmiyor.
Bu oyun, yürütme sırasında karşılaşılan tipik durumları gösterir. Algoritmanın tamamı için makalenin son bölümüne bakın.
Temel Paxos algoritmasında iki rol en önemlidir:
- Teklif veren: Yani Zhang Dafang ve Liu Shouzi
- Akseptör: Little A, Little B, Little C, Zhang Dafang ve Liu Shouzi dahil
Bir kişi birden fazla rol oynayabilir.
Oyuna "n sayıda kızın tanıtımı", Paxos algoritmasında sadece bir sayıdır.
Basic Paxos'un iki aşamalı protokolünde, Teklif Sahibi ilk aşamada "konuşma hakkı" almaya çalışarak diğerlerine Hazırlık (n) gönderir. Buradaki hazırlık (n), "n kızı tanıtmak" ile eşdeğerdir.
İkinci aşamada, sonucu belirlemeye çalışmak için Kabul Et (n, v) gönderilir, burada n hala "n kızı tanıtıyor" ve v ise güveç veya mangal yiyor.
Çünkü Prepare (n) gönderebilen birden fazla Teklif Sahibi var. Şu anda, Acceptor'ın n'nin boyutuna göre kimin dinlediğini belirlemesi gerekir. Böylece küçük B gibi ileri geri sallanan duvar çimenleri olacak.
Teklif Veren, ilk aşamada insanların çoğunluğu tarafından desteklendikten sonra, ikinci aşamaya girecek ve diğerlerine bir Kabul (n, v) mesajı gönderecektir.
Little B gibi belirli bir Alıcı, Zhang Dafangın Kabulünü (3, güveç) aldı ve güveç yemeğini kaydetti. Şu anda, alınan mesaj Hazırla (4) olsa bile, daha büyük bir sayı çalışmayacaktır. Liu Shouzi'ye güveç seçmeye karar verdiğimi söyledi.
Şu anda kilit nokta, Liu Shouzi'nin kendi mangalında ısrar etmek yerine takip etmesi gerektiğidir.
İlginç bir soru
Akıllı, muhtemelen zaten görmüşsünüzdür: Zhang Dafang ve Liu Shouzi dönüşümlü olarak konuşma hakkı için rekabet ederse, örneğin:
Zhang Dapang bir kızı tanıttı ve küçük bir A ve küçük bir B kazandı
Liu Shouzi 2 kızı tanıttı ve Little B ve Little C için kazandı
Zhang Dapang, 3 kızı tanıttı ve Küçük A ve Küçük B için kazandı
Liu Shouzi 4 kızı tanıttı ve küçük bir B ve küçük bir C kazandı.
...
Bu şekilde kimse ikinci aşamaya giremez ve algoritma hiçbir zaman tamamlanamayacaktır.
Çözümlerden biri, yeni bir dövüş turuna başladıklarında rastgele bir süre beklemelerine izin vermektir. Başkalarına bu algoritmayı tamamlama şansı verin.
algoritma
Ayrıntılı bir algoritma yayınlayın ve ilgilenenler onu dikkatlice inceleyebilirler.
Algoritma şu kaynaktan gelir: https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx
Yazar: Wang Zhuo, Pekin Posta Üniversitesi'nden Master ve blok zinciri teknolojisi için araştırma yönetimi, fikir birliği algoritmaları ve sıfır bilgi kanıtı, temel teknoloji blok zincirinin daha derin bir şekilde anlaşılması.
Sorumluluk Reddi: Bu makale, Code Farmer'dan çoğaltılmaya yetkilidir, yeniden yazdırmanız gerekirse, lütfen orijinal yazarla iletişime geçin.
SON
