کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333898 | 689835 | 2011 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Passively mobile communicating machines that use restricted space
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We propose a new theoretical model for passively mobile wireless sensor networks, called PM, standing for passively mobile machines. The main modification w.r.t. the population protocol model (Angluin et al., 2006) [30] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O(logn) memory, and use it to provide an exact characterization of the classes PMSPACE(f(n)) when f(n)=Ω(logn): they are precisely the classes of all symmetric predicates inNSPACE(nf(n)). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω(logn). We next explore the computability of the PM model when the protocols use o(loglogn) space per machine and prove that SEM=PMSPACE(f(n)) when f(n)=o(loglogn), where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(loglogn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 46, 28 October 2011, Pages 6469-6483
Journal: Theoretical Computer Science - Volume 412, Issue 46, 28 October 2011, Pages 6469-6483
نویسندگان
Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, Paul G. Spirakis,