Abstrakt. Att datorprotokollen fungerar korrekt är nödvändigt för att de distribuerade systemen ska fungera smidigt, vilket underlättar vår globala ekonomi. Formella tekniker ger vår bästa chans att se till att protokollkonstruktioner är fria från fel. Detta inbjudna dokument återbesöker klassen av Stopp-och-Vänta protokoll som innehåller retransmissionsstrategier för att återhämta sig från överföringsfel. Detta motiveras av att deras grundläggande mekanismer är viktiga för praktiska protokoll såsom TCP (Internet's Transmission Control Protocol). Stopp-och-vänta protokoll har visat sig fungera korrekt över media som kan förlora paket, men det har varit lite diskussion om hur dessa protokoll fungerar över media som kan beställa paket. I dokumentet presenteras en undersökning av dessa protokoll som fungerar via ett medium, t.ex. det som tillhandahålls genom Internetprotokollet, som gör det möjligt att omordna uppgifter. Färgade Petri Nets används för att bygga en modell av ett stopp-och-vänt protokoll parameteriserat av dess maximala sekvensnummer och det maximala värdet av retransmissionsräknaren. Modellen analyseras med hjälp av en kombination av handproof och automatiska tekniker. Vi identifierar fyra problem. Vi bevisar först och främst den intuitiva egenskapen hos räknaren för ett Stopp-och Vänta-protokoll att antalet paket som lagras i nätverket kan växa utan bindning. Detta gäller för eventuella positiva värden av det maximala sekvensnumret och det maximala antalet vidaresändningar. Vi visar vidare att förlust av paket är möjlig och att dubbletter kan accepteras som nya paket av mottagaren. Dessa tre första egenskaper håller trots att avsändaren och mottagaren uppfattar att protokollet fungerar korrekt. Det sista problemet är att protokollet inte uppfyller Stopp-och-Vänta tjänsten där skickar och tar emot alternativ. Slutligen ger vi en diskussion om hur relevanta dessa resultat är för protokollet om överföringskontroll.
Färgade petri nettomodeller används i REF för modellering av stopp-och-vänta protokoll.
How Stop and Wait Protocols Can Fail over the Internet
{'venue': 'FORTE', 'journal': None, 'mag_field_of_study': ['Computer Science']}