Vi anser att problemet med att syntetisera protokoll i en distribuerad miljö uppfyller specifikationer som formuleras i logik linjär tid och kunskap. I allmänhet är syntes i distribuerade inställningar omöjlig att bestämma redan för linjärtid tidslogik specifikationer, men det finns speciella fall där syntes från linjär tid tidslogik specifikationer är känd för att vara decidable. På grundval av dessa resultat och ett resultat av att syntesen av tids- och kunskapsspecifikationer kan fastställas i system med ett enda agens, förmodade van der Meyden och Vardi [CONCUR 96] att syntesen av tids- och kunskapsspecifikationer skulle kunna fastställas i två klasser av miljöer: hierarkiska miljöer, där varje agent i en linjär sekvens observerar minst lika mycket som de föregående agenterna, och sändningsmiljöer, i vilka all kommunikation begränsas till att ske genom synkron sändning. Vi visar att detta antagande är sant när det gäller sändningsmiljöer, men falskt när det gäller till och med en mycket enkel typ av hierarkisk miljö, där endast två agenter är inblandade, av vilka en observerar varje aspekt av systemtillståndet och en av dem inte observerar något av det. Icke desto mindre är syntesen från linjärtidslogiska specifikationer deciderbar i hierarkiska miljöer. För specifikationer som är positiva i kunskapsmetoderna kan dessutom syntesproblemet reduceras till samma problem för logiken i linjär tid. Vi använder dessa fakta för att dra slutsatsen att det går att bestämma i hierarkiska system av en egendom som är nära relaterad till icke-nedbrytbarhet på strategier, ett begrepp som har studerats i datasäkerhet.
Till exempel fastställer REF att problemet är avgjort i radio- och tv-miljöer, där informationsflödet mellan spelare endast sker genom offentliga sändningar.
Synthesis of distributed systems from knowledge-based specifications
{'venue': 'CONCUR, volume 3653 of LNCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}