BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Shlomi Dolev

Shlomi Dolev appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingCryptography and SecurityNetworking and Internet ArchitectureDatabasesData Structures and AlgorithmsComputational ComplexityEmerging TechnologiesHardware ArchitectureInformation Theorymath.ITMultiagent SystemsOther Computer ScienceRobotics

Catalog footprint

What is connected

29works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

29 published item(s)

preprint2020arXiv

Self-Stabilizing Automatic Repeat Request Algorithms for (Bounded Capacity, Omitting, Duplicating and non-FIFO) Computer Networks

End-to-end communication over the network layer (or data link in overlay networks) is one of the most important communication tasks in every communication network, including legacy communication networks as well as mobile ad hoc networks, peer-to-peer networks, and mesh networks. Reliable end-to-end communications are based on Automatic Repeat reQuest (ARQ) algorithms for dealing with packet failures, such as packet drops. We study ARQ algorithms that exchange packets to deliver (high level) messages in first-in-first-out (FIFO) order without omissions or duplications. We present a self-stabilizing ARQ algorithm that can be applied to networks of bounded capacity that are prone to packet loss, duplication, and reordering. Our analysis considers Lamport's happened-before relation when demonstrating stabilization without assuming the presence of a fair scheduler. It shows that the length of the longest chain of Lamport's happened-before relation is 8 for any system run.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Assignment Problems of Different-Sized Inputs in MapReduce

A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs that participate in the computation of this output. Reducers have a capacity, which limits the sets of inputs that they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which, each input of a list, X, is required to meet each input of another list, Y, in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient and Private Approximations of Distributed Databases Calculations

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separated databases and, a relative to it, issue of private data release were intensively investigated. However, despite a considerable progress, computational complexity, due to an increasing size of data, remains a limiting factor in real-world deployments, especially in case of privacy-preserving computations. In this paper, we present a general method for trade off between performance and accuracy of distributed calculations by performing data sampling. Sampling was a topic of extensive research that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on approximation of intersection set both without and with privacy-preserving mechanism. An analysis of the bound on error as a function of the sample size is discussed and heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Mending the Big-Data Missing Information

Consider a high-dimensional data set, in which for every data-point there is incomplete information. Each object in the data set represents a real entity, which is described by a point in high-dimensional space. We model the lack of information for a given object as an affine subspace in $\mathbb{R}^d$ whose dimension $k$ is the number of missing features. Our goal in this study is to find clusters of objects where the main problem is to cope with partial information and high dimension. Assuming the data set is separable, namely, its emergence from clusters that can be modeled as a set of disjoint ball in $\mathbb{R}^d$, we suggest a simple data clustering algorithm. Our suggested algorithm use the affine subspaces minimum distance and calculates pair-wise projection of the data achieving poly-logarithmic time complexity. We use probabilistic considerations to prove the algorithm's correctness. These probabilistic results are of independent interest, and can serve to better understand the geometry of high dimensional objects.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Meta-MapReduce: A Technique for Reducing Communication in MapReduce Computations

MapReduce has proven to be one of the most useful paradigms in the revolution of distributed computing, where cloud services and cluster computing become the standard venue for computing. The federation of cloud and big data activities is the next challenge where MapReduce should be modified to avoid (big) data migration across remote (cloud) sites. This is exactly our scope of research, where only the very essential data for obtaining the result is transmitted, reducing communication, processing and preserving data privacy as much as possible. In this work, we propose an algorithmic technique for MapReduce algorithms, called Meta-MapReduce, that decreases the communication cost by allowing us to process and move metadata to clouds and from the map phase to reduce phase. In Meta-MapReduce, the reduce phase fetches only the required data at required iterations, which in turn, assists in preserving the data privacy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Security and Privacy Aspects in MapReduce on Clouds: A Survey

MapReduce is a programming system for distributed processing large-scale data in an efficient and fault tolerant manner on a private, public, or hybrid cloud. MapReduce is extensively used daily around the world as an efficient distributed computation tool for a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and analysis of social networks. Security and privacy of data and MapReduce computations are essential concerns when a MapReduce computation is executed in public or hybrid clouds. In order to execute a MapReduce job in public and hybrid clouds, authentication of mappers-reducers, confidentiality of data-computations, integrity of data-computations, and correctness-freshness of the outputs are required. Satisfying these requirements shield the operation from several types of attacks on data and MapReduce computations. In this paper, we investigate and discuss security and privacy challenges and requirements, considering a variety of adversarial capabilities, and characteristics in the scope of MapReduce. We also provide a review of existing security and privacy protocols for MapReduce and discuss their overhead issues.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Self-stabilizing Reconfiguration

Current reconfiguration techniques are based on starting the system in a consistent configuration, in which all participating entities are in their initial state. Starting from that state, the system must preserve consistency as long as a predefined churn rate of processors joins and leaves is not violated, and unbounded storage is available. Many working systems cannot control this churn rate and do not have access to unbounded storage. System designers that neglect the outcome of violating the above assumptions may doom the system to exhibit illegal behaviors. We present the first automatically recovering reconfiguration scheme that recovers from transient faults, such as temporal violations of the above assumptions. Our self-stabilizing solutions regain safety automatically by assuming temporal access to reliable failure detectors. Once safety is re-established, the failure detector reliability is no longer needed. Still, liveness is conditioned by the failure detector's unreliable signals. We show that our self-stabilizing reconfiguration techniques can serve as the basis for the implementation of several dynamic services over message passing systems. Examples include self-stabilizing reconfigurable virtual synchrony, which, in turn, can be used for implementing a self-stabilizing reconfigurable state-machine replication and self-stabilizing reconfigurable emulation of shared memory.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Assignment of Different-Sized Inputs in MapReduce

A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs that participate in the computation of this output. Reducers have a capacity, which limits the sets of inputs that they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which, each input of a set, X, is required to meet each input of another set, Y, in at least one reducer. We prove that finding an optimal mapping schema for these families of problem is NP-hard, and present several approximation algorithms for finding a near optimal mapping schema.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Efficient On-line Detection of Temporal Patterns

Identifying a temporal pattern of events is a fundamental task of on-line (real-time) verification. We present efficient schemes for on-line monitoring of events for identifying desired/undesired patterns of events. The schemes use preprocessing to ensure that the number of comparisons during run-time is minimized. In particular, the first comparison following the time point when an execution sub-sequence cannot be further extended to satisfy the temporal requirements, halts the process that monitors the sub-sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of $n$ servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t<n/8 Byzantine servers if communication is asynchronous, and t<n/3 Byzantine servers if it is synchronous. The noteworthy feature of the proposed algorithms is that (to our knowledge) these are the first that build an atomic read/write storage on top of asynchronous servers prone to transient failures, and where up to t of them can be Byzantine.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Vehicle Authentication via Monolithically Certified Public Key and Attributes

Vehicular networks are used to coordinate actions among vehicles in traffic by the use of wireless transceivers (pairs of transmitters and receivers). Unfortunately, the wireless communication among vehicles is vulnerable to security threats that may lead to very serious safety hazards. In this work, we propose a viable solution for coping with Man-in-the-Middle attacks. Conventionally, Public Key Infrastructure (PKI) is utilized for a secure communication with the pre-certified public key. However, a secure vehicle-to-vehicle communication requires additional means of verification in order to avoid impersonation attacks. To the best of our knowledge, this is the first work that proposes to certify both the public key and out-of-band sense-able static attributes to enable mutual authentication of the communicating vehicles. Vehicle owners are bound to preprocess (periodically) a certificate for both a public key and a list of fixed unchangeable attributes of the vehicle. Furthermore, the proposed approach is shown to be adaptable with regards to the existing authentication protocols. We illustrate the security verification of the proposed protocol using a detailed proof in Spi calculus.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Vehicle to Vehicle Authentication

In recent future, vehicles will establish a spontaneous connection over a wireless radio channel, coordinating actions and information. Vehicles will exchange warning messages over the wireless radio channel through Dedicated Short Range Communication (IEEE 1609) over the Wireless Access in Vehicular Environment (802.11p). Unfortunately, the wireless communication among vehicles is vulnerable to security threats that may lead to very serious safety hazards. Therefore, the warning messages being exchanged must incorporate an authentic factor such that recipient is willing to verify and accept the message in a timely manner

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Ameba-inspired Self-organizing Particle Systems

Particle systems are physical systems of simple computational particles that can bond to neighboring particles and use these bonds to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far. We attempt to bridge this gap by proposing a model inspired by the behavior of ameba that allows rigorous algorithmic research on self-organizing particle systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme

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 previously known self-stabilizing asynchronous MST algorithms by a multiplicative factor $Θ(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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Self-Stabilizing Byzantine Resilient Topology Discovery and Message Delivery

Traditional Byzantine resilient algorithms use 2f+1 vertex disjoint paths to ensure message delivery in the presence of up to f Byzantine nodes. The question of how these paths are identified is related to the fundamental problem of topology discovery. Distributed algorithms for topology discovery cope with a never ending task, dealing with frequent changes in the network topology and unpredictable transient faults. Therefore, algorithms for topology discovery should be self-stabilizing to ensure convergence of the topology information following any such unpredictable sequence of events. We present the first such algorithm that can cope with Byzantine nodes. Starting in an arbitrary global state, and in the presence of f Byzantine nodes, each node is eventually aware of all the other non-Byzantine nodes and their connecting communication links. Using the topology information, nodes can, for example, route messages across the network and deliver messages from one end user to another. We present the first deterministic, cryptographicassumptions- free, self-stabilizing, Byzantine-resilient algorithms for network topology discovery and end-to-end message delivery. We also consider the task of r-neighborhood discovery for the case in which r and the degree of nodes are bounded by constants. The use of r-neighborhood discovery facilitates polynomial time, communication and space solutions for the above tasks. The obtained algorithms can be used to authenticate parties, in particular during the establishment of private secrets, thus forming public key schemes that are resistant to man-in-the-middle attacks of the compromised Byzantine nodes. A polynomial and efficient end-to-end algorithm that is based on the established private secrets can be employed in between periodical re-establishments of the secrets.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Self-Stabilizing Paxos

We present the first self-stabilizing consensus and replicated state machine for asynchronous message passing systems. The scheme does not require that all participants make a certain number of steps prior to reaching a practically infinite execution where the replicated state machine exhibits the desired behavior. In other words, the system reaches a configuration from which it operates according to the specified requirements of the replicated state-machine, for a long enough execution regarding all practical considerations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Data Interpolation: An Efficient Sampling Alternative for Big Data Aggregation

Given a large set of measurement sensor data, in order to identify a simple function that captures the essence of the data gathered by the sensors, we suggest representing the data by (spatial) functions, in particular by polynomials. Given a (sampled) set of values, we interpolate the datapoints to define a polynomial that would represent the data. The interpolation is challenging, since in practice the data can be noisy and even Byzantine, where the Byzantine data represents an adversarial value that is not limited to being close to the correct measured data. We present two solutions, one that extends the Welch-Berlekamp technique in the case of multidimensional data, and copes with discrete noise and Byzantine data, and the other based on Arora and Khot techniques, extending them in the case of multidimensional noisy and Byzantine data.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient Private Distributed Computation on Unbounded Input Streams

In the problem of swarm computing, $n$ agents wish to securely and distributively perform a computation on common inputs, in such a way that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation. Recently, Dolev, Garay, Gilboa and Kolesnikov [ICS 2011] considered this problem in the setting of information-theoretic security, showing how to perform such computations on input streams of unbounded length. The cost of their solution, however, is exponential in the size of the Finite State Automaton (FSA) computing the function. In this work we are interested in efficient computation in the above model, at the expense of minimal additional assumptions. Relying on the existence of one-way functions, we show how to process a priori unbounded inputs (but of course, polynomial in the security parameter) at a cost linear in $m$, the number of FSA states. In particular, our algorithms achieve the following: * In the case of $(n,n)$-reconstruction (i.e. in which all $n$ agents participate in reconstruction of the distributed computation) and at most $n-1$ agents are corrupted, the agent storage, the time required to process each input symbol and the time complexity for reconstruction are all $O(mn)$. * In the case of $(t+1,n)$-reconstruction (where only $t+1$ agents take part in the reconstruction) and at most $t$ agents are corrupted, the agents' storage and time required to process each input symbol are $O(m{n-1 \choose t-1})$. The complexity of reconstruction is $O(m(t+1))$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optical Solver of Combinatorial Problems: Nano-Technological Approach

We report the first steps in creating an optical computing system. This system may solve NP-Hard problems by utilizing a setup of exponential sized masks. This is exponential space complexity but the production of those masks is done with a polynomial time preprocessing. These masks are later used to solve the problem in polynomial time. We propose to reduced the size of the masks to nano-scaled density. Simulations were done to choose a proper design, and actual implementations show the feasibility of such a system.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO

A self-stabilizing protocol has the capacity to recover a legitimate behavior whatever is its initial state. The majority of works in self-stabilization assume a shared memory model or a communication using reliable and FIFO channels. In this article, we interest in self-stabilizing systems using bounded but non reliable and non FIFO channels. We propose a stabilizing communication protocol with optimal fault resilience. In more details, this protocol simulates a reliable and FIFO channel and ensures a minimal number of looses, duplications, creations, and re-ordering of messages.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computer Arithmetic Preserving Hamming Distance of Operands in Operation Result

The traditional approach to fault tolerant computing involves replicating computation units and applying a majority vote operation on individual result bits. This approach, however, has several limitations; the most severe is the resource requirement. This paper presents a new method for fault tolerant computing where for a given error rate, the hamming distance between correct inputs and faulty inputs as well as the hamming distance between a correct result and a faulty result is preserved throughout processing thereby enabling correction of up to transient faults per computation cycle. The new method is compared and contrasted with current protection methods and its cost / performance is analyzed.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient and Universal Corruption Resilient Fountain Codes

In this paper, we present a new family of fountain codes which overcome adversarial errors. That is, we consider the possibility that some portion of the arriving packets of a rateless erasure code are corrupted in an undetectable fashion. In practice, the corrupted packets may be attributed to a portion of the communication paths which are controlled by an adversary or to a portion of the sources that are malicious. The presented codes resemble and extend LT and Raptor codes. Yet, their benefits over existing coding schemes are manifold. First, to overcome the corrupted packets, our codes use information theoretic techniques, rather than cryptographic primitives. Thus, no secret channel between the senders and the receivers is required. Second, the encoders in the suggested scheme are oblivious to the strength of the adversary, yet perform as if its strength was known in advance. Third, the sparse structure of the codes facilitates efficient decoding. Finally, the codes easily fit a decentralized scenario with several sources, when no communication between the sources is allowed. We present both exhaustive as well as efficient decoding rules. Beyond the obvious use as a rateless codes, our codes have important applications in distributed computing.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Stabilizing data-link over non-FIFO channels with optimal fault-resilience

Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels. This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels. We propose a fault-send-deliver optimal stabilizing data-link layer that emulates a reliable FIFO communication channel over unreliable capacity bounded non-FIFO channels.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Deterministic and Energy-Optimal Wireless Synchronization

We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited. In the current setting, the problem is to synchronize clocks of $m$ processors that wake up in arbitrary time points, such that the maximum difference between wake up times is bounded by a positive integer $n$, where time intervals are appropriately discretized. Currently, the best-known results for synchronization for single-hop networks of $m$ processors is a randomized algorithm due to \cite{BKO09} of O(\sqrt {n /m} \cdot poly-log(n)) awake times per processor and a lower bound of Omega(\sqrt{n/m}) of the number of awake times needed per processor \cite{BKO09}. The main open question left in their work is to close the poly-log gap between the upper and the lower bound and to de-randomize their probabilistic construction and eliminate error probability. This is exactly what we do in this paper. That is, we show a {deterministic} algorithm with radio use of Theta(\sqrt {n /m}) that never fails. We stress that our upper bound exactly matches the lower bound proven in \cite{BKO09}, up to a small multiplicative constant. Therefore, our algorithm is {optimal} in terms of energy efficiency and completely resolves a long sequence of works in this area. In order to achieve these results we devise a novel {adaptive} technique that determines the times when devices power their radios on and off. In addition, we prove several lower bounds on the energy efficiency of algorithms for {multi-hop networks}. Specifically, we show that any algorithm for multi-hop networks must have radio use of Omega(\sqrt n) per processor.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Efficient Collaborative Application Monitoring Scheme for Mobile Networks

New operating systems for mobile devices allow their users to download millions of applications created by various individual programmers, some of which may be malicious or flawed. In order to detect that an application is malicious, monitoring its operation in a real environment for a significant period of time is often required. Mobile devices have limited computation and power resources and thus are limited in their monitoring capabilities. In this paper we propose an efficient collaborative monitoring scheme that harnesses the collective resources of many mobile devices, "vaccinating" them against potentially unsafe applications. We suggest a new local information flooding algorithm called "TTL Probabilistic Propagation" (TPP). The algorithm periodically monitors one or more application and reports its conclusions to a small number of other mobile devices, who then propagate this information onwards. The algorithm is analyzed, and is shown to outperform existing state of the art information propagation algorithms, in terms of convergence time as well as network overhead. The maximal "load" of the algorithm (the fastest arrival rate of new suspicious applications, that can still guarantee complete monitoring), is analytically calculated and shown to be significantly superior compared to any non-collaborative approach. Finally, we show both analytically and experimentally using real world network data that implementing the proposed algorithm significantly reduces the number of infected mobile devices. In addition, we analytically prove that the algorithm is tolerant to several types of Byzantine attacks where some adversarial agents may generate false information, or abuse the algorithm in other ways.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fast Self-Stabilizing Minimum Spanning Tree Construction

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 $Θ(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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Practically Stabilizing Atomic Memory

A self-stabilizing simulation of a single-writer multi-reader atomic register is presented. The simulation works in asynchronous message-passing systems, and allows processes to crash, as long as at least a majority of them remain working. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme that can accommodate arbitrary labels, i.e., including those not generated by the scheme itself.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

RoboCast: Asynchronous Communication in Robot Networks

This paper introduces the \emph{RoboCast} communication abstraction. The RoboCast allows a swarm of non oblivious, anonymous robots that are only endowed with visibility sensors and do not share a common coordinate system, to asynchronously exchange information. We propose a generic framework that covers a large class of asynchronous communication algorithms and show how our framework can be used to implement fundamental building blocks in robot networks such as gathering or stigmergy. In more details, we propose a RoboCast algorithm that allows robots to broadcast their local coordinate systems to each others. Our algorithm is further refined with a local collision avoidance scheme. Then, using the RoboCast primitive, we propose algorithms for deterministic asynchronous gathering and binary information exchange.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Randomization Adaptive Self-Stabilization

We present a scheme to convert self-stabilizing algorithms that use randomization during and following convergence to self-stabilizing algorithms that use randomization only during convergence. We thus reduce the number of random bits from an infinite number to a bounded number. The scheme is applicable to the cases in which there exits a local predicate for each node, such that global consistency is implied by the union of the local predicates. We demonstrate our scheme over the token circulation algorithm of Herman and the recent constant time Byzantine self-stabilizing clock synchronization algorithm by Ben-Or, Dolev and Hoch. The application of our scheme results in the first constant time Byzantine self-stabilizing clock synchronization algorithm that uses a bounded number of random bits.

0 citations0 reviewsNo code linkedOpen access