Задача двох генералів

Задача двох генералів (задача двох армій, проблема скоординованої атаки) — в обчислювальній техніці уявний експеримент, що ілюструє проблему синхронізації стану двох систем по ненадійному каналу зв'язку. Ця задача подібна на більш загальну задачу візантійських генералів, хоча і була сформульована пізніше за неї. Задача часто згадується на початку курсу комп'ютерних мереж (зокрема при розгляді протоколу TCP). Назву для цієї задачі придумав Джим Грей.

Визначення

Посильні між арміями A1 та A2 можуть бути перехоплені ворогом B.

Дві армії, кожна під проводом свого генерала, готуються до штурму міста. Табори армій розділені ворожою територією. Єдиним засобом зв'язку для генералів є відправка посильних через ворожу територію, де вони можуть бути перехоплені.

Для успішного штурму генерали повинні атакувати місто одночасно. Атака однією армією приречена на поразку. Потрібно розробити алгоритм обміну повідомленнями, що дозволяє кожному генералу бути впевненому в узгодженні часу атаки.

Ілюстрація проблеми

Перший генерал, відправивши повідомлення з часом атаки другому генералу, не може бути впевненим, що той його отримав, а ж поки не отримає від нього повідомлення у відповідь.

В свою чергу, другий генерал отримавши повідомлення з часом атаки і пославши повідомлення з підтвердженням, не може бути впевненим, що перший генерал отримає його підтвердження. Йому теж необхідне підтвердження доставки свого повідомлення.

Таким чином задача не має розв'язку.

Доведення від супротивного

Припустимо, що існує деяка мінімальна послідовність доставлених чи перехоплених повідомлень, що гарантує обом генералам впевненість в узгодженні часу штурму. Розглянемо останнє повідомлення цієї послідовності. Воно теж може бути перехоплене. В такому випадку його отримувач не буде мати підтвердження і може не розпочати атаку. В іншого ж генерала є впевненість в узгодженості дій, тому він розпочне атаку. Тобто, при існуванні алгоритму узгодження можлива ситуація поразки, що суперечить припущенню про існування алгоритму.

Інженерний підхід

Прагматичний підхід до розв'язку задачі не бореться з усуненням ненадійності каналу зв'язку, а зводить його до допустимого рівня.

Наприклад:

  • зважаючи на те, що імовірність перехоплення низька, перший генерал відправляє 100 посильних і атакує, другий генерал атакує, якщо він отримує хоча б одного посильного.

Посилання

Read other articles:

Follie d'invernoPoster del filmTitolo originaleSwing Time Lingua originaleinglese Paese di produzioneStati Uniti d'America Anno1936 Durata105 min Dati tecniciB/Nrapporto: 1,37:1 Generecommedia, musicale RegiaGeorge Stevens SoggettoErwin Gelsey SceneggiaturaHoward Lindsay, Allan Scott ProduttorePandro S. Berman (non accreditato) Casa di produzioneRKO Radio Pictures Distribuzione in italianoRKO (1938) FotografiaDavid Abel MontaggioHenry Berman Effetti specialiVernon L. Walker MusicheJerome ...

 

  لمعانٍ أخرى، طالع هارلي (توضيح). هارلي   الإحداثيات 41°55′27″N 74°03′42″W / 41.9242°N 74.0617°W / 41.9242; -74.0617  [1] تقسيم إداري  البلد الولايات المتحدة[2][3]  التقسيم الأعلى مقاطعة أولستر  خصائص جغرافية  المساحة 35.97 ميل مربع  عدد السكان  عدد ا�...

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Pope Innocent XII – news · newspapers · books · scholar · JSTOR (February 2019) (Learn how and when to remo...

Gedung Merdeka saat berlangsungnya Konferensi Asia Afrika Video luarArsip Konferensi Asia-Afrika di Bandung Konfrensi Asia Afrika oleh Humas Arsip Nasional RI. Konferensi Tingkat Tinggi Asia-Afrika (disingkat KTT Asia Afrika atau KAA; kadang juga disebut Konferensi Bandung) adalah sebuah konferensi antara negara-negara Asia dan Afrika, yang kebanyakan baru saja memperoleh kemerdekaan. KAA diselenggarakan oleh Indonesia, Myanmar (dahulu Burma), Sri Lanka (dahulu Ceylon), India dan Pakistan dan...

 

Kars province Kars iliProvince of TurkeyLocation of Kars Province in TurkeyCountryTurkeyRegionEastern AnatoliaLuas • Total9,587 km2 (3,702 sq mi)Populasi (2010-12-31)[1] • Total301.766 • Kepadatan31,000/km2 (82,000/sq mi)Kode area telepon0474Pelat kendaraan36Situs webkars.gov.tr Kars (Turki: Kars ili) adalah sebuah provinsi Turki. Galeri Kars city center Ruins of Ani Atatürk monument in Sarıkamış A ruined bridge in A...

 

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Princess Dorothea of Courland – news · newspapers · books · scholar · JSTOR (November 2012) (Learn how and when to remove this message) Duchess of Dino, Duchess of Talleyrand, Duchess of Sagan Princess DorotheaDuchess of Dino, Duchess of Talleyrand, Duchess of ...

 

Daniel Briere is the Flyers current general manager. The Philadelphia Flyers are a professional ice hockey team based in Philadelphia, Pennsylvania. They are members of the Metropolitan Division of the National Hockey League's (NHL) Eastern Conference.[1] The Flyers were founded in 1967 as one of six expansion teams, increasing the size of the NHL at that time to twelve teams.[2] Since the franchise was established, the team has had ten general managers,[3] including ...

 

World War II Victory Medal World War II Victory Medal Dianugerahkan oleh Department of the ArmyDepartment of the Navy Jenis Medal Persyaratan penerima served in the armed forces between the following dates: antara 7 Desember 1941 dan 31 Desember 1946, untuk jasa militer apapun. Status Dipensiunkan Statistik Anugerah pertama 7 Desember 1941 Anugerah terakhir 31 Desember 1946 Tingkatan Lebih tinggi European-African-Middle Eastern Campaign Medal Lebih rendah Army of Occupation Medal o...

City of Udham Singh Nagar district in the Indian state of Uttarakhand City in Uttarakhand, IndiaKashipurCityMaharana Pratap Chowk, Main crossroad of KashipurKashipurLocation within India and UttarakhandShow map of UttarakhandKashipurKashipur (India)Show map of IndiaCoordinates: 29°13′N 78°57′E / 29.22°N 78.95°E / 29.22; 78.95Country IndiaStateUttarakhandDistrictUdham Singh NagarFounded1639[1]Municipality1872Founded byKashinath Adhikari, an officer ...

 

Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) Suburb of Brisbane, Queensland, AustraliaWindsorBrisbane, QueenslandWindsor Shire Council Chambers, later Windsor Town Council ChambersWindsorCoordinates27°26′07″S 153°01′45″E / 27.4352°S 153.0291°E / -27.4352; 153.0291 (Windsor (centre of suburb))Population7,811 (2021 census)[1] •...

 

PS Shark TanjungpinangNama lengkapPerkumpulan Sepakbola Shark TanjungpinangJulukanThe Blue SharksBerdiri2013; 11 tahun lalu (2013)StadionStadion Antam KijangKota Tanjungpinang, Kepulauan Riau(Kapasitas: 5.000)PemilikAde Noverwin[1]ManajerZulkarnain[2]LigaLiga 3 Kepulauan Riau2023Babak grup Kostum kandang Kostum tandang Perkumpulan Sepakbola Shark (atau dikenal juga PS Shark Tanjungpinang) adalah klub sepak bola Indonesia yang bermarkas di Stadion Antam Kijang, Kota Tanjun...

梅拉蒂·达伊瓦·奥克塔维亚尼Melati Daeva Oktavianti基本資料代表國家/地區 印度尼西亞出生 (1994-10-28) 1994年10月28日(29歲)[1] 印度尼西亞万丹省西冷[1]身高1.68米(5英尺6英寸)[1]握拍右手[1]主項:女子雙打、混合雙打職業戰績48勝–27負(女雙)109勝–56負(混雙)最高世界排名第4位(混雙-普拉文·喬丹)(2020年3月17日[2])現時世界排名第...

 

Lempira Departamento Localización del departamento de LempiraCoordenadas 14°35′20″N 88°34′53″O / 14.588955555556, -88.581355555556Capital Gracias • Población 57 182 habitantesEntidad Departamento • País  HondurasGobernador José Enamorado(2022-2026)Subdivisiones 28 municipiosEventos históricos   • Fundación 1825Superficie Puesto 11.º de 18 • Total 4,228 km²Clima Tropical seco AwTemplado subhúmedo CwbPoblación (...

 

Prima CategoriaSport Calcio TipoCampionato CategoriaOdierna Serie A[1] FederazioneFIGC Paese Italia ContinenteEuropa OrganizzatoreFIGCcon delega ai Comitati Regionali per la fase eliminatoria dal 1912 CadenzaAnnuale AperturaAutunno ChiusuraPrimavera PartecipantiDa 5 a 72 FormulaGironi Regionali + Finali Nazionali StoriaFondazione1904 Soppressione1922 Coppa FawcusCoppa SpensleyCoppa BuniCoppa ObertiTrofeo o riconoscimento Modifica dati su Wikidata · Manuale La Prima Categori...

Women's rugby union team representing the island of Ireland For the men's team, see Ireland national rugby union team. For the women's sevens team, see Ireland women's national rugby sevens team. IrelandEmblemShamrockUnionIrish Rugby Football UnionHead coachScott BemandCaptainSam MonaghanHome stadiumDonnybrook Stadium First colours Second colours World Rugby rankingCurrent10 (as of 4 September 2023)Highest2 (11 August 2014)First international Scotland 10–0 Ireland  (Edinburgh, Sco...

 

Joseph Louis Proust, pencetus hukum perbandingan tetap Dalam kimia, hukum perbandingan tetap atau hukum Proust (diambil dari nama kimiawan Prancis Joseph Proust) adalah hukum yang menyatakan bahwa suatu senyawa kimia terdiri dari unsur-unsur dengan perbandingan massa yang selalu tepat sama.[1] Dengan kata lain, setiap sampel suatu senyawa memiliki komposisi unsur-unsur yang tetap. Misalnya, air terdiri dari 8/9 massa oksigen dan 1/9 massa hidrogen. Bersama dengan hukum perbandingan be...

 

Plant considered undesirable in a particular place or situation This article is about plants specifically called weeds. For the psychoactive plant commonly called weed, see Cannabis (drug). For other uses, see Weed (disambiguation). Weeds growing in the cracks of a concrete staircase (Epilobium roseum, Chelidonium majus, Oxalis corniculata, Plantago major) A weed is a plant considered undesirable in a particular situation, growing where it conflicts with human preferences, needs, or goals. ...

MS Independence of the Seas adalah kapal pesiar kelas Freedom dioperasikan oleh Royal Caribbean cruise line yang mulai beroperasi pada April 2008. Kapal 15-dek dapat menampung 4.370 penumpang dan dilayani oleh 1.360 awak. Kapal ini dibangun di galangan kapal Aker Finnyards Turku, Finlandia, builder dari Freedom of the Seas dan Liberty of the Seas, kapal adiknya dari kelas Freedom. Pada 154.407 gross ton, ia bergabung Freedom of the Seas dan Liberty of the Seas sebagai kapal pesiar terbesar d...

 

Ini adalah nama Batak Toba, marganya adalah Butarbutar. Gita BhebhitaLahirGita Anggita Butar Butar[1]5 Maret 1987 (umur 37)Riau, IndonesiaNama lainGita BhebhitaAlmamaterUniversitas Sumatera UtaraPekerjaanPelawak tunggalpresenterpenyiar radioaktrisTahun aktif2014—sekarang Gita Anggita Butar Butar (lahir 5 Maret 1987), dikenal dengan nama Gita Bhebhita adalah seorang pelawak tunggal, presenter, penyiar radio, dan aktris berkebangsaan Indonesia. Gita adalah salah satu ko...