A relatively simple safety-belt mechanism for im-proving DNS system availability and efficiency is proposed here. While it may seem ambitious, a careful examination shows it is both feasible and beneficial for the DNS system. The mechanism called ‘DNS Real-time Update’ (DNSRU), a service that facilitates real-time and secure updates of cached domain records in DNS resolvers worldwide, even before the expiration of the corresponding Time To Live (TTL) values. This service allows Internet domain owners to quickly rectify any erroneous global IP address distribution, even if a long TTL value is associated with it. By addressing this critical DNS high availability issue, DNSRU eliminates the need for short TTL values and their associated drawbacks. Therefore, DNSRU reduces the traffic load on authoritative servers while enhancing the system's fault tolerance. In this paper we show that our DNSRU design is backward compatible, supports gradual deployment, secure, efficient, and feasible.

Abstract We investigate the effect of omnipresent cloud storage on distributed computing. To this end, we specify a network model with links of prescribed bandwidth that connect standard processing nodes, and, in addition, passive storage nodes. Each passive node represents a cloud storage system, such as Dropbox, Google Drive etc. We study a few tasks in this model, assuming a single cloud node connected to all other nodes, which are connected to each other arbitrarily. We give implementations for basic tasks of collaboratively writing to and reading from the cloud, and for more advanced applications such as matrix multiplication and federated learning. Our results show that utilizing node-cloud links as well as node-node links can considerably speed up computations, compared to the case where processors communicate either only through the cloud or only through the network links. We first show how to optimally read and write large files to and from the cloud in general graphs using flow techniques. We use these primitives to derive algorithms for combining , where every processor node has an input value and the task is to compute a combined value under some given associative operator. In the special but common case of “fat links,” where we assume that links between processors are bidirectional and have high bandwidth, we provide near-optimal algorithms for any commutative combining operator (such as vector addition). For the task of matrix multiplication (or other non-commutative combining operators), where the inputs are ordered, we present tight results in the simple “wheel” network, where procesing nodes are arranged in a ring, and are all connected to a single cloud node.

Many exceptionally high-quality doctoral dissertations were submitted for the 2022 Principles of Distributed Computing Doctoral Dissertation Award. After careful long deliberation, the award committee decided to share the award among two:

We present a new system to protect IoT devices in multiple premises by a single Virtual Network Function (VNF) deployed in the ISP network. The system is based on the Manufacturer Usage Description (MUD) framework, a white-list IoT protection scheme that has been proposed in recent years.While MUD is designed for on-premise deployment, here we adapt it to work as a scalable, managed service in the ISP level. Our service does not require any cooperation or installation on the client premise or on the IoT devices themselves. Furthermore, it monitors the IoT traffic and detects malicious behavior, including outgoing DDoS traffic, without being on the critical path, and it filters bad traffic by ACLs on either the POP router or the client CPE. The CPE itself is considered an IoT device and traffic destined or that originates at the CPE is monitored as well. For the white-list method we extend the MUD architectural framework to support peer to peer communicating IoT devices (e.g., direct mobile device to IoT device communication).The system includes a mechanism to distinguish between flows of different devices at the ISP level despite the fact that most home networks (and their IoT devices) are behind a NAT and all the flows from the same home come out with the same source IP address. Moreover, the NFV system needs to receive only the first packet of each flow/connection at the VNF, and rules space is proportional to the number of unique types of IoT devices rather than the total number of IoT devices (which is much larger).A PoC with a large national level ISP proves that our technology works as expected, identifying the various IoT devices that are connected to the network and detecting any unauthorized communications.

This demo focuses on demonstrating features of a new system to protect IoT devices in customer premises at the ISP level. The core of the system is deployed as a Virtual Network Function (VNF) within the ISP network, and is based on the Manufacturer Usage Description (MUD) framework, a white-list IoT protection scheme that has been proposed in recent years.As MUD is designed for on-premise deployment, the system makes the necessary adaptations to enable its deployment outside the customer premise. Moreover, the system includes a mechanism to distinguish between flows of different devices at the ISP level despite the fact that most home networks (and their IoT devices) are behind a NAT and all the flows from the same home come out with the same source IP address.Our demo follows closely a proof-of-concept that we have done with a large national level ISP, showing how our system can identify the various IoT devices that are connected to the network and detecting any unauthorized communications.

Is there an equilibrium for distributed consensus when all agents except one collude to steer the decision value towards their preference? If an equilibrium exists, then an n-1 size coalition cannot do better by deviating from the algorithm, even if it prefers a different decision value. We show that an equilibrium exists under this condition only if the number of agents in the network is odd and the decision is binary (among two possible input values). That is, in this framework we provide a separation between binary and multi-valued consensus. Moreover, the input and output distribution must be uniform, regardless of the communication model (synchronous or asynchronous). Furthermore, we define a new problem - Resilient Input Sharing (RIS), and use it to find an iff condition for the (n-1)-resilient equilibrium for deterministic binary consensus, essentially showing that an equilibrium for deterministic consensus is equivalent to each agent learning all the other inputs in some strong sense. Finally, we note that (n-2)-resilient equilibrium for binary consensus is possible for any n. The case of (n-2)-resilient equilibrium for multi-valued consensus is left open.

We present a basic tool for zero day attack signature extraction. Given two large sets of messages, P the messages captured in the network at peacetime (i.e., mostly legitimate traffic) and A the messages captured during attack time (i.e., contains many attack messages), we present a tool for extracting a set S of strings that are frequently found in A and not in P , thus allowing the identification of the attack packets. This is an important tool in protecting sites on the Internet from worm attacks and distributed denial of service attacks and may also be useful for other problems, including command and control identification and the DNA-sequences analysis. The main contributions of this paper are the system we developed to extract the required signatures together with the string-heavy hitters problem definition and the algorithm for solving this problem. This algorithm finds popular strings of variable length in a set of messages, using, in a tricky way, the classic heavy-hitter algorithm as a building block. The algorithm runs in linear time requiring one-pass over the input. Our system makes use of this algorithm to extract the desired signatures. Furthermore, we provide an extended algorithm which is able to identify groups of signatures, often found together in the same packets, which further improves the quality of signatures generated by our system. Using our system, a yet unknown attack can be detected and stopped within minutes from attack start time.

What can be computed by a network of n randomized finite state machines communicating under the stone age model (Emek & Wattenhofer, PODC 2013)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? We answer this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine's tape. To construct the tour with high probability, we first show how to 2-hop color the network concurrently with building a spanning tree.

The Dijkstra Prize Committee has decided to grant the 2018 Edsger W. Dijkstra Prize in Distributed Computing to Bowen Alpern and Fred B. Schneider for their paper:

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move from a set of initial positions to a set of final positions. The processes are oblivious (no internal memory) and must preserve, at any time, a minimal distance between them. A naive solution would be to move the processes one by one, but this would take too long. The difficulty here is to move the processes simultaneously in clearly delimited phases, no matter how unfavorable the initial configuration may be. We solve this by treating the problem "dimension by dimension": the processes first form 1D trails, then gather into a 2D shape (this technique can be generalized to higher dimensions). We present an optimal algorithm which time complexity depends linearly on the radius of the smallest circle containing both initial and final positions. The algorithm is self-stabilizing, as the processes are oblivious and the initial positions are arbitrary.

Until now, distributed algorithms for rational agents have assumed a-priori knowledge of $n$, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about $n$ is given. The a-priori knowledge of $n$ is formalized as a Bayesian setting where at the beginning of the algorithm agents only know a prior $σ$, a distribution from which they know $n$ originates. We begin by providing new algorithms for the Knowledge Sharing and Coloring problems when $n$ is a-priori known to all agents. We then prove that when agents have no a-priori knowledge of $n$, i.e., the support for $σ$ is infinite, equilibrium is impossible for the Knowledge Sharing problem. Finally, we consider priors with finite support and find bounds on the necessary interval $[α,β]$ that contains the support of $σ$, i.e., $α\leq n \leq β$, for which we have an equilibrium. When possible, we extend these bounds to hold for any possible protocol.

The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open. We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions.

Traditional DDoS anti-spoofing scrubbers require dedicated middleboxes thus adding CAPEX, latency and complexity in the network. This paper starts by showing that the current SDN match-and-action model is rich enough to implement a collection of anti-spoofing methods. Secondly we develop and utilize advance methods for dynamic resource sharing to distribute the required mitigation resources over a network of switches. None of the earlier attempts to implement anti-spoofing in SDN actually directly exploited the match and action power of the switch data plane. They required additional functionalities on top of the match-and-action model, and are not implementable on an SDN switch as is. Our method builds on the premise that an SDN data path is a very fast and efficient engine to perform low level primitive operations at wire speed. The solution requires a number of flow-table rules and switch-controller messages proportional to the legitimate traffic. To scale when protecting multiple large servers the flow tables of multiple switches are harnessed in a distributed and dynamic network based solution. We have fully implemented all our methods in either Open-Flow1.5 in Open-vSwitch and in P4. The system mitigates spoofed attacks on either the SDN infrastructure itself or on downstream servers.

We suggest a template that reveals the structure of many consensus algorithms as a generic procedure. The template builds on a new object, vacillate-adopt-commit which is an extension of the well known adopt-commit object. In addition we extend Aspnes's conciliator object to a new object that we call a reconciliator. The consensus algorithm template works in rounds of alternating vacillate-adopt-commit and reconciliator operations. The vacillate-adopt-commit object observes the processors' preferences and suggests a preference output with a measure of confidence vacillate, adopt or commit) on the preference. The reconciliator ensures termination, by providing new preferences for the processors. We show how several key consensus algorithms exactly fit our template. Here we demonstrate the decomposition of Ben-Or's randomized algorithm. The decomposition of the Phase King Byzantine and the Paxos algorithm are given in the full paper [1]. We analyze and compare our template based on vacillate-adopt-commit and reconciliator objects to previous work [3,5], suggesting a decomposition of consensus based on adopt-commit and conciliator objects. We claim that the three return values of vacillate-adopt-commit more accurately describe existing algorithms.

What can be computed by a network of n randomized finite state machines communicating under the stone age model (a generalization of the beeping model’s communication scheme)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? The reported reseach answers this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine’s tape. To construct the tour, it is first shown how to 2-hop color the network concurrently with building a spanning tree with high probability.

For all integers m ≥ 2, we construct an infinite sequence of deterministic objects of consensus number m with strictly increasing computational power. In particular, this refutes the Common2 Conjecture, which claimed that every deterministic object of consensus number 2 has a deterministic, wait-free implementation from 2-consensus objects and registers in a system with any finite number of processes.

This paper starts by demonstrating the vulnerability of Deep Packet Inspection (DPI) mechanisms, which are at the core of security devices, to algorithmic complexity denial of service attacks, thus exposing a weakness in the first line of defense of enterprise networks and clouds. A system and a multi-core architecture to defend from these algorithmic complexity attacks is presented in the second part of the paper. The integration of this system with two different DPI engines is demonstrated and discussed. The vulnerability is exposed by showing how a simple low bandwidth cache-miss attack takes down the Aho-Corasick (AC) pattern matching algorithm that lies at the heart of most DPI engines. As a first step in the mitigation of the attack, we have developed a compressed variant of the AC algorithm that improves the worst case performance (under an attack). Still, under normal traffic its running-time is worse than classical AC implementations. To overcome this problem, we introduce MCA2-Multi-Core Architecture to Mitigate Complexity Attacks, which dynamically combines the classical AC algorithm with our compressed implementation, to provide a robust solution to mitigate this cache-miss attack. We demonstrate the effectiveness of our architecture by examining cache-miss algorithmic complexity attacks against DPI engines and show a goodput boost of up to 73%. Finally, we show that our architecture may be generalized to provide a principal solution to a wide variety of algorithmic complexity attacks.

Configuring range based packet classification rules in network switches is crucial to all network core functionalities, such as firewalls and routing. However, OpenFlow, the leading management protocol for SDN switches, lacks the interface to configure range rules directly and only provides mask based rules, named flow entries. In this work we present, ORange, the first solution to multi dimensional range classification in OpenFlow. Our solution is based on paradigms used in state of the art non-OpenFlow classifiers and is designed in a modular fashion allowing future extensions and improvements. We consider switch space utilization as well as atomic updates functionality, and in the network context we provide flow consistency even if flows change their entrance point to the network during policy updates, a property we name cross-entrance consistency. Our scheme achieves remarkable results and is easy to deploy.

This paper introduces a temporally bounded total store ordering (TBTSO) memory model, and shows that it enables nonblocking fence-free solutions to asymmetric synchronization problems, such as those arising in memory reclamation and biased locking.

We present a new deep network layer called “Dynamic Convolutional Layer” which is a generalization of the convolutional layer. The conventional convolutional layer uses filters that are learned during training and are held constant during testing. In contrast, the dynamic convolutional layer uses filters that will vary from input to input during testing. This is achieved by learning a function that maps the input to the filters. We apply the dynamic convolutional layer to the application of short range weather prediction and show performance improvements compared to other baselines.

No abstract available.

Work stealing is the method of choice for load balancing in task parallel programming languages and frameworks. Yet despite considerable effort invested in optimizing work stealing task queues, existing algorithms issue a costly memory fence when removing a task, and these fences are believed to be necessary for correctness.

Following [4] we extend and generalize the game-theoretic model of distributed computing, identifying different utility functions that encompass different potential preferences of players in a distributed system. A good distributed algorithm in the game-theoretic context is one that prohibits the agents (processors with interests) from deviating from the protocol; any deviation would result in the agent losing, i.e., reducing its utility at the end of the algorithm. We distinguish between different utility functions in the context of distributed algorithms, e.g., utilities based on communication preference, solution preference, and output preference. Given these preferences we construct two basic building blocks for game theoretic distributed algorithms, a wake-up building block resilient to any preference and in particular to the communication preference (to which previous wake-up solutions were not resilient), and a knowledge sharing building block that is resilient to any and in particular to solution and output preferences. Using the building blocks we present several new algorithms for consensus, and renaming as well as a modular presentation of the leader election algorithm of [4].

With hardware transactional memory (HTM) becoming available in mainstream processors, lock-based critical sections may now initiate a hardware transaction instead of taking the lock, enabling their concurrent execution unless a real data conflict occurs. However, just a few transactional aborts can cause the lock to be acquired non-transactionally resulting in the serialization of all the threads, severely degrading the amount of speedup obtained. In this paper we provide two software extension mechanisms that considerably improve the concurrency and speedup levels attained by lock based programs using HTM-based lock elision. The first sacrifices opacity to achieve higher levels of concurrency, and the second retains opacity while reaching slightly lower levels of concurrency.

In the musical chairs game $MC(n,m)$, a team of $n$ players plays against an adversarial scheduler. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player occupies one of the $m$ available chairs. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be in conflict. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory?

We present a basic tool for zero day attack signature extraction. Given two large sets of messages, P of messages captured in the network at peacetime (i.e., mostly legitimate traffic) and A captured during attack time (i.e., contains many attack messages), we present a tool for extracting a set S of strings, that are frequently found in A and not in P. Therefore, a packet containing one of the strings from S is likely to be an attack packet. This is an important tool in protecting sites on the Internet from Worm attacks, and Distributed Denial of Service (DDoS) attacks. It may also be useful for other problems, including command and control identification, DNA-sequences analysis, etc. which are beyond the scope of this work. Two contributions of this paper are the system we developed to extract the required signatures together with the problem definition and the string-heavy hitters algorithm. This algorithm finds popular strings of variable length in a set of messages, using, in a tricky way, the classic heavy-hitter algorithm as a building block. This algorithm is then used by our system to extract the desired signatures. Using our system a yet unknown attack can be detected and stopped within minutes from attack start time.

We present a simple yet effective technique for improving performance of lock-based code using the hardware lock elision (HLE) feature in Intel's upcoming Haswell processor.

Conventional wisdom in designing concurrent data structures is to use the most powerful synchronization primitive, namely compare-and-swap (CAS), and to avoid contended hot spots. In building concurrent FIFO queues, this reasoning has led researchers to propose combining-based concurrent queues.

A recursive and fast construction of an n elements priority queue from exponentially smaller hardware priority queues and size n RAM is presented. All priority queue implementations to date either require O (log n) instructions per operation or exponential (with key size) space or expensive special hardware whose cost and latency dramatically increases with the priority queue size. Hence constructing a priority queue (PQ) from considerably smaller hardware priority queues (which are also much faster) while maintaining the O(1) steps per PQ operation is critical. Here we present such an acceleration technique called the Power Priority Queue (PPQ) technique. Specifically, an n elements PPQ is constructed from 2k-1 primitive priority queues of size k√n (k=2,3,...) and a RAM of size n, where the throughput of the construct beats that of a single, size n primitive hardware priority queue. For example an n elements PQ can be constructed from either three √n or five 3√n primitive H/W priority queues.

This paper takes advantage of the emerging multi-core computer architecture to design a general framework for mitigating network-based complexity attacks. In complexity attacks, an attacker carefully crafts "heavy" messages (or packets) such that each heavy message consumes substantially more resources than a normal message. Then, it sends a sufficient number of heavy messages to bring the system to a crawl at best. In our architecture, called MCA2---Multi-Core Architecture for Mitigating Complexity Attacks---cores quickly identify such suspicious messages and divert them to a fraction of the cores that are dedicated to handle all the heavy messages. This keeps the rest of the cores relatively unaffected and free to provide the legitimate traffic the same quality of service as if no attack takes place.

Poor placement of data blocks in memory may negatively impact application performance because of an increase in the cache conflict miss rate [18]. For dynamically allocated structures this placement is typically determined by the memory allocator. Cache index-oblivious allocators may inadvertently place blocks on a restricted fraction of the available cache indexes, artificially and needlessly increasing the conflict miss rate. While some allocators are less vulnerable to this phenomena, no general-purpose malloc allocator is index-aware and methodologically addresses this concern. We demonstrate that many existing state-of-the-art allocators are index-oblivious, admitting performance pathologies for certain block sizes. We show that a simple adjustment within the allocator to control the spacing of blocks can provide better index coverage, which in turn reduces the superfluous conflict miss rate in various applications, improving performance with no observed negative consequences. The result is an index-aware allocator. Our technique is general and can easily be applied to most memory allocators and to various processor architectures.

We consider the power of objects in the unbounded concurrency shared memory model, where there is an infinite set of processes and the number of processes active concurrently may increase without bound. By studying this model we obtain new results and observations that are relevant and meaningful to the standard bounded concurrency model.First we resolve an open problem from 2006 and provide, contrary to what was conjectured, an unbounded concurrency wait-free implementation of a swap object from 2-consensus objects. This construction resolves another puzzle that has eluded us for a long time, that of considerably simplifying a 16 year old complicated bounded concurrency swap construction.A further insight to the traditional bounded concurrency model that we obtain by studying the unbounded concurrency model, is a refinement of the top level of the wait-free hierarchy, the class of infinite-consensus number objects. First we resolve an open question of Merritt and Taubenfeld from 2003, showing that having n-consensus objects for all n does not imply consensus under unbounded concurrency. I.e., consensus alone, treated as a black box, cannot be boosted in this way. We continue to show an infinite-number consensus object that while able to perform consensus for any n-bounded concurrency (n unknown in advance) cannot solve consensus in the face of unbounded concurrency. This divides the infinite-consensus class of objects into two, those that can solve consensus for unbounded concurrency, and those that cannot.

Lock-based software transactional memory algorithms do not perform well in workloads with a high rate of context switches, which is caused for example by scheduling events or page faults. This occurs since threads that are switched-out by the operating system while holding locks block other threads from progressing, causing their transactions to abort repeatedly. We present here Lock Stealing, a novel contention management algorithm for minimizing the effect of context switches by enabling threads to acquire locks which are held by other threads. While some methods addressing this problem exist (e.g., schedctl in Solaris) they are best effort and only cover scheduling related context switches. In addition, they are platform specific and thus are not suitable or available in managed runtimes such as Java or .NET. In contrast, our approach is solely based on user-level code and is de-coupled from specific operating system events. We evaluate the performance of our approach on a set of benchmarks and observe improvements in both micro benchmarks and more elaborate test applications.

We present view transactions, a model for relaxed consistency checks in software transactional memory (STM). View transactions always operate on a consistent snapshot of memory but may commit in a different snapshot. They are therefore simpler to reason about, provide opacity and maintain composability. In addition, view transactions avoid many of the overheads associated with previous approaches for relaxing consistency checks. As a result, view transactions outperform the prior approaches by 1.13x to 2x on various benchmarks.

This paper explores the power of failure detectors in read write shared memory systems with n processes whose names are drawn from the set {1...m}, m>=2n-1. We do so by making an additional assumption, name obliviousness, on top of the three failure detector assumptions introduced by ZieliDski. We present name non-oblivious failure detectors that are strong enough to wait-free solve the Symmetry Breaking (SB) problem, but not enough to solve the (n-1)-Set Consensus problem. Furthermore a family of weakest such failure detectors is presented. On the other hand we show that any non trivial name oblivious failure detector can wait-free solve (n-1)-Set Consensus, by introducing a simple extension to anti-Omega, the Loose-anti-Omega failure detector, and proving that it is the weakest failure detector that conforms to the four assumptions above.

Common2, the family of objects that implement and are wait-free implementable from 2 consensus objects, is extended inhere in two ways: First, the stack object is added to the family --- an object that was conjectured not to be in the family. Second, Common2 is investigated in the unbounded concurrency model, whereas until now it was considered only in an n-process model.We show that fetch-and-add, test-and-set, and stack are in Common2 even with respect to this stronger notion of wait-free implementation. This necessitated the wait-free implementation of immediate snapshots in the unbounded concurrency model, which was previously not known to be possible.In addition to extending Common2, the introduction of unbounded-concurrency may help in resolving the Common2 membership problem: If, as conjectured, queue is not implementable for a-priori known concurrency n, then it is definitely not implementable for unbounded concurrency. Proving the latter should be easier than proving the former. In addition we conjecture that the swap object, that has an n-process implementation, does not have an unbounded concurrency implementation.

Labovitz et al. (2001) and Labovitz et al. (2000) noticed that sometimes it takes border gateway protocol (BGP) a substantial amount of time and messages to converge and stabilize following the failure of some node in the Internet. In this paper, we suggest a minor modification to BGP that eliminates the problem pointed out and substantially reduces the convergence time and communication complexity of BGP. Roughly speaking, our modification ensures that bad news (the failure of a node/edge) propagate fast, while good news (the establishment of a new path to a destination) propagate somewhat slower. This is achieved in BGP by allowing withdrawal messages to propagate with no delay as fast as the network forward them, while announcements propagate as they do in BGP with a delay at each node of one minRouteAdver (except for the first wave of announcements). As a by product of this work, a new stateless mechanism to overcome the counting to infinity problem is provided, which compares favorably with other known stateless mechanisms (in RIP and IGRP).

In (Ref.1), (Ref.2) it was noticed that sometimes it takes BGP a substantial amount of time and messages to converge and stabilize following the failure of some node in the Internet. In this paper we suggest a minor modification to BGP that eliminates the problem pointed out and substantially reduces the convergence time and communication complexity of BGP. Roughly speaking, our modification ensures that bad news (the failure of a node/edge) propagate fast, while good news (the establishment of a new path to a destination) propagate somewhat slower. This is achieved in BGP by allowing withdrawal messages to propagate with no delay as fast as the network forwards them, while announcements propagate as they do in BGP with a delay at each node of one minRouteAdver (except for the first wave of announcements).

The notion of Internet Policy Atoms has been recently introduced in [1], [2] as groups of prefixes sharing a common BGP AS path at any Internet backbone router In this paper we further research these 'Atoms'. First we offer a new method for computing the Internet policy atoms, and use the RIPE RIS database [6] to derive their structure Second, we show that atoms remain stable with only about 2--3% of prefixes changing their atom membership in eight hour periods. We support the 'Atomic' nature of the policy atoms by showing BGP update and withdraw notifications carry updates for complete atoms in over 70% of updates, while the complete set of prefixes in an AS is carried in only 21% of updates. We track the locations where atoms are created (first different AS in the AS path going back from the common origin AS 1) showing 86% are split between the origin AS and it's peers thus supporting the assumption that they are created by policies. Finally applying atoms "real fife" applications we achieve a modest savings in BGP updates due to the low average prefix count in the atoms.

A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in a network after removing k edges is the concatenation of at most k + 1 shortest paths in the original network.

We suggest a new simple forwarding technique to speed up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6), and performs IP lookup nearly as fast as IP/Tag switching but with a smaller memory requirement and a much simpler protocol. The basic idea is that each router adds a "clue" to each packet, telling its downstream router where it ended the IP lookup. Since the forwarding tables of neighboring routers are similar, the clue either directly determines the best prefix match for the downstream router, or provides the downstream router with a good point to start its IP lookup. The new scheme thus prevents repeated computations and distributes the lookup process across the routers along the packet path. Each router starts the lookup computation at the point its upstream neighbor has finished. Furthermore, the new scheme is easily assimilated into heterogeneous IP networks, does not require routers coordination, and requires no setup time. Even a flow of one packet enjoys the benefits of the scheme without any additional overhead. The speedup we achieve is about 10 times faster than current standard techniques. In a sense, this paper shows that the current routers employed in the Internet are clue-less; namely, it is possible to speed up the IP lookup by an order of magnitude without any major changes to the existing protocols.

Trainet, a new scheme to extend MPLS (multi-protocol label switching) is presented. The scheme works much like the subway system in a large metropolitan area. Each (unidirectional) subway line corresponds to a labeled path, and a route in the network is defined by either a pair, where count specifies how many hops a packet still has to take in the specified train, or a route may be defined by a sequence of such pairs. A sequence of such pairs specifies that the packet has to take a number of hops in one train-line, and then continue for a certain number of hops on another train-line and so forth. While slightly increasing the number of labels in a header and adding a counter to each label, the scheme reduces the total number of different labels necessary in the network, and in each switch. Thus, for a given number of labels it may support a larger number of flows. Moreover, our scheme considerably simplifies the path set-up cost while still providing all the features of MPLS: switching, supporting QoS, explicit routing, and traffic engineering.

In this paper we prove: For any constant d there is a large enough n such that there is no long-lived adaptive implementation of collect or renaming in the read write model with n processes that uses d or less MWMR registers.

Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. However, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. The number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is O(Nk3) and O(Nk4) respectively where N is the total number of processes in the system and k is the encountered contention. Here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, O(k4) for the snapshot implementation.

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.

Article Fast, wait-free (2k-1)-renaming Share on Authors: Yehuda Afek Tel Aviv University, Tel-Aviv, Israel Tel Aviv University, Tel-Aviv, IsraelView Profile , Michael Merritt AT&T Labs, 180 Park Av., Florham Park, NJ AT&T Labs, 180 Park Av., Florham Park, NJView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 105–112https://doi.org/10.1145/301308.301338Online:01 May 1999Publication History 43citation303DownloadsMetricsTotal Citations43Total Downloads303Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We suggest a new simple forwarding technique to speed-up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP lookup nearly as fast as IP/Tag-switching but with a smaller memory requirement and a much simpler protocol. The basic idea is that each router adds a "clue" to each packet, telling its downstream router where it ended the IP lookup. Since the forwarding tables of neighboring routers are similar, the clue either directly determines the best prefix match for the downstream router, or provides the downstream router with a good point to start its IP lookup. The new scheme thus prevents repeated computations and distributes the lookup process across the routers along the packet path. Each router starts the lookup computation at the point its up-stream neighbor has finished. Furthermore, the new scheme is easily assimilated into heterogeneous IP networks, does not require routers coordination, and requires no setup time. Even a flow of one packet enjoys the benefits of the scheme without any additional overhead. The speedup we achieve is about 10 times faster than current standard techniques. In a sense this paper shows that the current routers employed in the Internet are clue-less; Namely, it is possible to speedup the IP-lookup by an order of magnitude without any major changes to the existing protocols.

A local stabilizer protocol that takes any on-line or of-line distributed algorithm and converts it into a synchronous self-stabilizing algorithm with local monitoring and repairing properties is presented. Whenever the self-stabilizing version enters an inconsistent state, the inconsistency is detected, in O(1) time, and the system state is repaired in a local manner. The expected computation time that is lost during the repair process is proportional to the largest diameter of a faulty region.

We consider the problem of implementing atomic operations on multiple shared memory objects, in systems which directly support only single-object atomic operations.Our motivation is to design algorithms that exhibit both low contention between concurrent operations and a high level of concurrency, by disentangling long chains of conflicting operations.That is, operations that access widely disjoint parts of a data structure, or are widely separated in time, should not interfere with each other.The algorithm reported here extends and is based on the work of Attiya and Dagan [A D96], where a nonblocking solution is presented for two-object atomic operations.For any number, k, we present a wait-free solution for atomically accessing up to k objects.Notions of local contention and local step complexity are defined, and it is shown that the solution has low local contention and local step complexity.Relations between multi-objects and the familiar resource allocation problem are explored-the algorithm presented also provides a solution to the resource allocation problem. Int roduct ionConsider a data structure stored in shared memory and accessed concurrently by n processes.The shared data structure is abstracted w an array of memory locations.To perform its operation, a process needs to get exclusive access to the set of locations necessary to carry out qComputer

When traffic of connectionless best effort protocols such as IP is carried over connection oriented protocols with guaranteed bandwidth, such as CBR connection in ATM, the interface layer between the protocols (i.e., AAL-the ATM adaption layer) needs to specify the bandwidth requirement and the duration of the bandwidth reservation. The purpose of this paper is to develop policies for deciding and for adjusting the amount of bandwidth requested for a best effort connection over such networks. Our aim is to develop such policies that achieve a good trade off between latency and utilization. The performances of the different policies are compared by an empirical evaluation.

No abstract available.

Article The power of multi-objects (extended abstract) Share on Authors: Yehuda Afek Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs. Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs.View Profile , Michael Merritt AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Gadi Taubenfeld The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs. The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs.View Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 213–222https://doi.org/10.1145/248052.248096Published:01 May 1996 6citation173DownloadsMetricsTotal Citations6Total Downloads173Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents Phantom, a simple constant space algorithm for rate based flow control. As shown by our simulations, it converges fast to a fair rate allocation while generating a moderate queue length. While our approach can be easily implemented in ATM switches for managing ABR traffic, it is also suitable for flow control in TCP router based networks. Both the introduced overhead and the required modifications in TCP flow control systems are minimal. The implementation of this approach in TCP guarantees fairness and provides a unifying interconnection between TCP routers and ATM networks. The new algorithm easily inter-operates with current TCP flow control mechanisms and thus can be gradually introduced into installed based TCP networks.

This paper studies basic properties of rate based flowcontrol algorithms and of the max-min fairness criteria.For the algorithms we suggest a new approach for their mod cling and analysis, which may be considered more "optimistic" and realistic than traditional approaches.Three variations of the approach are presented and their rate of convergence to an optimal max-min fairness solution is analyzed.In addition, we introduce and analyze approximate rate based flow control algorithms.We show that under certain conditions the approximate algorithms may converge faster.However, we show that the resulting flows may be substantially different than the tlows according to the max-min fairness.We further demonstrate that the max-min fairness solution can be very sensitive to small changes, i.e., there are configurations in which an addition or deletion of a session with rate 8 may change the allocation of another session by Cl(c$ .2~), but by no more than 0(6 .2W).This implies that it might be hard to locally estimate in a given state how close a session is to its max-min fair allocation.

This paper introduces a new distributed data object called Resource Controller that provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of resources that may be managed by such an object include; number of messages sent, number of nodes participating in the protocol, and total CPU time consumed. The Resource Controller object is accessed through a procedure that can be invoked at any node in the network. Before consuming a unit of resource at some node, the controlled algorithm should invoke the procedure at this node, requesting a permit or a rejection. The key characteristics of the Resource Controller object are the constraints that it imposes on the global resource consumption. An (M, W)-Controller guarantees that the total number of permits granted is at mostM; it also ensures that, if a request is rejected, then at leastM—Wpermits are eventually granted, even if no more requests are made after the rejected one. In this paper, we describe several message and space-efficient implementations of the Resource Controller object. In particular, we present an (M, W)-Controller whose message complexity isO(nlog2nlog(M/(W+ 1)) wherenis the total number of nodes. This is in contrast to theO(nM)message complexity of a fully centralized controller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to the node.

An implementationof an asynchronous shared-data structure is wait-free if no adversarial scheduler can stop an individual operation on the data structure from making progress (that is the implementation can tolerate a fail-stop fault of any number of processes).An implementation is non-blocking if an adversarial scheduler cannot stop the system from making progress.of the Assoc!abon of Computing Machinery.o cop otherwse, or to repubhsh, requires y '/' a fee ancf/or soecl IC oermisslon.STOC' 95, L& Veg&, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 places the O(n) term of wait-free implementations with an O(k) term (or O(k~log f)).

This paper investigates the effects of the failure of shared objects on distributed systems.First the notion of a faulty shared object is introduced.Then upper and lower bounds on the space complexity of implementing reliable shared objects are provided, Shared object failures are modeled as instantaneous and arbitraty changes to the state of the object.Several constructions of nonfaulty wait-free shared objects from a set of shared objects, some of which may suffer any number of faults, are presented.Three of these constructions are: (1) A reliable atomic read/write register from 20~+ 8 atomic read/write registers ~of which may be faulty, (2) a reliable test& set register for n processes from n + 10 primitive test & set registers, one of which may be faulty, and 3n + 13 reliable atomic registers, and (3) a reliable consensus object from 2f + 1 read-modify-write registers when f of these may be faulty.Using these constructions a universal construction of any linearizable shared object from a set of either A preliminary version of the results presented in this paper appeared in

Theoretically, various shared synchronization objects, such as compare&swap and arbitrary read-modify-write registers, are universal [10, 20].That is, any sequentially specified task can be solved in a concurrent system that supports these objects and a large enough number of shared read/write registers.Are these objects indeed almighty?Or, are there other considerations that have

ongoing investigation into the computability power of proces-

Layered communicationprotocols frequently implement a FIFO message fiacility cm top of an unrehable non-FIFO serwce such as that provided hy a packet-swltchmg network.This paper investigates the possibdity of Implementing a reliable message layer on top of an underlying layer that can low packets and deliver them out of order, with the addltlonzd restriction that the implementatmn uses only a fixed fimte number of different packets.A new formalism is presented to spcclfy communication layers and their properties, the notion of their implementation by 1/0 automata.and the properties of such implementations.An 1/0 automaton that Implements a rellable layer over an unreliable layer is presented In this implementation, tbe number ot packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur.A proof is gwen that no protocol can avoid such performance degradatmn.

This paper addresses the question of distributively computing over a strongly connected unidirectional data communication network. In unidirectional networks the existence of a communication link from one node to another does not imply the existence of a link in the opposite direction. The strong connectivity means that from every node there is a directed path to any other node. The authors assume an arbitrary topology network in which the strong connectivity is the only restriction. Four models are considered, synchronous and asynchronous, and for each node space availability, which grows as either $O(1)$ bits or $O(\log n)$ bits per incident link, where n is the total number of nodes in the network, is considered. First algorithms for two basic problems in distributed computing in data communication networks, traversal, and election, are provided. Each of these basic protocols produces two directed spanning trees rooted at a distinguished node in the network, one called in-tree, leading to the root, and the other, out-tree, leading from the root. Given these trees, the authors efficiently transform bidirectional algorithms to run on unidirectional networks, and in particular solve other problems such as the broadcast and echo [E. J. CHANG, Decentralized Algorithms in Distributed Systems, Ph.D. thesis, University of Toronto. October 19791 in a way that is more efficient $O(n^2 )$ messages) than direct transformation (which yields $O(nm)$ messages algorithm). The communication cost of the traversal and election algorithms is $O(nm + n^2 \log n)$ bits ($O(nm)$ messages and time), where m is the total number of links in the network. The traversal algorithms for unidirectional networks of finite automata achieve the same cost $O(nm + n^2 \log n)$ bits ($O(nm)$ messages and time) bits) in the asynchronous case, while in the synchronous case the communication cost of the algorithm is ($O(nm)$ bits.

This article presents a solution to the first-come, first-enabled ℓ-exclusion problem of Fischer et al. [1979]. Unlike their solution, this solution does not use powerful read-modify-write synchronization primitives and requires only bounded shared memory. Use of the concurrent timestamp system of Dolev and Shavir [1989] is key in solving the problem within bounded shared memory.

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".>

We study a class of synchronization objects in shared memory concurrent systems, which we call common2.This class contains r-ead-modify-wr-ife objects that commute (e.g.fetch-and-add), or overwrite (e.g.swap) and queue shared objects.It is known that this class is contained in the consensus number 2 class of objects [Her91a], and most of the commonly used objects with consensus number 2 are included in it.We show that any object in the common~class can implement any other object in the class, in a system with an arbitrary number of processes.In fact we show that the objects

This paper introduces a general formulation of atomic snapshot memory , a shared memory partitioned into words written ( updated ) by individual processes, or instantaneously read ( scanned ) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer, n -reader registers. The third algorithm implements a multi-writer snapshot memory from atomic n -writer, n -reader registers, again echoing key ideas from the earlier constructions. All operations require Θ( n 2 ) reads and writes to the component shared registers in the worst case. — Authors' Abstract

This paper examines cache consistency conditions for multiprocessor shared memory systems. It states and motivates a weaker condition than is normally implemented. An algorithm is presented that exploits the weaker condition to achieve greater concurrency. The algorithm is shown to satisfy the weak consistency condition. Other properties of the algorithm and possible extensions are discussed.

This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.

This paper presents a simple and efficient building block, called slide, for constructing communication protocols in dynamic networks whose topology frequently changes. We employ slide to derive (1) an end-to-end communication protocol with optimal amortized message complexity, and (2) a general method to efficiently and systematically combine dynamic and static algorithms. (Dynamic algorithms are designed for dynamic networks, and static algorithms work in networks with stable topology.)

The problem of applying static distributed algorithms in an eventually connected network is addressed.We propose a new technique, bootstrap resynchronization,

This paper addresses the problem of distributively electing a leader in both synchronous and asynchronous complete networks. $O(n\log n)$ messages synchronous and asynchronous algorithms are presented. The time complexity of the synchronous algorithm is $O(\log n)$, while that of the asynchronous algorithm is $O(n)$. In the synchronous case, a lower bound of $\Omega (n\log n)$ on the message complexity is proven. It is also proven that any message-optimal synchronous algorithm requires $\Omega (\log n)$ time. In proving these bounds, the type of operations performed by nodes are not restricted. The bounds thus apply to general algorithms and not just to comparison-based algorithms.

An atomic snapshot memory is a shared data structure allowing concurrent processes to store information in a collection of shared registers, all of which may be read in a single atomic scan operation.This paper presents three wait-free implementations of atomic snapshot memory.Two constructions implement wait-free single-writer atomic snapshot memory from wait-free atomic single-writer, n-reader registers.A third construction implements a wait-free n-writer atomic snapshot memory from n-writer, n-reader registers.The first implementation uses unbounded

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

This paper examines cache consistency conditions (safety conditions) for multiprocessor shared memory systems.It states and motivates a weaker condition than is normally required.An algorithm is presented that exploits the weaker condition to achieve greater concurrency.The paper concludes with a proof that the algorithm satisfies the safety condition.

The alternating-bit protocol is a fundamental protocol for transmitting data across an unreliable transmission medium. The reliability of the protocol depends on its initial state. The authors present a self-stabilizing version of the alternating-bit protocol, i.e. the system converges to a state that guarantees reliable data transmission regardless of its initial state. Applications of the protocol and possible extensions are discussed.>

In this paper we introduce a new network model called a muZtimedia network.It combines the point-to-point message passing network and the multiaccess channel.To benefit from the combination we design algorithms which consist of two stages: a local stage which utilizes the parallelism of the point-to-point network and a global stage which utilizes the broadcast capability of the multiaccess channel.As a reasonable approach, one wishes to balance the complexities of the two stages by obtaining an efficient partition of the network 'AT&T Bell Labs.

This paper addresses the problem of end-toend communication over a dynamically changing network in which the sender and the receiver are not forever separated.We present several end-to-end communication protocols whose space complexity at each node is independent of either the input length or the network size.Although the time complexity of these protocols is bounded, their communication complexity is either unbounded, or exponential if an acyclic orientation of the network is given.To bound the communication complexity of the protocols, in the absence of an acyclic orientation, we assume either knowledge of the total number of nodes in the network, or that nodes have unique ids.These bounded communication-complexity protocols thus require O(logn) space per incident link at each node.In sum, we dispel the myth 'Supported by NSF Presidential Young

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.

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.

Article Free Access Share on Time and message bounds for election in synchronous and asynchronous complete networks Authors: Yehuda Afek Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile , Eli Gafni Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 186–195https://doi.org/10.1145/323596.323613Published:01 August 1985Publication History 27citation528DownloadsMetricsTotal Citations27Total Downloads528Last 12 Months38Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents distributed algorithms for election and traversal in strongly connected unidirectional networks. A unidirectional network consists of nodes which are processors connected by unidirectional communication links. Initially, processors differ by their identifier but are otherwise similar. The election algorithm distinguishes a single processor from all other processors. The election algorithm requires O(log n) bits of memory in each processor and has communication complexity of O(n • m+n2log n) bits. In the traversal algorithm one node initiates a token which visits all the nodes of the network and returns to the initiator. The traversal algorithm is derived from the election algorithm. It achieves the same communication complexity and uses only O(1) bits of memory in each processor.