Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStand Up Indulgent Rendezvous
159
0
0.0
(
0
)
Added by
Quentin Bramas
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Quentin Bramas
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 previously 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 Mobile 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
