In the classical firing squad problem, an unknown number of nodes represented by identical finite state machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated ``firing" state. A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously. The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem? Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.

A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted asconvex recoloring(CR). While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest.

We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,… , M − 1}. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF (finding the maximum identity). We show that in chain and ring topologies, the message complexities of all three tasks are the same. Hence, we study a finer measure of complexity: the number of transmitted bits required to solve a task T , denoted BitC ( T ). We prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC (Consensus) = 2 and BitC (Leader) = BitC (MaxF) = 2log 2 M ± O (1), where the gap between the lower and upper bounds is almost always 1. For a chain, BitC (Consensus) = Θ( n ), BitC (Leader) = Θ( n + log M ), and BitC (MaxF) = Θ( n log M ). For the ring topology, we prove the lower bound of Ω( n log M ) for Leader, and (hence) MaxF. We consider also a chain where the intermediate processors have no identities. We prove that BitC (Leader) = Θ( n log M ), which is equal to n times the bit complexity of the problem for two processors. For the specific case when the chain length is even, we prove that BitC (Leader) = Θ( n ), for both above settings. In addition, we show that for any algorithm solving MaxF, there exists an input, for which every execution has the bit complexity Ω( n log M ) (this is not the case for Leader). In our proofs, we use both methods of distributed computing and of communication complexity theory, establishing new links between the two areas.

We study the process in which search engines with segmented indices serve queries. In particular, we investigate the number of result pages that search engines should prepare during the query processing phase.Search engine users have been observed to browse through very few pages of results for queries that they submit. This behavior of users suggests that prefetching many results upon processing an initial query is not efficient, since most of the prefetched results will not be requested by the user who initiated the search. However, a policy that abandons result prefetching in favor of retrieving just the first page of search results might not make optimal use of system resources either.We argue that for a certain behavior of users, engines should prefetch a constant number of result pages per query. We define a concrete query processing model for search engines with segmented indices, and analyze the cost of such prefetching policies. Based on these costs, we show how to determine the constant that optimizes the prefetching policy. Our results are mostly applicable to local index partitions of the inverted files, but are also applicable to processing short queries in global index architectures.

We study the caching of query result pages in Web search engines. Popular search engines receive millions of queries per day, and efficient policies for caching query results may enable them to lower their response time and reduce their hardware requirements. We present PDC (probability driven cache), a novel scheme tailored for caching search results, that is based on a probabilistic model of search engine users. We then use a trace of over seven million queries submitted to the search engine AltaVista to evaluate PDC, as well as traditional LRU and SLRU based caching schemes. The trace driven simulations show that PDC outperforms the other policies. We also examine the prefetching of search results, and demonstrate that prefetching can increase cache hit ratios by 50% for large caches, and can double the hit ratios of small caches. When integrating prefetching into PDC, we attain hit ratios of over 0.53.

This paper studies the design of low-cost survivable wavelength-division-multiplexing (WDM) networks. To achieve survivability, lightpaths are arranged as a set of rings. Arrangement in rings is also necessary to support SONET/SDH protection schemes such as 4FBLSR above the optical layer. This is expected to be the most common architecture in regional (metro) networks. We assume that we are given a set of lightpaths in an arbitrary network topology and aim at finding a partition of the lightpaths to rings adding a minimum number of lightpaths to the original set. The cost measure that we consider (number of lightpaths) reflects the switching cost of the entire network. In the case of a SONET/SDH higher layer, the number of lightpaths is equal to the number of add-drop multiplexers (ADMs) (since two subsequent lightpaths in a ring can share an ADM at the common node). We prove some negative results on the tractability and approximability of the problem and provide an approximation algorithm with a worst case approximation ratio of 8/5. We study some special cases in which the performance of the algorithm is improved. A similar problem was introduced, motivated, and studied by Liu, Li, Wan and Frieder (see Proc. INFOCOM 2000, p.1020-1025, 2000) Gerstel, Lin and Sasaki, (see Proc. IEEE INFOCOM '98, p. 94-101, 1998)(where it was termed minimum ADM problem). However, these two works focused on a ring topology while we generalize the problem to an arbitrary network topology.

Abstract We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.

Today, when searching for information on the WWW, one usually performs a query through a term-based search engine. These engines return, as the query's result, a list of Web pages whose contents matches the query. For broad-topic queries, such searches often result in a huge set of retrieved documents, many of which are irrelevant to the user. However, much information is contained in the link-structure of the WWW. Information such as which pages are linked to others can be used to augment search algorithms. In this context, Jon Kleinberg introduced the notion of two distinct types of Web pages: hubs and authorities . Kleinberg argued that hubs and authorities exhibit a mutually reinforcing relationship : a good hub will point to many authorities, and a good authority will be pointed at by many hubs. In light of this, he dervised an algoirthm aimed at finding authoritative pages. We present SALSA, a new stochastic approach for link-structure analysis, which examines random walks on graphs derived from the link-structure. We show that both SALSA and Kleinberg's Mutual Reinforcement approach employ the same metaalgorithm. We then prove that SALSA is quivalent to a weighted in degree analysis of the link-sturcutre of WWW subgraphs, making it computationally more efficient than the Mutual reinforcement approach. We compare that results of applying SALSA to the results derived through Kleinberg's approach. These comparisions reveal a topological Phenomenon called the TKC effect which, in certain cases, prevents the Mutual reinforcement approach from identifying meaningful authorities.

Ye m Dinitz Shlomo Moran Sergio Rajsbaum Abstract We consider a failure-free, asynchronous message passing network, with n processors arranged on a ring or a chain. The processes are identically programmed but have distinct identities, taken from f1; : : : ; Mg. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF ( nding the maximum identity, a restricted version of Leader). We show that in both chain and ring topologies, somewhat surprisingly, the message complexities of all three tasks are the same. Hence, we suggest as a ner measure of complexity the number of bits transmitted, BitC(). We show that in chains, w.r.t. this measure, Consensus is easier than Leader, which is easier than MaxF. More speci cally, we prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC(Consensus) = 2 and BitC(Leader) = BitC(MaxF) = 2 log 2 M O(1). For a chain, BitC(Consensus) = (n), and BitC(MaxF) = (n log M ). When the length is even BitC(Leader) = (n), while if the length is odd BitC(Leader) = (n + log M ).

Linear interval routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an interval with no wraparound. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For interval routing, the upper bound and lower bound on this quantity are 2D and 2D − 3, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D2) on the length of a path a message traverses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the total2-diameter (defined in Section 4) of the network, and by presenting a family of graphs for which this lower bound is tight. © 1999 John Wiley & Sons, Inc. Networks 34: 37–46, 1999

Self-stabilizing message-driven protocols are defined and discussed. The class weak exclusion that contains many natural tasks such as $\ell$-exclusion and token passing is defined, and it is shown that in any execution of any self-stabilizing protocol for a task in this class, the configuration size must grow at least in a logarithmic rate. This last lower bound is valid even if the system is supported by a time-out mechanism that prevents communication deadlocks. Then we present three self-stabilizing message-driven protocols for token passing. The rate of growth of configuration size for all three protocols matches the aforementioned lower bound. Our protocols are presented for two-processor systems but can be easily adapted to rings of arbitrary size. Our results have an interesting interpretation in terms of automata theory.

A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(/spl Delta/D log n) time when the number of the processors is unknown and O(/spl Delta/D), otherwise. Here /spl Delta/ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol.

Yao proved that in the decision-tree model, the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is shown that a similar result does not always hold in the common model of distributed computation, the model in which all the processors run the same program (which may depend on the processors’ input). We therefore construct a new technique that together with Yao’s method enables us to show that in many cases, a similar relationship does hold in the distributed model. This relationship enables us to carry over known lower bounds on the complexity of deterministic computations to the realm of randomized computations, thus obtaining new results. The new technique can also be used for obtaining results concerning algorithms with bounded error.

We study a new problem—the wakeup problem—that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, and other related problems. The main question we try to answer is “How much memory is needed to solve the wakeup problem?” We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique.>

Article Free Access Share on Wait-freedom vs. bounded wait-freedom in public data structures (extended abstract) Authors: Hagit Brit View Profile , Shlomo Moran Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 52–60https://doi.org/10.1145/197917.197950Online:14 August 1994Publication History 6citation196DownloadsMetricsTotal Citations6Total Downloads196Last 12 Months4Last 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

A counting protocol (mod m) consists of shared memory bits -referred to as the counter -and of a procedure for incrementing the counter value by 1 (mod m).The procedure may be executed by many processes concurrently.It is required to satisfy a very weak correctness requirement, namely: the counter is required to show a correct value only in quiescent states -states in which no process is incrementing the counter.Special cases of counting protocols are "counting networks" [AHS91] and "concurrent counters" [MTY92].We consider the problem of implementing a wait-free counting protocol, assuming that the basic atomic operation of a process is a read-modify-write on a single bit.Let ~lip(.%)be the maximum number of times a single increment operation changes the counter bits in a counting protocol Pr.Our main result is: In any waitfree counting protocol Pr which counts modulo m, m divides 2f~@tp'J.Thus, flip(Pr) z log m and m is a power of 2. This result provides interesting generalizations of lower bounds and impossibility results for counting and smoothing networks, Recently there was much interest in the implementation of counters in a concurrent environment where many processes may try to access the

Consider a bidirectional ring of n identical processors that communicate asynchronously. The processors have no identifiers, and hence the ring is called anonymous. Each processor receives an input letter, and the ring is to compute a function of the circular input string. If the function value is constant for all input strings, then the processors do not need to send any messages. On the other hand, it is proven that any deterministic algorithm that computes any nonconstant function for anonymous rings requires $\Omega (n\log n)$ bits of communication for some input string. Also exhibited are nonconstant functions that require $O(n\log n)$ bits of communication for every input string. The same gap for the bit complexity of nonconstant functions remains even if the processors have distinct identifiers, provided that the identifiers are taken from a large enough domain. When the communication is measured in messages rather than bits, the results change. A nonconstant function that can be computed with $O(n\log ^ * n)$ messages on an anonymous ring is presented.

Our purpose is to implement clocks and, in general, counters in a shared memory environment. A concurrent counter is a counter that can be incremented and read, possibly at the same time by many processes. We study counters that achieve high level of concurrency and thus are likely to reduce memory contention; require only weak atomicity and thus are easy to implement; do not depend on the initial state of the memory and hence are more robust to memory changes; and are wait-free - one process cannot prevent another process from finishing its increment or read operations - and thus can tolerate any number of process failures. We concentrate on providing upper and lower bounds on the space complexity of the counters studied.

Article Resource bounds for self stabilizing message driven protocols Share on Authors: Shlomi Dolev Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Amos Israeli Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Shlomo Moran Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 281–293https://doi.org/10.1145/112600.112624Online:01 July 1991Publication History 22citation195DownloadsMetricsTotal Citations22Total Downloads195Last 12 Months4Last 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 SiteGet Access

No abstract available.

We study a new problem, the wakeup problem, that seems to be very fundamental in distributed computing.We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader election problem, and other related problems.The main question we try to answer is, how much memory is needed to solve the wakeup problem?We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

Abstract We consider the problem of covering a weighted graph G = (V, E) by a set of vertex‐disjoint paths, such that the total weight of these paths is maximized. This problem is clearly NP‐complete, since it contains the Hamiltonian path problem as a special case. Three approximation algorithms for this problem are presented, exhibiting a complexity‐performance trade‐off. First, we develop an algorithm for covering undirected graphs. The time complexity of this algorithm is O(|E|log|E|), and its performance‐ratio is ½. Second, we present an algorithm for covering undirected graphs, whose performance‐ratio is ⅔. This algorithm uses a maximum weight matching algorithm as a subroutine, which dominates the overall complexity of our algorithm. Finally, we develop an algorithm for covering directed graphs, whose performanceratio is ⅔. This algorithm uses a maximum weight bipartite matching algorithm as a subroutine, which dominates the overall complexity of the algorithm.

The VLSI-related problem of embedding graphs in books is studied. A book embedding of a graph $G = ( V,E )$ consists of two parts, namely, (1) an ordering of V along the spine of the book, and (2) an assignment of each $e \in E$ to a page of the book, so that edges assigned to the same page do not intersect. In devising an embedding, one seeks to minimize the number of pages used. This paper addresses a generalization of the book embedding problem, called the black/white (b/w) book embedding problem, where a vertex-neighborhood constraint is imposed on the ordering of the vertices. A b/w graph is a pair $( G, U )$, where $G = ( V,E )$ is a graph and $U \subseteq V$ is a set of distinguished black vertices (the vertices in $V - U$ are called white). A b/w book embedding of $( G,U )$ is a book embedding of G, where the black vertices are arranged consecutively along the spine. Given a b/w graph $( G, U )$, the b/w book embedding problem is that of finding a b/w book embedding of $( G,U )$, such that the number of pages is minimized. The need for b/w embeddings may arise, for example, in applications where the input ports of a VLSI chip are to be separated from the output ports. The main result of this paper is a characterization of the b/w graphs that admit a one-page b/w embedding. The characterization is given in terms of a set of forbidden b/w subgraphs, the absence of which is necessary and sufficient for one-page b/w embedding. For a b/w graph with none of these forbidden subgraphs, a one-page b/w embedding is constructible in linear time. The construction utilizes a technique called b/w unfolding, which is a feature of independent interest.

A general, modular technique for designing efficient leader finding algorithms in distributed, asynchronous networks is developed. This technique reduces the problem of efficient leader finding to a simpler problem of efficient serial traversing of the corresponding network. The message complexity of the resulting leader finding algorithms is bounded by [ f ( n ) + n )(log 2 k + 1) (or ( f ( m ) + n )(log 2 k + 1)], where n is the number of nodes in the network [ m is the number of edges in the network], k is the number of nodes that start the algorithm, and f ( n ) [ f ( m )] is the message complexity of traversing the nodes [edges] of the network. The time complexity of these algorithms may be as large as their message complexity. This technique does not require that the FIFO discipline is obeyed by the links. The local memory needed for each node, besides the memory needed for the traversal algorithm, is logarithmic in the maximal identity of a node in the network. This result achieves in a unified way the best known upper bounds on the message complexity of leader finding algorithms for circular, complete, and general networks. It is also shown to be applicable to other classes of networks, and in some cases the message complexity of the resulting algorithms is better by a constant factor than that of previously known algorithms.

Abstract Let N be a network of asynchronous processors, viewed as vertices, communicating by sending messages over unreliable unidirectional edges, and let r be a specified vertex in N. We consider the problem of constructing efficient and reliable protocols to broadcast messages from r to all other vertices of N: Suppose that for some vertex v in N, at least k edges must be deleted in order to disconnect v from r; we say that a protocol PR, this message will eventually reach v. A protocol is faithful if it is reliable fro all vertices of the network. A general lower bound on the message complexity of faithful protocols, which is at most linear in the network size, is given. It is also shown that this bound can always be achieved by protocols which use the local memories of the vertices to record messages. On the other hand, it is shown that for certain networks, all faithful protocols that use no memory for local computations have a message complexity which is exponential in the network sixe. A characterization of networks that hve faithful protocosl with optimal message and space complexities is also given.

Fischer, Lynch and Paterson showed in a fundamental paper that achieving a distributed agreement for N > I processors is impossible in the presence of one faulty processor.This result was later extended by Moran and Wolfstahl who showed that it holds for any task with a connected input graph and a disconnected decision graph (whcrc a vcrtcx in the input [decision] graph is an N-tuple of input [decision] values of the processors, and there is an edge connecting two vertices if and only if they differ in exactly one component),In this paper we extend that latter result, and in fact we set the exact bordedine between solvable and unsolvable tasks, by giving a necessary and sufficient condition for a task to be solvable in the presence of a faulty processor.We present a universal protocol which solves any task which is found to be solvable by our condition.Using our characterization, we derive a novel technique to prove lower bounds on the number of messages that must be sent due to processor failure; specifically, we show that for each fixed JV > 2 there exist distributed tasks for Iv processors that can be solved in the presence of a faulty processor, but any protocol that solves them must send arbitrarily many messages in the worst case.

A least upper bound is derived on the amount of adjustment of virtual token passing (VTP) time needed to assure collision-free access control in VTP networks (i.e. networks that use 'time-out' or scheduling function-based access protocols) and in which nodes change their spatial configuration due to motion (although always stay within range and in line-of-sight of each other). Since the new bound is a function of network geographical size, as well as of node maximal speeds and the time that passed since the previous adjustment, it allows VTP times that are shorter than those found in previous publications, especially when intervals between adjustments grow larger. For most VTP networks, with large mixed populations of mobile and stationary users, the average VTP time (which is a major factor in performance of the access protocol) allowed by the new bound is shorter than that of any configuration-independent protocol.>

In a previous paper we showed that the distributive construction of a spanning tree in a complete network of processors can be done in $O(n\log n)$ messages. We show in this work that if the spanning tree is required to satisfy certain properties, then the complexity of its construction increases: First we show that the construction of a minimum weight spanning tree requires, in the worst case, at least $\Omega (n^2 )$ messages, and then we show that the construction of a spanning tree where the maximum degree is at most k may require at least $\Omega ({{n^2 } / k})$ messages in the worst case. Actually, in both cases the lower bounds are shown for the number of edges used in the worst case. Moreover, the results are valid for both asynchronous and synchronous networks, and are independent of the lengths of the messages. On the other hand, there are algorithms for the above tasks which achieve these lower bounds, up to a constant factor, and use messages of $O(\log n)$ length.

Article Free Access Share on Geometric applications of a matrix searching algorithm Authors: A Aggarwal IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , M Klawe IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile , S Moran IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , P Shor Math. Sciences Research Institute, Berkeley Math. Sciences Research Institute, BerkeleyView Profile , R Wilber IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile Authors Info & Claims SCG '86: Proceedings of the second annual symposium on Computational geometryAugust 1986Pages 285–292https://doi.org/10.1145/10515.10546Published:01 August 1986Publication History 39citation1,255DownloadsMetricsTotal Citations39Total Downloads1,255Last 12 Months234Last 6 weeks35 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

Consider a ring of n anonymous processors, i.e. the processors have no id's.Each processor receives an input string and the ring is to compute a function of the circular input configuration in the asynchronous bidirectional model of computation.The complexity of an algorithm is the number of bits or the number of messages sent in the worst case.The complexity of a function is the lowest complexity of any algorithm that computes that function.If the function value is constant for all input configurations, the processors do not need to send any messages (complexity zero).On the other hand, we prove that any non-constant function has bit complexity f~(n logn ) for anonymous rings.There are non-constant functions that reach the upper end of the gap, i.e. we exhibit a non-constant function of bit complexity O (nlogn).The same gap for the bit complexity of non-constant functions remains even if the processors have distinct id's, provided that the id's are taken from a large enough domain.For the case of using the number of messages sent rather than the number of bits as the complexity measure, we present a nonconstant function that can be computed with O (n log* n ) messages on an anonymous ring.

Article Free Access Share on Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings Authors: Baruch Shieber Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Tel Aviv, IsraelView Profile , Shlomo Moran IBM J. Watson Research Center, Yorktown Heights, NY IBM J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 282–292https://doi.org/10.1145/10590.10615Published:01 November 1986Publication History 14citation230DownloadsMetricsTotal Citations14Total Downloads230Last 12 Months10Last 6 weeks3 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

A general, modular technique for designing efficient leader finding algorithms in distributed, asynchronous networks is developed.This technique reduces the relatively complex problem of efficient leader finding to a simpler problem of efficient serial traversing of the corresponding network.The message complexity of the resulted leader finding algorithms is bounded by (f(n)+n)logn [ or (f (m )+n )logn ], where n is the number of nodes in the network [rrL is the number of edges in the network], and f (n) [f (rn)] is the message complexity of traversing the nodes [edges] of the network.This result achieves in a unified way the best known upper bounds on the message complexity of leader finding algorithms for circular, complete and Eulerian networks, and generalizes to other classes of more complex networks.Also, some known results are thus improved by a constant factor.

Article The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors Share on Authors: E. Korach Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile , S. Moran Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile , S. Zaks Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 277–286https://doi.org/10.1145/323596.323622Online:01 August 1985Publication History 2citation186DownloadsMetricsTotal Citations2Total Downloads186Last 12 Months1Last 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

Combinatorial techniques for extending lower bound results for decision trees to general types of queries are presented. Problems that are defined by simple inequalities between inputs, called order invariant problems, are considered. A decision tree is called k-bounded if each query depends on at most k variables. No further assumptions on the type of queries are made. It is proved that one can replace the queries of any k -bounded decision tree that solves an order-invariant problem over a large enough input domain with k -bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison-based algorithms are valid for general k -bounded decision trees, where k is a constant. An Ω( n log n ) lower bound for the element uniqueness problem and several other problems for any k -bounded decision tree, such that k = O ( n c ) and c < 1/2 is proved. This lower bound is tight since there exist n 1/2 -bounded decision trees of complexity O ( n ) that solve the element-uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

We look at a simple, but general model, of a systolic system called a trellis automaton (TA). A TA is equivalent in computational power to a one-dimensional unbounded cellular automaton (CA), a model of parallel computation which has been studied extensively in the literature. Different varieties of TA’s are equivalent to corresponding variations of CA’s. We present, for the first time, sequential machine characterizations of TA’s (CA’s). The sequential machines are useful and powerful tools for investigating properties of TA’s (CA’s). They ar easy to program because, unlike the parallel models, one does not have to deal with the problem of synchronization. Several applications are given. In particular, we prove a new speed-up theorem which is stronger than what has previously been shown.

Combinatorial techniques for extending lower bounds results for decision trees to general types of queries are presented. We consider problems, which we call order invariant, that are defined by simple inequalities between inputs. A decision tree is called k-bounded if each query depends on at most k variables. We make no further assumptions on the type of queries. We prove that we can replace the queries of any k-bounded decision tree that solves an order invariant problem over a large enough input dornain with k-bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison based algorithms are valid for general k-bounded decision trees, where k is a constant. We also prove an /spl Omega/(n log n) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k - )(n/sup c/) and c < 1/2. This lower bound is tight since that there exist n/sup 1/2/-bounded decision trees of complexity 0(n) that solve the element uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

Distributed algorithms for complete asynchronous networks of processors (i.e., networks where each pair of processors is connected by a communication line) are discussed. The main result is O(nlogn) lower and upper bounds on the number of messages required by any algorithm in a given class of distributed algorithms for such networks. This class includes algorithms for problems like finding a leader or constructing a spanning tree (as far as we know, all known algorithms for those problems may require O(n2) messages when applied to complete networks). O(n2) bounds for other problems, like constructing a maximal matching or a Hamiltonian circuit are also given. In proving the lower bound we are counting the edges which carry messages during the executions of the algorithms (ignoring the actually number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude of the total number of messages needed by these algorithms. In the upper bounds, the length of any message is at most log2[4mlog2n] bits, where m is the maximum identity of a node in the network. One implication of our results is that finding a spanning tree in a complete network is easier than finding a minimum weight spanning tree in such a network, which may require O(n2) messages.

Abstract Let G(V, E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints to be a transmitter, the other to be a receiver, and sending a message from the transmitter to the receiver through the line. We define several different models for communication networks, all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models, two problems arise: What is the maximum number of lines one can test simultaneously? and What is the minimum number of phases necessary for testing the entire network?, where, by “phase” we mean a period in which some tests are conducted simultaneously. We show that in most models, including the “natural” model of radio communication, both problems are NP‐hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem is unknown.

We describe a distributed method for keeping down “token-passing” overhead in a mobile multi-access network, by performing local corrections in the token-passing sequence as they become necessary due to changes in node spatial configuration. These corrections involve only a subset of the nodes in the network, thus reducing the required computational effort. The method consists of three distributed protocols. The first is for detecting deterioration and identifying a subset of nodes that constitutes a “problem area”, the second is to provide each node with the distances (propagation delays) to all other nodes, and the third is to use this topological information to construct a minimal spanning tree, from which a good “token passing” sequence can be derived. The second and third protocols may also have applications other than the one described here, such as position location, routing and broadcasting.

Let Q be any algebraic structure and ~the set of all total programs over Q using the instruction set {z ,,--1, z ,,-x + y, z ,,--x -y, z ~ x * y, z ~--x/y}.(A program is total if no division by zero occurs during any computation ) Let the equivalence problem for ~ be the problem of deciding for two given programs in ~whether or not they compute the same funcuon The following results are proved:(1) If Q is an inftmte field (e.g, the rauonal numbers or the complex numbers), then the equwalence problem for ~ is probabilistlcally decidable in polynomml time.The result also holds for programs with no dwlslon instructions and Q an infimte integral domain (e.g., the integers).(2) If Q is a finite field, or if Q is a fimte set of integers of cardmahty _>2, then the equivalence problem is NP-hard.The case when the field Q is finite but its cardinality is a funcuon of the size of the instance to the eqmvalence problem is also considered An example is shown for which a sharp boundary between the classes NP-hard and probabihsticaUy decidable exists (provided they are not identical classes).

Fast simulations of time-bounded single-tape TM’s and offline TM’s (i.e., TM’s with a two-way read-only input and one storage tape) by space-bounded TM’s of the same type are presented. The following results are shown: (1) Any language accepted by a single-tape TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape TM in space $T^{1/2} (n)$ and time $T^2 (n)$. (2) Any language accepted by an offline TM in time $T(n) \geqq n $ can be accepted by an offline TM in space $(T(n)\log n)^{1/2} $ and time $T^{3/2} (n)(T^{1/2} (n) + n/(\log n)^{1/2} )$. Similar (in fact, in some sense, stronger) results hold for nondeterministic TM’s. For example: (3) Any language accepted by a single-tape nondeterministic TM in time $T(n) \geqq n^2 $ can be accepted by a single-tape nondeterministic TM in space $S(n)$ and time $T^2 (n)/S(n)$ for any $T^{1/2} (n) \leqq S(n) \leqq T(n)$. Similar time-space tradeoffs hold for TM’s with a multidimensional storage tape. Previously known results on simulation of time bounded by space bounded TM’s had exponential (in $T(n)$) time complexity.

We present a theoretical description and analysis of a collision-free channel-access protocol for a shared channel with "mobile" nodes that are all within range and in line-of-sight of each other, in arbitrarily changing spatial (one-, two-or three-dimensional) configurations.

We consider the problem of designing an information retrieval system on which partial match queries have to be answered. Each record in the system consists of a list of attributes , and a partial match query specifies the values of some of the attributes. The records are stored in buckets in a secondary memory, and in order to answer a partial match query all the buckets that may contain a record satisfying the specifications of that query must be retrieved. The bucket in which a given record is stored is found by a multiple key hashing function, which maps each attribute to a string of a fixed number of bits. The address of that bucket is then represented by the string obtained by concatenating the strings on which the various attributes were mapped. A partial match query may specify only part of the bits in the string representing the address, and the larger the number of bits specified, the smaller the number of buckets that have to be retrieved in order to answer the query. The optimization problem considered in this paper is that of deciding to how many bits each attribute should be mapped by the bashing function above, so that the expected number of buckets retrieved per query is minimized. Efficient solutions for special cases of this problem have been obtained in [1], [12], and [14]. It is shown that in general the problem is NP-hard, and that if P ≠ NP, it is also not fully approximable. Two heuristic algorithms for the problem are also given and compared.

Let $Al$ be a polynomial time nondeterministic algorithm accepting a set A, and let $a \in A$. The “accepting density” of $Al$ for a is the ratio between the number of accepting computations and the total number of computations of $Al$ on input a. (If this ratio is $ \geqq 1/2$ for all $a \in A$, then $Al$ is a polynomial time probabilistic algorithm accepting A.) In this paper a characterization of sets in NP according to their “accepting density” is investigated. It is shown that for some relativized form of NP no general, nontrivial lower bound on the accepting density of sets in NP exists. It follows that for this relativized form the accepting density of any NP complete set for inputs of length n cannot be greater than $1/2^{n^c } $ for some fixed $c > 0$ and that NP (under that relativization) can be partitioned to infinitely many classes $C_1 ,C_2 , \cdots $, such that the accepting density of sets in $C_i $ is strictly greater, in some precise sense, than that of sets in $C_{i + 1} $. Recent works on the relationship between relativized and unrelativized proof techniques imply that to prove that any of the above results does not hold for the (unrelativized) class NP, possible at all, is probably beyond the ability of today’s techniques.