000138593 001__ 138593
000138593 005__ 20180622133016.0
000138593 02470 $$2ISI$$a000270927200040
000138593 037__ $$aCONF
000138593 245__ $$aNames Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
000138593 260__ $$c2009
000138593 269__ $$a2009
000138593 336__ $$aConference Papers
000138593 520__ $$aWe 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.
000138593 6531_ $$aStorage Modification Machines
000138593 700__ $$0240335$$aGuerraoui, Rachid$$g105326
000138593 700__ $$aRuppert, Eric
000138593 7112_ $$a36th International Colloquium on Automata, Languages and Programming$$cRhodes, Greece$$dJuly 5-12, 2009
000138593 773__ $$t36th International Colloquium on Automata, Languages and Programming
000138593 8564_ $$zURL
000138593 8564_ $$s170963$$uhttps://infoscience.epfl.ch/record/138593/files/popbyz.pdf$$zn/a
000138593 909CO $$ooai:infoscience.tind.io:138593$$pconf$$pIC
000138593 909C0 $$0252114$$pDCL$$xU10407
000138593 937__ $$aLPD-CONF-2009-005
000138593 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000138593 980__ $$aCONF