Search

• Formulate a non-cooperative game with both UEs and MECs as players. • Prove the existence of and convergence to a Nash equilibrium. • Develop a set of algorithms to find the Nash equilibrium. • Demonstrate numerical examples of non-cooperative games with and without MECs' participation. In a newly emerged fog computing environment, various user equipments (UE) enhance their computing power and extend their battery lifetime by computation offloading to mobile edge cloud (MEC) servers. Such an environment is distributed and competitive in nature. In this paper, we take a game theoretical approach to computation offloading optimization in a fog computing environment. Such an approach captures and characterizes the nature of a competitive environment. The main contributions of the paper can be summarized as follows. First, we formulate a non-cooperative game with both UEs and MECs as players. Each UE attempts to minimize the execution time of its tasks with an energy constraint. Each MEC attempts to minimize the product of its power consumption for computation and execution time for allocated tasks. Second, we develop a heuristic algorithm for a UE to determine its "heuristically" best response to the current situation, an algorithm for an MEC to determine its best response to the current situation, and an iterative algorithm to find the Nash equilibrium. Third, we prove that our iterative algorithm converges to a Nash equilibrium. We demonstrate numerical examples of our non-cooperative games with and without MECs' participation. We observe that our iterative algorithm always quickly converges to a Nash equilibrium. The uniqueness of our non-cooperative games is that the strategy set of a player can be discrete and the payoff function of a player can be obtained by a heuristic algorithm for combinatorial optimization. To the best of the author's knowledge, there has been no such investigation of non-cooperative games based on combinatorial optimization for computation offloading optimization in a fog computing environment. [ABSTRACT FROM AUTHOR]

Synchronous SGD with data parallelism, the most popular parallelization strategy for CNN training, suffers from the expensive communication cost of averaging gradients among all workers. The iterative parameter updates of SGD cause frequent communications and it becomes the performance bottleneck. In this paper, we propose a lazy parameter update algorithm that adaptively adjusts the parameter update frequency to address the expensive communication cost issue. Our algorithm accumulates the gradients if the difference of the accumulated gradients and the latest gradients is sufficiently small. The less frequent parameter updates reduce the per-iteration communication cost while maintaining the model accuracy. Our experimental results demonstrate that the lazy update method remarkably improves the scalability while maintaining the model accuracy. For ResNet50 training on ImageNet, the proposed algorithm achieves a significantly higher speedup (739.6 on 2048 Cori KNL nodes) as compared to the vanilla synchronous SGD (276.6) while the model accuracy is almost not affected (<0.2% difference). • Adaptive parameter update frequency control for scalable parallel deep learning. • Allowing gradient accumulation considering the direction of the gradients. • Reducing per-iteration communication cost at the input side model layers. • Overlapping gradient communications with backpropagation computations. [ABSTRACT FROM AUTHOR]

Abstract: Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of moves. Up until now the best transformer had a slowdown factor of moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer. [Copyright &y& Elsevier]

Abstract: In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on “the price of connectivity”, that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an n-vertex graph the ratio between the connected searching number and the non-connected one is while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton–Strahler number. [Copyright &y& Elsevier]

Abstract: In order to gather sensor data, a data gathering tree is commonly created as a subnetwork of a wireless sensor network. Power conservation is of paramount importance in such networks, and using periodic sleep–wake cycles for sensor nodes is one of the most effective methods for power conservation. This paper addresses the problem of scheduling the sleep–wake cycles of nodes in a data gathering tree under deadline constraints. After formally modeling the problem being addressed, an optimal wake-up frequency assignment (OWFA) algorithm, which takes into account the data rate at each node and the total permitted delay, is proposed. The results of simulations under various conditions showed that OWFA consumed about 8.6%∼24.3% less average power, and thus resulted in a 7.4%∼26.0% longer network lifetime, than a previously proposed method that did not consider individual data rates. [Copyright &y& Elsevier]

Abstract: History independent data structures, presented by Micciancio, are data structures that possess a strong security property: even if an intruder manages to get a copy of the data structure, the memory layout of the structure yields no additional information on the history of operations applied on the structure beyond the information obtainable from the content itself. Naor and Teague proposed a stronger notion of history independence in which the intruder may break into the system several times without being noticed and still obtain no additional information from reading the memory layout of the data structure. An open question posed by Naor and Teague is whether these two notions are equally hard to obtain. In this paper we provide a separation between the two requirements for comparison-based algorithms. We show very strong lower bounds for obtaining the stronger notion of history independence for a large class of data structures, including, for example, the heap and the queue abstract data structures. We also provide complementary upper bounds showing that the heap abstract data structure may be made weakly history independent in the comparison based model without incurring any additional (asymptotic) cost on any of its operations. (A similar result is easy for the queue.) Thus, we obtain the first separation between the two notions of history independence. The gap we obtain is exponential: some operations may be executed in logarithmic time (or even in constant time) with the weaker definition, but require linear time with the stronger definition. [Copyright &y& Elsevier]