We address the design of algorithms for multicores that are oblivious to machine parameters. We propose HM, a multicore model consisting of a parallel shared-memory machine with hierarchical multi-level caching, and w...
详细信息
We address the design of algorithms for multicores that are oblivious to machine parameters. We propose HM, a multicore model consisting of a parallel shared-memory machine with hierarchical multi-level caching, and we introduce a multicore-oblivious approach to algorithms and schedulers for HM. A multicore-oblivious algorithm is specified with no mention of any machine parameters, such as the number of cores, number of cache levels, cache sizes and block lengths. However, it is equipped with a small set of instructions that can be used to provide hints to the run-time scheduler on how to schedule parallel tasks. We present efficient multicore-oblivious algorithms for several fundamental problems including matrix transposition, FFT, sorting, the Gaussian Elimination Paradigm, list ranking, and connected components. The notion of a multicore-oblivious algorithm is complementary to that of a network-oblivious algorithm, introduced by Bilardi et al. (2007) [8] for parallel distributed-memory machines where processors communicate point-to-point. We show that several of our multicore-oblivious algorithms translate into efficient network-oblivious algorithms, adding to the body of known efficient network-oblivious algorithms. (c) 2013 Elsevier Inc. All rights reserved.
Federated Learning (FL) allows multiple clients to collaboratively train machine learning models while preserving the model privacy of the clients. However, when generating a global model during the aggregation proces...
详细信息
Federated Learning (FL) allows multiple clients to collaboratively train machine learning models while preserving the model privacy of the clients. However, when generating a global model during the aggregation process, a malicious FL server could derive clients' local model weights. Such a threat cannot be completely eliminated, even if model aggregation is performed in the Trusted Execution Environment of the server, due to memory access pattern attacks. To tackle this challenge, our paper focuses on the top-k model aggregation algorithm in FL and introduces a space efficient and oblivious sparsified model aggregation algorithm named Sort-Then-Insert (STI), which removes the dependency of the memory access pattern on the model input, thus protecting the confidentiality of clients' models. Compared with Path ORAM, STI is over 100 times faster, and compared with the state-of-the-art solution for the same problem, Olive, our theoretical analysis and experiments demonstrate that STI can achieve comparable performance overhead ( O ( nk log 2 ( nk )) + O ( d log2(d)) for STI vs. O((nk+d) log2(nk+d)) for Olive) and reduced space overhead ( max( O ( nk ) , O ( d )) for STI vs. O(nk+d) for Olive).
We propose a self-stabilizing marching algorithm for a group of oblivious robots in an obstacle-free workplace. To this end, we develop a distributed algorithm for a group of robots to transport a polygonal object, wh...
详细信息
ISBN:
(纸本)9783540922209
We propose a self-stabilizing marching algorithm for a group of oblivious robots in an obstacle-free workplace. To this end, we develop a distributed algorithm for a group of robots to transport a polygonal object, where each robot holds the object at a corner, and observe that each robot can simulate the algorithm, even after we replace the object by an imaginary one;we thus can use the algorithm as a marching algorithm. Each robot independently computes a velocity vector using the algorithm, moves to a new position with the velocity for a unit of time, and repeats this cycle until it reaches the goal position. The algorithm is oblivious, i.e., the computation depends only on the current robot configuration, and is constructed from a naive algorithm that generates only a selfish move, by adding two simple ingredients. For the case of two robots, we theoretically show that the algorithm is self-stabilizing, and demonstrate by simulations that the algorithm produces a motion that is fairly close to the time-optimal motion. For cases of more than two robots, we show that a natural extension of the algorithm for two robots also produces smooth and elegant motions by simulations as well.
Consider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules excha...
详细信息
Consider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given the sensor locations as input, moves the robots to suitable locations in the grid so that a connected network of all modules is established. The number of robots that the algorithm uses is worst case optimal.
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the (l,k)-routing problem, e...
详细信息
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the (l,k)-routing problem, each node can send at most l packets and receive at most k packets. Permutation routing is the particular case l = k = 1. In the r-central routing problem, all nodes at distance at most r from a fixed node v want to send a packet to v. In this article we study the permutation routing, the r-central routing and the general (l,k)-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the store-and-forward Delta-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on (l,k)-routing on plane grids. Our main contributions are the following: 1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. 2. Tight r-central routing algorithms on triangular and hexagonal grids. 3. Tight (k,k)-routing algorithms on square, triangular and hexagonal grids. 4. Good approximation algorithms (in terms of running time) for (l,k)-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the (l,k)-routing problem as a Weighted Edge Coloring problem on bipartite graphs.
obliviousness is a security feature to protect sensitive information from an algorithm's observable behaviours. For better run-time performance, many oblivious algorithms published recently are probabilistic inste...
详细信息
ISBN:
(纸本)9781450399012
obliviousness is a security feature to protect sensitive information from an algorithm's observable behaviours. For better run-time performance, many oblivious algorithms published recently are probabilistic instead of deterministic, but this also brings difficulties to reason about them. We introduce some challenges, works and further ideas in this paper, including the concrete contribution of extending PSL for verifying one of the random oblivious algorithms. We also present my further PhD research plan on this topic.
暂无评论