bysantinska generalsproblemet

i datorvetenskap: utmaningen att få ett it-system att fatta bästa möjliga beslut, som måste verkställas av alla delar av systemet, när det är tänkbart att någon del av systemet lämnar felaktig information eller inte kommunicerar alls. Eller att olika delar av systemet lämnar olika information om samma sak. Problemet formulerades först med tanke på krångel i it‑system. Det bysantinska generalsproblemet är också relevant för så kallade konsensusalgoritmer, alltså algoritmer som fastställer att en viss transaktion eller annan åtgärd är giltig om den godkänns av ett visst antal noder, eller alla, i ett nätverk. – Det bysantiska generalsproblemet har tre delar:

  1. – att få alla delar att medverka till ett välgrundat gemensamt beslut;
  2. – att förhindra att någon del av systemet skickar felaktig eller vilseledande information till andra delar av systemet;
  3. – att hantera eventuell brist på kommunikation (att någon del av systemet inte deltar i arbetet med att lösa problemet).

– Det bysantinska generalsproblemet har namn efter ett scenario där ett antal bysantinska generaler belägrar en stad. De måste komma överens om ifall de ska anfalla staden eller låta bli. Ett anfall kan bli framgångsrikt bara om alla generalerna låter sina arméer anfalla samtidigt (konsensus). Om några generaler anfaller men andra låter bli slutar det med nederlag. Generalerna kan inte träffas, utan skickar budbärare till varandra. Det är nödvändigt att alla generalerna talar om för varandra om de vill anfalla eller avstå. Beslut fattas först när alla har jämfört sina bedömningar med varandra. Man måste ha kommunikation med alla generalerna, och man måste gardera sig mot förräderi: som att någon av generalerna skickar ett besked till några av generalerna och ett annat besked till andra. Man måste också gardera sig mot att budbärarna fifflar med beskeden. – En ingående analys från 1982 av det bysantinska generalsproblemet, författad av Leslie Lamport, Robert Shostak och Marshall Pease, kan laddas ner här. – Kallas också för bysantinska generalerna, på engelska the Byzantine generals problem. – Varför problemet har uppkallats efter just bysantinska generaler är okänt.

  • Byzantine fault – bysantinskt fel – är ett fel som ter sig olika för olika komponenter i ett datorsystem. Det är därför ett problem för systemet att avgöra vad det ska göra åt felet, eller ifall det verkligen är ett fel;
  • Byzantine fault tolerance – bysantinsk feltolerans – system för feltolerans som kan hantera bysantinska fel (se ovan);
  • Byzantine failure – bysantinskt funktionsfel – funktionsfel (det att datorsystemet helt eller delvis slutar att fungera) som orsakas av ett bysantinskt fel.

[datorvetenskap] [fel] [ändrad 9 oktober 2018]

suffixträd

(suffix tree) – systematisk uppställning av alla suffix (betydelse 2) av en teckensträng. Teckensträngen ”ananas”, till exempel, har suffixen ”nanas”, ”anas”, ”nas”, ”as” och ”s”. I ett suffixträd ordnas de på ett sätt som gör det lätt att söka bland dem (det vill säga att datorn kan göra det med så få operationer som möjligt). – Suffixträd har praktisk användning vid sökningar i textmassor, dels i ordbehandling, dels vid sökningar i kemiska formler och i medicinska och biovetenskapliga datamängder. –Läs mer i Wikipedia.

[datorvetenskap] [programmering] [13 juni 2017]

deobfuskering

(deobfuscation) – omvandling av tillkrånglad programkod till pro­gramkod som är lätt att överblicka och förstå. Termen används främst när det gäller programkod som är avsiktligt tillkrånglad, se obfuskering. – En dator­veten­skap­lig artikel om tekniker för deobfuskering finns på denna länk.

[datorvetenskap] [programmering] [26 maj 2017]

entitet

(entity) – i datorvetenskap:

  1. – något som existerar oberoende av sina attribut. Om attributen ändras förblir entiteten ändå densamma, till och med om alla lagrade attribut ändras. Exempel: en människa. Hon kan byta namn, adress, telefonnummer, i ovanliga fall till och med personnummer och kön, men hon är ändå samma människa – samma entitet. När man lägger upp databaser kan det vara viktigt att se till att samma entitet inte kommer med i två exemplar: om någon gifter sig och byter efternamn bör man se till att den personen inte dubbleras. (Se också unik besökare);
  2. – den fysiska person som står bakom en identitet, till exempel ett användarnamn;
  3. – se entity-relationship, där en entitet kan vara i stort sett vad som helst.

Entitet är i grunden en filosofisk term. Det står för vad som helst som vi kan tänka oss, vare sig det är en varelse, ett materiellt föremål, en händ­else eller process, en tanke eller något som existerar i historien, i religion eller i fantasin. Ordet används i olika sammanhang i mer begränsad betyd­else. – Ordet kommer från latinets entitatem – det varande, det som finns, och lär ha myntats av Julius Caesar.

[data] [datorvetenskap] [filosofi] [identitet] [språktips] [ändrad 31 augusti 2020]

Gödelpriset

the Gödel Prize – ett årligt pris för enastående artiklar i ämnet teoretisk datorveten­skap. Det är uppkallat efter logikern Kurt Gödel†. Priset har delats ut sedan 1993. Bakom priset står ACM och European association for theoretical computer science, EATCS (eatcs.org). I priset ingår 5 000 dollar. – Kurt Gödels insats för datorvetenskapen var dels att hans ofullständighetssats inspirerade Alan Turing† till artikeln om Turingmaskinen, dels att han var först med att formulera problemet P=NP?.) – Se denna webbsida.

[datorvetenskap] [utmärkelser] [ändrad 6 juni 2017]