Self-stabilization of dynamic systems assuming only read/write atomicity

Summary Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spanning tree protocol for systems with any connected communication graph. The thrid protocol is obtianed by use offair protoco combination, a simple technique which enables the combination of two self-stabilizing dynamic protocols. The result protocol is a self-stabilizing, mutualexclusion protocol for dynamic systems with a general (connected) communication graph. The presented protocols improve upon previous protocols in two ways: First, it is assumed that the only atomic operations are either read or write to the shared memory. Second, our protocols work for any connected network and even for dynamic network, in which the topology of the network may change during the excution. Shlomi Dolev received his B.Sc. in Civil Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and Ph.D. in computer Sciene in 1989 and 1992 from the Technion Israel Institute of Technology. He is currently a post-dotoral fellow in the Department of Computer Science at Texas A & M Univeristy. His current research interests include the theoretical aspects of distributed computing and communcation networks. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a sensior lecturer at the Electrical Engineering Department at the Technion. Prior tot his he was a postdoctoral fellow at the Aiken Computation Laboratory at harvard. His research interests are in Parellel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Shlomo Moran received his B.Sc. and D.Sc. degrees in matheamtics from Technion, Israel Institute of Technology, Haifa, in 1975 and 1979, respectively. From 1979 to 1981 he was assistant professors and a visiting research specialist at the University of Minnesota, Minneapolis. From 1981 to 1985 he was a senior lecturer at the Department of Computer Science. Technion, and from 1985 to 1986 he visted at IBM Thoas J. Watson Research Center, Yorktown Heights. From 1986 to 1993 he was an associated professor at the Department of Computer Science, Technin. in 1992–3 he visited at AT & T Bell Labs at Murray Hill and at Centrum voor Wiskunde en Informatica, Amsterdam. From 1993 he is a full professor at the Department of Computer Science, Technion. His researchinterests include distributed algorithm, computational complexity, combinatorics and grapth theory.Part of this research was supported in part by Technion V.P.R. Funds — Wellner Research Fund, and by the Foundation for Research in Electronics, Computers and Communictions, administrated by the Israel Academy of Sciences and Humanities.     

Bounds on evacuation time for deflection routing

Summary Upper bounds are given on the timeT needed to evacuatek packets from a synchronous packet network using deflection routing, whereby all packets that arrive at a node during one time slot leave the node during the next slot. For example,Tn+2(k–1) for a binaryn-cube network when priority is given to packets closer to their destination, and for a single destination networkT is less than or equal to the network diameter plusk–1 times the network deflection index. Deflection routing for one pass through an omega network is also considered. Bruce Hajek received a B.S. in Mathematics and an M.S. in Electrical Engineering from the University of Illinois and a Ph.D. in Electrical Engineering from the University of California at Berkeley. He is a Professor in the Coordinated Science Laboratory and the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, where he has been since August, 1979. His research interests include communication and computer network algorithms, information theory, random processes, and combinatorial optimization.Supported by the National Science Foundation under contract NSF ECS 83 52030 with matching funds provided by AT&T. Postal address: CSL, 1101 W. Springfield, Urbana IL 61801, USA.     

Atomic snapshots using lattice agreement

Summary Thesnapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to thelattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of read and write operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. We present a deterministic algorithm for lattice agreement that usedO (log² n) operations on 2-processorTest & Set registers, plusO (n) operations on atomic single-writer multi-reader registers. The shared objects are used by the algorithm in adynamic mode, that is, the identity of the processors that access each of the shared objects is determined dynamically during the execution of the algorithm. By a randomized implementation of 2-processorsTest & Set registers from atomic registers, this algorithm implies a randomized algorthm for lattice agreement that uses an expected number ofO (n) operations on (dynamic) atomic single-writer multi-reader registers. Combined with our transformation this yields implementations of atomic snapshots with the same complexity.Cambridge Research Laboratory, Digital Equipment Corporation Hagit Attiya received the B.Sc. degreeiin Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the departtment of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms. Maurice Herlihy received the A.B. degree in Mathematics from Harvard University, and the M.S. and the Ph.D. degrees in Computer Science from M.I.T. From 1984 to 1989 he was a faculty member in the Computer Science Department at Carnegie Mellon University in Pittsburgh, PA. In 1989 he joined the research staff at the Digital Equipment Corporation's Cambridge Research Laboratory in Cambridge MA. Since 1994, he has been on the faculty at the Computer Science Department at Brown University. Dr. Herlihy's research interests encompass practical and theoretical aspects of distributed and concurrent computation. Ophir achman received a B.A. in computer science from the Technion, Haifa, Israel in 1989 and M.Sc. in computer science from the Technion, Haifa, Israel, in 1992. He is now studying for a D.Sc. in computer science at the Technion. His currentarea of research is distributed computing, and in particular, asynchronous shared memory systems.This work appeared in preliminary form in proceedings ofthe 6th International Workshop on Distributed Algorithms [12]. This research was partially supported by grant No. 92-0233 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Technion V.P.R. funds — B. and G. Greenberg Research Fund (Ottawa), and the fund for the promotion of research in the TechnionPart of the work of this author was performed while visiting DEC Cambridge Research Laboratory     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

Direct routing: Algorithms and complexity

Direct routing is the special case ofbufferless routing whereN packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct routing:

Packet Routing in Networks with Long Wires

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((C lg^ε(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also show that for edge-simple paths, there exists a schedule (which could be found off-line) of length O((cd_max + D) (lg(d_max)/lg lg (d_max))), where d_max is the maximum wire delay in the network. These results improve upon previous routing results which assume that unit time suffices to traverse a wire of any length. They also yield improved results for job-shop scheduling as long as we incorporate a technical restriction on the job-shop problem.     

一种高效的多媒体无线传感器网络地理路由算法

针对多媒体无线传感器网络数据流巨大的特点,本文提出一种高效的地理路由算法AOGR。与现有的地理路由算法以路由单包时的性能最优化为目标相比,AOGR将一次会话中所有交互数据包作为整体,使得平均每包传输的路由跳数最少。它充分利用先行包在路由方面的参考作用以优化后续包的路由。随着路由数据包的增多,AOGR最终收敛于最短路径。最后,通过仿真实验验证该路由算法能够有效地减少GPSR协议在周边转发模式时产生的绕道跳数,路由平均跳数有明显减少。     

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing the current solution. Montemanni et al. [1] considered a DVRP as an extension to the standard vehicle routing problem (VRP) by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm. This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in [1]. The effectiveness of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs. Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario, Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain reasoning, optimization and evolutionary computation. Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and ant colony optimization.     

Counting networks with arbitrary fan-out

Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb ₁,...,b _k , if there exists a prime factorp ofn, such thatp does not divideb _i , for alli, 1ik. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2 ^k , for any integerk0, is constructed out of 2-balancers andp-balancers. Eran Aharonson received the B.A. and M.Sc. degrees in Computer Science from the Technion, Israel Institute of Technology (Haifa, Israel) in 1989 and 1992, respectively. He is currently vice president for research and development at ART-Advanced Recognition Technolgies Ltd., a company dedicated to handwriting and voice recognition. His general research interests are distributed computation, theoretical computer science and pattern recognition. Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.A preliminary version of this paper appears in proceedings of the3rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992, pp. 104–113. This research was supported by Technion V.P.R.-B. and G. Greenberg Research Fund (Ottawa)Supported by Rashi Enterprise graduate fellowship     

The Network as a Storage Device: Dynamic Routing with Bounded Buffers

We study dynamic routing in store-and-forward packet networks where each network link has bounded buffer capacity for receiving incoming packets and is capable of transmitting a fixed number of packets per unit of time. At any moment in time, packets are injected at various network nodes with each packet specifying its destination node. The goal is to maximize the throughput, defined as the number of packets delivered to their destinations. In this paper, we make some progress on throughput maximization in various network topologies. Let n and m denote the number of nodes and links in the network, respectively. For line networks, we show that Nearest-to-Go (NTG), a natural distributed greedy algorithm, is -competitive, essentially matching a known lower bound on the performance of any greedy algorithm. We also show that if we allow the online routing algorithm to make centralized decisions, there is a randomized polylog(n)-competitive algorithm for line networks as well as for rooted tree networks, where each packet is destined for the root of the tree. For grid graphs, we show that NTG has a competitive ratio of while no greedy algorithm can achieve a ratio better than . Finally, for arbitrary network topologies, we show that NTG is -competitive, improving upon an earlier bound of O(mn). An extended abstract appeared in the Proceedings of the 8th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, Berkeley, CA, USA, pp. 1–13, Lecture Notes in Computer Science, vol. 1741, Springer, Berlin. S. Angelov is supported in part by NSF Career Award CCR-0093117, NSF Award ITR 0205456 and NIGMS Award 1-P20-GM-6912-1. S. Khanna is supported in part by an NSF Career Award CCR-0093117, NSF Award CCF-0429836, and a US-Israel Binational Science Foundation Grant. K. Kunal is supported in part by an NSF Career Award CCR-0093117 and NSF Award CCF-0429836.     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

Bounded time-stamps

Summary Time-stamps are labels which a system adds to its data items. These labels enable the system to keep track of the temporal precedence relations among its data elements. Many distributed protocols and some applications use the natural numbers as time-stamps. The natural numbers however are not useful for bounded protocols. In this paper we develop a theory ofbounded time-stamps. Time-stamp schemes are defined and the complexity of their implementation is analyzed. This indicates a direction for developing a general tool for converting time-stamp based protocols to bounded protocols. Amos Israeli received his B.Sc. in Mathematics and Physics from Hebrew University in 1976, and his M.Sc. and D.Sc. in Computer Science from the Weizmann Institute in 1980 and the Technion in 1985, respectively. Currently he is a senior lecturer at the Tlectrical Engineering Department at the Technion. Prior to this he was a postdoctoral fellow at the Aiken Computation Laboratory at Harvard. His research interests are in Parallel and Distributed Computing and in Robotics. In particular he has worked on the design and analysis of Wait-Free and Self-Stabilizing distributed protocols. Ming Li received his M.S. and Ph.D. in Computer Science from Wayne State University in 1980 and Cornell University 1985, respectively. Currently he is an associate professor at the Computer Science Department at the University of Waterloo. His research interests are in Theory of Computing, Kolmogorov Complexity, and Machine Learning.Supported in part by the Weizmann fellowship and NSF Grant DCR-86-00379Supported in part by ONR Grant N00014-85-k-0445 and Army Research Office Grant DAAL03-86-K-0171 at Harvard University, by NSF Grant kDCR-86-06366 at Ohio State University, and by NSERC Operating Grant OGP0036747. Most of this work was done when the authors were at Aiken Computation Laboratory at Harvard University. The authors also acknowledge the hospitality of the computer science department at York University, Canada     

基于历史效用的机会网络路由算法

针对机会网络中传统的概率路由协议投递率较低的问题,提出一种基于历史相遇预测的改进概率路由(HMPR)算法。该算法根据节点历史接触时间和接触频率两个因素,预测数据包成功投递到目的节点的效用值,通过比较其效用值大小来决定数据包是否转发到下一跳节点。仿真结果表明,与传统的传染路由和概率路由相比,该路由在数据包投递率、平均延迟时间和平均缓存时间方面比上述两个路由协议的性能更好。     

Distributed algorithms for constructing a minimum-weight spanning tree in a broadcast network

Two distributed algorithms are presented for a network using a common communication channel (e.g. radio) in which all nodes are within signal range and in line of sight of each other: (a) an algorithm to compute all internode distances (in terms of propagation delays) in the network. the algorithm requires only 2 messages per node, and provides each node with the distances to all other nodes. (b) An algorithm for constructing a minimum-weight spanning tree (MST) in such a network. This algorithm starts out with the information provided by (a) and ends with each node possessing the explicit knowledge of the full MST. The algorithm requires at most log₂ N messages per node. The internal processing in each node needsO(N logN) time andO(N) space. All messages required by (a) and (b) contain at most one edge weight plus 2 log₂ N bits. Some possible applications of the algorithms are: position-location, tuning acknowledgement time-out mechanisms, tuning the scheduling functions of access protocols that are sensitive to individual internode propagation delays, and selecting performance effective transmission sequences for round robin access protocols.Yaron I. Gold received the B.Sc. (Cum Laude, 1970) and M.Sc. (1975), both in Electrical Engineering, from the Technion, Israel institute of Technology, and the Ph.D. (1981) in Computer Science, from the University of Minnesota, Minneapolis.From 1970 to 1975 Yaron Gold served as Research and Development Officer in the Israeli Defense Forces, leading a group of several scientists, engineers and technicians. From 1982 to 1984 he was on the faculty of the Department of Electrical Engineering the Department of Electrical Engineering and Computer Science at the University of Connecticut. During that period he also served as consultant for United Technologies Corporation and for Battelle Laboratories. Presently, Dr. Gold is on the faculty of the Computer Science Department at the Technion.His research interests include Computer Networks and Communications, Simulation and Intelligent Systems.Shlomo Moran received the B.Sc. and D.Sc. degrees in mathematics from Technion, Israel Institute of Technology, Haifa, in 1975 and 1979, respectively.From 1979 to 1981 he was assistant professor and a visiting research specialist at the University of Minnesota, Minneapolis. From 1981 to 1985 he was a senior lecturer at the Department of Computer Science, Technion, and from 1985 to 1986 he was a World Trade visitor at IBM Thomas J. Watson Research Center, Yorktown Heights. Currently he is associate professor at the Department of Computer Science, Technion.His research interests include distributed algorithms, computational complexity, combinatorics, graph theory and geometric aspects of communication networks.This work was supported in part by NSF grant ECS-8307186Part of this research was done while this author was with the University of ConnecticutPart of this research was done while this author was with IBM, Thomas J. Watson Research Center     

Randomized multipacket routing and sorting on meshes

We consider the problem of routing and sorting ond-dimensionaln×...× mesh connected computers. Each of the processing units initially holdsk packets. We present randomized algorithms that solve these problems with (1+o(1))·max{2·d·n,k·n/2} communication steps. On a torus these problems are solved twice as fast. Thus we match the bisection bound up to lower-order terms, for allk≥4·d. Earlier algorithms required some additional Θ(n) steps or more, and were more complicated. With 2·d·n extra steps our algorithm can also route in the cut-through routing model.     

One-bit algorithms

Many algorithms in distributed systems assume that the size of a single message depends on the number of processors. In this paper, we assume in contrast that messages consist of a single bit. Our main goal is to explore how the one-bit translation of unbounded message algorithms can be sped up by pipelining. We consider two problems. The first is routing between two processors in an arbitrary network and in some special networks (ring, grid, hypercube). The second problem is coloring a synchronous ring with three colors. The routing problem is a very basic subroutine in many distributed algorithms; the three coloring problem demonstrates that pipelining is not always useful. Amotz Bar-Noy received his B.Sc. degree in Mathematics and Computer Science in 1981, and his Ph.D. degree in Computer Science in 1987, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1989 he was a post-doctoral fellow in the Department of Computer Science at Stanford University. He is currently a visiting scientist at the IBM Thomas J. Watson Research Center. His current research interests include the theoretical aspects of distributed and parallel computing, computational complexity and combinatorial optimization. Joseph (Seffi) Naor received his B.A. degree in Computer Science in 1981 from the Technion, Israel Institute of Technology. He received his M.Sc. in 1983 and Ph.D. in 1987 in Computer Science, both from the Hebrew University of Jerusalem, Israel. Between 1987 and 1988 he was a post-doctoral fellow at the University of Southern California, Los Angeles, CA. Since 1988 he has been a post-doctoral fellow in the Department of Computer Science at Stanford University. His research interests include combinatorial optimization, randomized algorithms, computational complexity and the theoretical aspects of parallel and distributed computing. Moni Naor received his B.A. in Computer Science from the Technion, Israel Institute of Technology, in 1985, and his Ph.D. in Computer Science from the University of California at Berkeley in 1989. He is currently a visiting scientist at the IBM Almaden Research Center. His research interests include computational complexity, data structures, cryptography, and parallel and distributed computation.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731Supported by contract ONR N00014-88-K-0166 and by a grant from Stanford's Center for Integrated Systems. This work was done while the author was a post-doctoral fellow at the University of Southern California, Los Angeles, CAThis work was done while the author was with the Computer Science Division, University of California at Berkeley, and Supported by NSF grant DCR 85-13926     

From Active to Passive—Progress in Testing Internet Routing Protocols

Routing protocols play an important role in the Internet and the test requirements are running up.To test routing protocols more efficiently,several enhancing techniques are applied in the protocol integrated test system described in this paper.The Implementation Under Test is modeled as a black box with windows.The test system is endowed with multiple channels and multiple ports to test distributed protocols.The test suite and other related aspects are also extended.Meanwhile,the passive testing is introduced to test,analyze and manage routing protocols in the production field,which is able to perform the conformance test,the interoperability test and the performance test.The state machine of peer sessions is tested with the state synchronization algorithm,and the routing information manipulation and other operations are checked and analyzed with the methods like the topology analysis and the internal process simulation,With both the active testing and the passive testing,the routing protool test is going further and more thoroughly and helps a lot in the developmnt of routers。     

Atomicm-register operations

Summary We investigate systems where it is possible to access several shared registers in one atomic step. We characterize those systems in which the consensus problem can be solved in the presence of faults and give bounds on the space required. We also describe a fast solution to the mutual exclusion problem using atomicm-register operations. Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph. D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT&T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently coauthored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility. Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT&T Bell Laboratories. His primary research interests are in concurrent and distributed computing.A preliminary version of this workappeared in theProceedings of the Fifth International Workshop on Distributed Algorithms, Delphi, Greece, October 1991, pp 289–294     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).