A MapReduce algorithm can be described by a mapping schema , which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have a capacity that limits the sets of inputs they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which each input of a list, X , is required to meet each input of another list, Y , in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.

We investigate the problem of path selection under multiple QoS constraints, when the information available for making routing decisions is nondeterministic. The goal of the path selection process is to identify a feasible path while minimizing the overall setup time required for establishing a successful connection. We assume that a list of candidate paths already exists and, under some practical assumptions, we show how to find an optimal order of the given paths in order to achieve the goal.

This paper explores efficient discrete coding techniques that are motivated by the time/energy tradeoff in message transmission between mobile hosts and mobile support stations. Three algorithms are suggested two of which use guessing games in which the mobile support station guesses the message to be transmitted by the mobile host and receives approving signal for successful guess from the mobile host. The first algorithm is designed to achieve the smallest expected amount of energy while obeying a time bound for message transmissions. The second algorithm achieves the shortest expected transmission time while obeying a bound on the energy. This algorithm uses dynamic programming to construct an optimal tree for the guessing game. The third algorithm uses a different approach, approach that is based on the Lempel-Ziv (1978) compression algorithm. The time energy tradeoff is controlled by the choice of the length of the codes used to encode strings in the dictionary. The theoretical results obtained are not tied to mobile computing and are of independent interest.

No abstract available.

Both data communication and telecommunication networks consist of nodes, links and network resources. Many studies deal with the design of optimal network topologies. In current methodologies, every node presents the same constraints and behavior, while in reality, the network resources vary. The research problem at stake is how to add central network resources (i.e., servers, gateways, network managers, probes, mainframes, etc.) in an optimal way, for example, such that the transmission delay will be minimized. For small networks or for a small number of resources, it is feasible to find the optimal locations of the resources by checking all the possibilities. This method cannot be applied to large networks, where a great many of resources are located. In such cases the problem turns into a difficult optimization problem that can be classified as NP-complete. We deal with both optimal and heuristics techniques to solve this problem.

Sequential consistency is the most widely used correctness condition for multiprocessor memory systems. This paper studies the problem of testing shared-memory multiprocessors to determine if they are indeed providing a sequentially consistent memory. It presents the first formal study of this problem, which has applications to testing new memory system designs and realizations, providing run-time fault tolerance, and detecting bugs in parallel programs. A series of results are presented for testing an execution of a shared memory under various scenarios, comparing sequential consistency with linearizability, another well-known correctness condition. Linearizability imposes additional restrictions on the shared memory, beyond that of sequential consistency; these restrictions are shown to be useful in testing such memories.

Sequential consistency is the most-widely used correctness condition for multiprocessor memory systems. High-performance shared memory multiprocessors such as the Kendall Square KSR1, the Stanford DASH, and the MIT Alewife employ a variety of techniques to improve memory system performance while providing sequential consistency. Primary among them is the use of caches at each processor, kept coherent by protocols implemented in hardware.

Chou et al. (1990) presented two synchronizer algorithms for ABD networks. One of their synchronizers has a round time of three, and the other has a round time of only two but requires an additional bit in every message of the simulated algorithm. The authors show that ABD synchronization can be improved by using information that can be obtained, without exchanging more messages, during the initialization of the synchronizers. The authors first contribution is a synchronizer with a round time of two that does not require an additional bit in basic messages. The second result refutes the common belief that a round time of two is the best achievable for this type of synchronizer. They show that in some network topologies a smaller round time is achievable by making the local time of simulation of the pulses dependent on the arrival time of messages received during initialization. The correctness of the synchronizers is shown by modeling this class of synchronizers as functions, and using these functions lower bounds on the round time can also be easily obtained. The authors show that their synchronizers are optimal, i.e., further reduction of the round time by the same means is not possible.>

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.

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.

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

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.

Tills paper establishes several lower bounds of the form f~(nlogn) for the number of messages needed to find the maximum label in a circular configuration of n labeled processes with no central controller.

The problem of determining in a distributed fashion the centers and the medians of a network is considered.Lower bounds on the time needed to solve these problems are proved.Algorithms that achieve those bounds for tree networks are presented; the number of exchanged messages is linear in the number of nodes.These techniques are extended to work on general networks in O(n) time units exchanging O(n.e) messages, where n is the number of nodes and e the number of edges in the network.In addition, a comparison with a simple heuristic approach is included.

This paper deals with the problem of finding the maximum of a distributed set of distinct integers. The problem is to be solved by a completely distributed asynchronous algorithm.