I STOC'16, Fraigniaud m.fl. Tänk på problemet med att hitta en skatt gömd i en av många lådor som är beställda av betydelse. Det vill säga, om en skatt ligger i en viktigare låda, då skulle man vilja hitta den snabbare. Förutsatt att det finns många sökare, författarna föreslår att använda en algoritm som kräver ingen samordning mellan sökare kan vara mycket fördelaktigt. Förutom att man sparar på behovet av en mekanism för kommunikation och samordning åtnjuter sådana algoritmer en inneboende robusthet. Författarna fortsätter att lösa detta linjära sökproblem i fallet med räkna många lådor och en motståndare placerade skatt, och bevisa att den bästa snabb-upp möjligt av k icke-koordinerande sökare är exakt 2. Detta innebär i synnerhet att det asymmetriskt sett är fyra gånger så snabbt som i fallet med fullständig samordning. Vi föreslår en naturlig variant av problemet, där skatten placeras jämnt slumpmässigt i en av en ändlig, stor, antal lådor. Vi utformar icke-samordningsalgoritmer som uppnår en hastighetsökning på 6/5 för två sökare, en hastighetsökning på 3/2 för tre sökare, och i allmänhet en hastighetsökning på k(k + 1)/(3k − 1) för alla k ≥ 1 sökare. I takt med att k växer till oändligheten närmar sig därför upptrappningen tre gånger värre jämfört med fallet med full samordning. Dessutom är dessa gränser snäva i en stark mening eftersom ingen icke-samordnad sökalgoritm för k sökare kan uppnå bättre hastigheter. Vi utformar också icke-koordinerande algoritmer som endast använder logaritmiskt minne i storleken på sökdomänen, och ändå, asymptotiskt, uppnå optimal upphastighet. Slutligen noterar vi att alla våra algoritmer är extremt enkla och därmed tillämpliga.
Ett fortsättningsarbete med tanke på det fall där skatten placeras jämnt slumpmässigt i en stor domän studerades i REF.
Parallel Linear Search with no Coordination for a Randomly Placed Treasure
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}