Yehuda Afek

TCS Journal 2015 Journal Article

A simple characterization of asynchronous computations

• Yehuda Afek
• Eli Gafni

In this paper we investigate synchronous message-passing systems with reliable processors but different scenarios of message loss. In particular, we investigate and present the minimum set of messages whose delivery must be guaranteed to ensure the equivalence of this model to asynchronous wait–free shared-memory. Delivery guarantees were investigated in the past at the other extreme – delivery guarantees that ensure consensus. Because message failure is a more refined type of fault than processor crash failure, we were able to use in this paper an extremely simple message-passing model to characterize exactly what is computable in wait–free read–write shared memory. We use a synchronous complete network where in each round a subset from a defined family of subsets of messages, must be successfully delivered. With this model we obtain an extremely simple derivation of the Herlihy–Shavit condition that equates the wait–free read–write model with a subdivided-simplex. We show how each step in the computation inductively takes a subdivided-simplex and further subdivides it in the simplest way possible, making the characterization of read–write wait–free widely accessible.

FOCS Conference 1999 Conference Paper

ong-lived Adaptive Collect with Applications

• Yehuda Afek
• Gideon Stupp
• Dan Touitou

A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-lived and adaptive algorithms for collect in the read/write shared-memory model. Replacing the reads and writes in long-lived shared memory algorithms with our adaptive collect results in many cases in a corresponding long-lived algorithm which is adaptive. Examples of such applications, which are discussed are atomic-snapshots, and l-exclusion. Following the long-lived and adaptive collect we present a more pragmatic version of collect, called active set. This algorithm is slightly weaker than the collect but has several advantages. We employ this algorithm to transform algorithms, such as the Bakery algorithm, into their corresponding adaptive long-lived version, which is more efficient than the version that was obtained with the collect. Previously, long-lived and adaptive algorithms in this model were presented only for the renaming problem.

SODA Conference 1997 Conference Paper

Self-Stabilizing Unidirectional Network Algorithms by Power-Supply (Extended Abstract)

• Yehuda Afek
• Anat Bremler-Barr

TCS Journal 1997 Journal Article

The local detection paradigm and its applications to self-stabilization

• Yehuda Afek
• Shay Kutten
• Moti Yung

A new paradigm for the design of self-stabilizing distributed algorithms, called local detection, is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read/write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O(log n) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.

STOC Conference 1996 Conference Paper

Convergence Complexity of Optimistic Rate Based Flow Control Algorithms (Extended Abstract)

• Yehuda Afek
• Yishay Mansour
• Zvi Ostfeld

STOC Conference 1995 Conference Paper

Wait-free made fast (Extended Abstract)

• Yehuda Afek
• Dalia Dauber
• Dan Touitou

FOCS Conference 1993 Conference Paper

Synchronization power depends on the register size (Preliminary Version)

• Yehuda Afek
• Gideon Stupp

Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational power. The authors study this question and choose as a first target the popular compare and swap operation (which is the basis for many modern multiprocessor architectures). The results of this paper suggest that a complexity hierarchy for multiprocessor synchronization operations should be based on the space complexity of synchronization registers and not on the number of so called "synchronization objects". >

FOCS Conference 1989 Conference Paper

Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract)

• Yehuda Afek
• Eli Gafni
• Moty Ricklin

An algorithm and two lower bounds are presented for the problem of constructing and maintaining routing schemes in dynamic networks. The algorithm distributively assigns addresses to nodes and constructs routing tables in a dynamically growing tree. The resulting scheme routes data messages over the shortest path between any source and destination, assigns addresses of O(log/sup 2/n) bits to each node, and uses in its routing table O(log/sup 3/n) bits of memory per incident link, where n is the final number of nodes in the tree. The amortized communication cost of the algorithm is O(log n) messages per node. Also given are two lower bounds on the tradeoff between the quality of routing schemes (i. e. their stretch factor) and their amortized communication cost in general dynamic networks. >

FOCS Conference 1987 Conference Paper

Applying Static Network Protocols to Dynamic Networks

• Yehuda Afek
• Baruch Awerbuch
• Eli Gafni

This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.

FOCS Conference 1987 Conference Paper

Local Management of a Global Resource in a Communication Network

• Yehuda Afek
• Baruch Awerbuch
• Serge A. Plotkin
• Michael E. Saks

We introduce a new primitive, the Resource Controller, which abstracts the problem of controlling the total amount of resources consumed by a distributed algorithm. We present an efficient distributed algorithm to implement this abstraction. The message complexity of our algorithm per participating node is polylogarithmic in the size of the network, compared to the linear cost per node of the naive algorithm. The implementation of our algorithm is simple and practical and the techniques used are interesting because a global quantity is managed in a distributed way. The Resource Controller can be used to construct efficient algorithms for a number of important problems, such as the problem of bounding the worst-case message complexity of a protocol and the problem of dynamically assigning unique names to nodes participating in a protocol.