Kahden kenraalin ongelma () on tietojenkäsittelytieteen klassinen ajatuskoe, joka havainnollistaa hajautettujen järjestelmien välisen luotettavan kommunikaation mahdottomuutta epäluotettavassa verkossa. Ongelma tunnetaan myös nimellä koordinoidun hyökkäyksen ongelma ().

Ongelman kuvaus Ajatuskokeessa kaksi armeijaa ja niiden kenraalit sijaitsevat laakson vastakkaisilla puolilla. Laakson keskellä on vahvasti linnoitettu linna. Kenraalit tietävät, että ainoa tapa valloittaa linna on hyökätä täsmälleen samaan aikaan, sillä yksittäinen armeija ei pysty voittamaan taistelua yksin.

Kenraalit voivat kommunikoida keskenään vain lähettämällä viestinviejiä vaarallisen laakson läpi. Viestinviejät saattavat joutua vihollisen väijytykseen, jolloin viesti ei koskaan saavu perille. Ongelman ydin on: miten kenraalit voivat varmistua siitä, että molemmat hyökkäävät samaan aikaan?

Ongelman ratkaisu Ongelman on matemaattisesti todistettu olevan mahdoton ratkaista täydellisesti. Vaikka ensimmäinen kenraali (A) lähettäisi viestin ehdotetusta hyökkäysajasta ja toinen kenraali (B) lähettäisi vahvistuksen, ei kumpikaan voi olla varma viestin perillemenosta. Tämä johtaa päättymättömään vahvistusten ketjuun:

Kenraali A ei tiedä, saapuiko alkuperäinen viesti perille Kenraali B ei tiedä, saapuiko hänen vahvistusviestinsä perille Kenraali A ei tiedä, saapuiko vahvistuksen vahvistus perille Ja niin edelleen

Käytännön sovellukset Vaikka ongelma on teoreettisesti ratkaisematon, käytännön tietotekniikassa on kehitetty useita tapoja lieventää ongelmaa. Yksi tärkeimmistä ratkaisuista on idempotenssiavain, joka on yksilöllinen tunniste jokaiselle pyynnölle. Sen avulla järjestelmä voi tunnistaa ja estää samojen toimintojen suorittamisen useaan kertaan.

Ongelma on erityisen merkittävä verkkokaupoissa ja maksuliikenteessä, missä kaksoisveloitukset tai -tilaukset voivat aiheuttaa merkittäviä ongelmia. Vuonna 2018 Isossa-Britanniassa tapahtui ruoankuljetuspalvelun häiriö, jossa asiakkaat saivat useita identtisiä tilauksia tai eivät saaneet tilauksiaan lainkaan järjestelmän vahvistusviestien epäonnistumisen vuoksi.

Katso myös Verkkoprotokolla

Lähteet

Luokka:Hajautetut järjestelmät Luokka:Ajatuskokeet