BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Shlomi Dolev

Shlomi Dolev contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingCryptography and SecurityNetworking and Internet ArchitectureData Structures and AlgorithmsHardware ArchitectureInformation Theorymath.ITMultiagent SystemsRobotics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

10 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
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
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

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