Arrow Research search

Author name cluster

Danny Dolev

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
2 author rows

Possible papers

28

TCS Journal 2018 Journal Article

Compact routing messages in self-healing trees

  • Armando Castañeda
  • Danny Dolev
  • Amitabh Trehan

Existing compact routing schemes, e. g. , Thorup and Zwick [4] and Chechik [6] often have no means to tolerate failures, once the system has been set up and started. This paper presents, to our knowledge, the first self-healing compact routing scheme. Besides, our schemes are developed for low memory nodes and are compact schemes, meaning they require only O ( log 2 ⁡ n ) bits memory. We introduce two algorithms of independent interest: The first is CompactFT, a novel compact version of the self-healing algorithm Forgiving Tree of Hayes et al. [7] that uses only O ( log ⁡ n ) bits local memory. The second algorithm (CompactFTZ) combines CompactFT with Thorup–Zwick's tree-based compact routing scheme [4] to produce a compact self-healing routing scheme. In the self-healing model, the adversary deletes nodes one at a time and the affected nodes self-heal locally by adding few edges. We introduce the bounded-memory self-healing model, where the memory each node need to use for the self-healing algorithm is bounded. CompactFT recovers from each attack in only O ( 1 ) time and Δ messages, with only +3 degree increase and O ( log ⁡ Δ ) graph diameter increase, over any sequence of deletions (Δ 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 ⁡ Δ ) 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 is removed from the network. CompactFTZ uses only O ( log ⁡ n ) bits memory for local fields (such as routing tables) and O ( log 2 ⁡ n ) bits for the routing labels, thus requiring O ( log 2 ⁡ n ) bits overall.

Details DOI

I&C Journal 1992 Journal Article

Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement

  • Amotz Bar-Noy
  • Danny Dolev
  • Cynthia Dwork
  • H. Raymond Strong

We describe several new algorithms for Byzantine agreement. The first of these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport, and is of comparable complexity to their algorithm. However, its proof is very intuitively appealing. A technique of shifting between algorithms for solving the Byzantine agreement problem is then studied. We present two families of algorithms obtained by applying a shift operator to our first algorithm. These families obtain the same rounds to message length trade-off as do Coan's families but do not require the exponential local computation time (and space) of his algorithms. We also describe a modification of an O( n )-resilient algorithm for Byzantine agreement of Dolev, Reischuk, and Strong. Finally, we obtain a hybrid algorithm that dominates all our others, by beginning execution of an algorithm in one family, first shifting into an algorithm of the second family, and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm.

Details DOI

I&C Journal 1991 Journal Article

Fault-tolerant critical section management in asynchronous environments

  • Amotz Bar-Noy
  • Danny Dolev
  • Daphne Koller
  • David Peleg

The paper deals with the problem of managing a fault-tolerant critical section in a completely asynchronous distributed network. The existence of a solution to this problem should be contrasted with a basic result of Fischer, Lynch, and Paterson, proving that in a completely asynchronous network, “nontrivial agreement” cannot be achieved even when only a single “benign” processor failure is possible. We present solutions to several versions of the critical section problem in this model. Denote by t the maximum number of possible faulty processors. Processors are allowed to fail while in the critical section, and therefore the critical section must have at least t + 1 slots. In the case where the slots are identical we present two algorithms which require t + 1 slots. The first is very simple, but requires every non-faulty processor to use the critical section infinitely often. The second solution allows non-faulty processors to quit. For distinct slots we present an algorithm that requires 2t + 1 slots.

Details DOI

FOCS Conference 1990 Conference Paper

Perfectly Secure Message Transmission

  • Danny Dolev
  • Cynthia Dwork
  • Orli Waarts
  • Moti Yung

The problem of perfectly secure communication in a general network in which processors and communication lines may be faulty is studied. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms that operate with this connectivity and rely on no complexity theoretic assumptions are derived. These are the first algorithms for secure communication in a general network to achieve simultaneously the goals of perfect secrecy, perfect resiliency, and a worst case time which is linear in the diameter of the network. >

Details

FOCS Conference 1989 Conference Paper

Multiparty Communication Complexity

  • Danny Dolev
  • Tomás Feder

A given Boolean function has its input distributed among many parties. The aim is to determine which parties to talk to and what information to exchange with each of them in order to evaluate the function while minimizing the total communication. It is shown that it is possible to obtain the Boolean answer deterministically with only a polynomial increase in communication with respect to the information lower bound given by the nondeterministic communication complexity of the function. >

Details

STOC Conference 1988 Conference Paper

Toward a Non-Atomic Era: \ell-Exclusion as a Test Case

  • Danny Dolev
  • Eli Gafni
  • Nir Shavit

Most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. Following Lamport, recent research promoting the use of weaker primitives, “safe” rather than “atomic,” has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. We argue that the properties provided by atomic operations may be too powerful, masking core difficulties of problems and leading to inefficiency. We therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. Though it has been shown that “test and set” cannot be implemented from safe registers, we show how to achieve a fair solution to l -exclusion, a classical concurrency control problem previously solved assuming a very powerful form of atomic “test and set”. We do so using safe registers alone and without introducing atomicity. The solution is based on the construction of a simple novel non-atomic synchronization primitive.

Details

I&C Journal 1987 Journal Article

A new look at fault-tolerant network routing

  • Danny Dolev
  • Joseph Y. Halpern
  • Barbara Simons
  • H.Raymond Strong

We model a communication network as a graph in which a processor is a node and a communication link is an edge. A routing for such a network is a fixed path, or route, between each pair of nodes. Given a network with a predefined routing, we study the effects of faulty components on the routing. Of particular interest is the number of routes along which a message must travel between any two non-faulty nodes. This problem is analyzed for specific families of graphs and for classes of routings. We also give some bounds for general versions of the problem. Finally, we conclude with one of the most important contributions of this paper, a list of interesting and apparently difficult open problems.

Details DOI

FOCS Conference 1987 Conference Paper

Achievable Cases in an Asynchronous Environment (Extended Abstract)

  • Hagit Attiya
  • Amotz Bar-Noy
  • Danny Dolev
  • Daphne Koller
  • David Peleg
  • Rüdiger Reischuk

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

Details

I&C Journal 1987 Journal Article

Efficient fault-tolerant routings in networks

  • Andrei Broder
  • Danny Dolev
  • Michael Fischer
  • Barbara Simons

We analyze the problem of constructing a network with a given number of nodes which has a fixed routing and which is highly fault tolerant. A construction is presented which forms a “product route graph” from two or more constituent “route graphs. ” The analysis involves the surviving route graph, which consists of all nonfaulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a “padding theorem” which allows one to add nodes to a graph and to extend a previous routing.

Details DOI

FOCS Conference 1984 Conference Paper

Flipping coins in many pockets (Byzantine agreement on uniformly random values)

  • Andrei Z. Broder
  • Danny Dolev

It was recently shown by Michael Rabin that a sequence of random 0-1 values, prepared and distributed by a trusted "dealer, " can be used to achieve Byzantine agreement in constant expected time in a network of processors. A natural question is whether it is possible to generate these values uniformly at random within the network. In this paper we present a cryptography based protocol for agreernent on a 0-1 randona value, if less than half of the processors are faulty. In fact the protocol allows uniform sampling from any finite set, and thus solves the problem of choosing a network leader uniformly at random. The protocol is usable both when all the communication is via "broadcast, " in which case it needs three rounds of information exchange, and when each pair of processors communicate on a private line, in which case it needs 3t + 3 rounds, where t is the number of faulty proccssors. The protocol remains valid even if passive eavesdropping is allowed. On the other hand we show that no (probabilistic) protocol can achieve agreement on a fair coin in fewer phases then necessary for Byzantine agreement, and hence the "pre-dealt" nature of the random sequence required for Rabin's algorithm is crucial.

Details

FOCS Conference 1983 Conference Paper

On the Minimal Synchronism Needed for Distributed Consensus

  • Danny Dolev
  • Cynthia Dwork
  • Larry J. Stockmeyer

Reaching agreement is a primitive of distributed computing. While this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: a system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer, Lynch and Paterson [FLP] have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper we extend their work, identifying several critical system parameters, including various synchronicity conditions, and examine how varying these affects the number of faults which can be tolerated. Our proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.

Details

FOCS Conference 1982 Conference Paper

'Eventual' Is Earlier than 'Immediate'

  • Danny Dolev
  • Rüdiger Reischuk
  • H. Raymond Strong

Two different notions of Byzantine Agreement - immediate and eventually - are defined depending on whether the agreement involves an action to be performed synchronously or not. The lower bounds for time complexity depend on what kind of agreement has to be achieved. All previous algorithms to reach Byzantine Agreement ensure immediate agreement. We present two algorithms that in many cases reach the second type of agreement faster than previously known algorithms showing that there actually is a difference between the two notions: Eventual Byzantine Agreement can be reached earlier than Immediate.

Details

STOC Conference 1982 Conference Paper

Polynomial Algorithms for Multiple Processor Agreement

  • Danny Dolev
  • H. Raymond Strong

Reaching agreement in a distributed system while handling malfunctioning behavior is a central issue for reliable computer systems. All previous algorithms for reaching the agreement required an exponential number of messages to be sent, with or without authentication. We give polynomial algorithms for reaching (Byzantine) agreement, both with and without the use of authentication protocols. We also prove that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.

Details

FOCS Conference 1981 Conference Paper

Unanimity in an Unknown and Unreliable Environment

  • Danny Dolev

Can unanimity be achieved in an unknown and unreliable distributed system? We analyze two extreme models of networks: one in which all the routes of communication are known, and the other in which not even the topology of the network is known. We prove that independently of the model, unanimity is achievable if and only if the number of faulty processors in the system is 1. less than one half of the connectivity of the system's network, and 2. less than one third of the total number of processors. In cases where unanimity is achievable, an algorithm to obtain it is given.

Details

TCS Journal 1979 Journal Article

Commutation properties and generating sets characterize slices of various synchronization primitives

  • Danny Dolev

Various synchronization primitives are described by adding and testing integer vectors, or by using “Petri Nets”. A slice represents a local behavior, described by permissible sequences of distinct actions of the system. We present a double characterization of slices defined by various synchronization primitives: In terms of generating sets and dually in terms of commutation properties. A typical form of a commutation property is: The set of sequences of past actions which disallow a certain coming action is closed under certain permutations. The synchronization primitives treated here include various systems which lie between PV and Vector Replacement Systems or Petri Nets.

Details DOI
v2026.09.13