Detta arbete presenterar en klassificering av svaga modeller av distribuerade datorer. Vi fokuserar på deterministiska distribuerade algoritmer, och vi studerar modeller av datorer som är svagare versioner av den brett studerade portnumrering modellen. I portnumreringsmodellen, tar en nod av grad d emot meddelanden genom d ingångsportar och det skickar meddelanden genom d utgångsportar, båda numrerade med 1, 2,....... d. I detta arbete, VVc är klassen av alla grafproblem som kan lösas i standardportnumreringsmodellen. Vi studerar följande underklasser av VVc: VV: Input port i och output port i är inte nödvändigtvis anslutna till samma granne. MV: Inmatningsportar är inte numrerade; algoritmer får en multiuppsättning meddelanden. SV: Inmatningsportar är inte numrerade; algoritmer får en uppsättning meddelanden. VB: Utmatningsportar är inte numrerade; algoritmer skickar samma meddelande till alla utmatningsportar. MB: Kombination av MV och VB. SB: Kombination av SV och VB. Nu har vi många triviala inneslutning förbindelser, såsom SB  på MB  och VB VV  på VVc, men det är inte uppenbart om t.ex., endera av VB på SV eller SV på VB bör hålla. Ändå visar det sig att vi kan identifiera en linjär ordning på dessa klasser. Vi bevisar att SB MB = VB SV = MV = VV VVc. Samma sak gäller för de konstanta tidsversionerna av dessa klasser. Vi visar också att de konstanta varianterna av dessa klasser kan karakteriseras av en motsvarande modal logik. Därför har den linjära ordning som identifieras i detta arbete direkta konsekvenser i undersökningen av uttryckligheten hos modallogiken. Omvänt kan vi använda verktyg från modal logik för att studera dessa klasser.
Det är värt att notera att olika versioner av portnumrerade nätverk kännetecknas i REF genom att koppla dem till modal logik.
Weak models of distributed computing, with connections to modal logic
{'venue': "PODC '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}