اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStand Up Indulgent Rendezvous
159
0
0.0
(
0
)
تأليف
Quentin Bramas
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider two mobile oblivious robots that evolve in a continuous Euclidean space. We require the two robots to solve the rendezvous problem (meeting in finite time at the same location, not known beforehand) despite the possibility that one of those robots crashes unpredictably. The rendezvous is stand up indulgent in the sense that when a crash occurs, the correct robot must still meet the crashed robot on its last position. We characterize the system assumptions that enable problem solvability, and present a series of algorithms that solve the problem for the possible cases.
قيم البحث
اقرأ أيضاً
We propose an univesal scheme to design loop-free and super-stabilizing protocols for constructing spanning trees optimizing any tree metrics (not only those that are isomorphic to a shortest path tree). Our scheme combines a novel super-stabilizing
loop-free BFS with an existing self-stabilizing spanning tree that optimizes a given metric. The composition result preserves the best properties of both worlds: super-stabilization, loop-freedom, and optimization of the original metric without any stabilization time penalty. As case study we apply our composition mechanism to two well known metric-dependent spanning trees: the maximum-flow tree and the minimum degree spanning tree.
We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is $O(log^2n)$ bits and it converges in $O(n^2)$ rounds. Thus, this algorithm improves the convergence time of all previo
usly known self-stabilizing asynchronous MST algorithms by a multiplicative factor $Theta(n)$, to the price of increasing the best known space complexity by a factor $O(log n)$. The main ingredient used in our algorithm is the design, for the first time in self-stabilizing settings, of a labeling scheme for computing the nearest common ancestor with only $O(log^2n)$ bits.
We present an efficient clustering algorithm applicable to one-dimensional data such as e.g. a series of timestamps. Given an expected frequency $Delta T^{-1}$, we introduce an $mathcal{O}(N)$-efficient method of characterizing $N$ events represented
by an ordered series of timestamps $t_1,t_2,dots,t_N$. In practice, the method proves useful to e.g. identify time intervals of missing data or to locate isolated events. Moreover, we define measures to quantify a series of events by varying $Delta T$ to e.g. determine the quality of an Internet of Things service.
Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact
routing scheme. Besides, our schemes are developed for low memory nodes, i.e., nodes need only $O(log^2 n)$ memory, and are thus, compact schemes. We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version (using only $O(log n)$ local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008]. The second algorithm (CompactFTZ) combines CompactFT with Thorup-Zwicks tree-based compact routing scheme [SPAA 2001] to produce a fully compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time with the affected nodes self-healing locally by adding few edges. CompactFT recovers from each attack in only $O(1)$ time and $Delta$ messages, with only +3 degree increase and $O(log Delta)$ graph diameter increase, over any sequence of deletions ($Delta$ is the initial maximum degree). Additionally, CompactFTZ guarantees delivery of a packet sent from sender s as long as the receiver t has not been deleted, with only an additional $O(y log Delta)$ latency, where $y$ is the number of nodes that have been deleted on the path between $s$ and $t$. If $t$ has been deleted, $s$ gets informed and the packet removed from the network.
This paper proposes the first implementation of a self-stabilizing regular register emulated by $n$ servers that is tolerant to both mobile Byzantine agents, and emph{transient failures} in a round-free synchronous model. Differently from existing Mo
bile Byzantine tolerant register implementations, this paper considers a more powerful adversary where (i) the message delay (i.e., $delta$) and the period of mobile Byzantine agents movement (i.e., $Delta$) are completely decoupled and (ii) servers are not aware of their state i.e., they do not know if they have been corrupted or not by a mobile Byzantine agent.The proposed protocol tolerates emph{(i)} any number of transient failures, and emph{(ii)} up to $f$ Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the $mathcal{Z}_{13}$ domain and it is optimal with respect to the number of servers needed to tolerate $f$ mobile Byzantine agents in the given model.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
