Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures

We introduce a new theoretical model of ad hoc mobile computing in which agents have severely restricted memory, highly unpredictable movement and no initial knowledge of the system. Each agent’s memory can store O(1) bits, plus a unique identifier, and O(1) other agents’ identifiers. Inputs are distributed across n agents, and all agents must converge to the correct output value. We give a universal construction that proves the model is surprisingly strong: It can solve any decision problem in NSPACE(n log n). Moreover, the construction is robust with respect to Byzantine failures of a constant number of agents.


Publié dans:
36th International Colloquium on Automata, Languages and Programming
Présenté à:
36th International Colloquium on Automata, Languages and Programming, Rhodes, Greece, July 5-12, 2009
Année
2009
Mots-clefs:
Laboratoires:




 Notice créée le 2009-05-19, modifiée le 2019-12-05

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)