Abstract Distributed restrict tillfredsställelse problem (DisCSPs) består av agenter, var och en håller sina egna variabler, som är kopplade till begränsningar till variabler av andra agenter. På grund av problemets distribuerade karaktär kan meddelandefördröjning ha oväntade effekter på beteendet hos distribuerade sökalgoritmer på DisCSPs. Detta har nyligen visats i experimentella studier av asynkrona backtracking algoritmer (Bejar et al., Artif. Information., 161:117-148, 2005; Silaghi och Faltings, Artif. Information., 161:25-54, 2005). För att utvärdera effekten av meddelandefördröjning på driften av DisCSP-sökalgoritmer presenteras en modell för distribuerade prestandamått. Modellen räknar antalet icke samtidiga begränsningar kontroller, för att komma fram till en lösning, som en icke samtidig mätning av distribuerad beräkning. En enklare version mäter distribuerad beräkningskostnad genom det icke-konkurrenta antalet steg av beräkning. En algoritm för beräkning av dessa distribuerade mått på beräkningsansträngning beskrivs. Förverkligandet av modellen för mätning av prestanda för distribuerade sökalgoritmer är en simulator som inkluderar kostnaden för meddelandeförseningar. Två familjer av distribuerade sökalgoritmer på DisCSPs undersöks. Algoritmer som kör en enda sökprocess, och flera sökprocesser algoritmer. De två algoritmfamiljerna beskrivs och associeras med befintliga algoritmer. Prestandan av tre representativa algoritmer av dessa två familjer mäts på slumpmässigt genererade fall av DisCSPs med försenade meddelanden. Förseningen av meddelanden visar sig ha en stark negativ effekt på enskilda sökprocessalgoritmer, vare sig synkrona eller asynkrona. Flera
Zivan m.fl. REF undersökte effekterna av fördröjningar av meddelanden i problem med DCSP.
Message delay and DisCSP search algorithms
{'venue': 'Annals of Mathematics and Artificial Intelligence', 'journal': 'Annals of Mathematics and Artificial Intelligence', 'mag_field_of_study': ['Computer Science']}