Back from Supercomputing by Bruno Raffin (Datamove)
– November 28, 2019
Bruno will present his report from the new trends he saw this year at supercomputing as well as explain some technical talks he liked presented at the conference.
Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution by Paul Duetting (Google, switzerland)
– November 14, 2019
(ACM EC 2019 Best Full Paper Award)
A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1,..., Xn drawn independently from a distribution F, the goal is to choose a stopping time τ so as to maximize α such that for all distributions F we have E[Xτ] ≥ α · E[maxt Xt]. What makes this problem challenging is that the decision whether τ = t may only depend on the values of the random variables X1,..., Xt and on the distribution F. For a long time the best known bound for the problem had been α ≥ 1 − 1/e ≈ 0.632, but quite recently a tight bound of α ≈ 0.745 was obtained. The case where F is unknown, such that the decision whether τ = t may depend only on the values of the random variables X1,..., Xt, is equally well motivated but has received much less attention. A straightforward guarantee for this case of α ≥ 1/e ≈ 0.368 can be derived from the solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from F , and show that even with o(n) samples α ≤ 1/e. On the other hand, n samples allow for a significant improvement, while O(n2) samples are equivalent to knowledge of the distribution: specifically, with n samples α ≥ 1 − 1/e ≈ 0.632 and α ≤ ln(2) ≈ 0.693, and with O(n2) samples α ≥ 0.745 − ϵ for any ϵ > 0.
Joint work with Jose Correa (Universidad de Chile), Felix Fischer (Queen Mary), and Kevin Schewior (ENS Paris)
Understanding and improving the performance of applications on NUMA systems by Vivien Quema (LIG)
– November 21, 2019
Understanding and improving the performance of applications on NUMA systems
Modern multicore systems are based on a Non-Uniform Memory Access (NUMA) design. Efficiently exploiting such architectures is notoriously complex. In this talk we will present different works we did during these last years to help application and system designers leveraging the power of these architectures. In particular, we will present some profiling tools that we used to detect inefficiencies and some algorithms/heuristics that we implemented within the Linux kernel to improve the performance of NUMA systems.
Back from Supercomputing by Bruno Raffin (Datamove)
– November 28, 2019
Bruno will present his report from the new trends he saw this year at supercomputing as well as explain some technical talks he liked presented at the conference.
Phd Defense: Autonomic Resilience of Distributed IoT Applications in the Fog, by Umar Ozeer (Polaris)
– December 11, 2019
Abstract:
Recent computing trends have been advocating for more distributed paradigms, namely Fog computing, which extends the capacities of the Cloud at the edge of the network, that is close to end devices and end users in the physical world. The Fog is a key enabler of the Internet of Things (IoT) applications as it resolves some of the needs that the Cloud fails to provide such as low network latencies, privacy, QoS, and geographical requirements. For this reason, the Fog has become increasingly popular and finds application in many fields such as smart homes and cities, agriculture, healthcare, transportation, etc.
The Fog, however, is unstable because it is constituted of billions of heterogeneous devices in a dynamic ecosystem. IoT devices may regularly fail because of bulk production and cheap design. Moreover, the Fog-IoT ecosystem is cyber-physical and thus devices are subjected to external physical world conditions which increase the occurrence of failures. When failures occur in such an ecosystem, the resulting inconsistencies in the application affect the physical world by inducing hazardous and costly situations.
In this Thesis, we propose an end-to-end autonomic failure management approach for IoT applications deployed in the Fog. The proposed approach recovers from failures in a cyber-physical consistent way. Cyber-physical consistency aims at maintaining a consistent behavior of the application with respect to the physical world, as well as avoiding dangerous and costly circumstances.
The approach was validated using model checking techniques to verify important correctness properties. It was then implemented as a framework called F3ARIoT. This framework was evaluated on a smart home application. The results showed the feasibility of deploying F3ARIoT on real Fog-IoT applications as well as its good performances in regards to end user experience.
Tropical approach to semidefinite programming and mean payoff games, by Mateusz Skomra (ENS Lyon)
– December 19, 2019
Semidefinite programming (SDP) is a fundamental tool in convex and polynomial optimization. It consists in minimizing linear functions over spectrahedra (sets defined by linear matrix inequalities). In particular, SDP is a generalization of linear programming. In this talk, we discuss the nonarchimedean analogue of SDP, replacing the field of real numbers by the field of Puiseux series. Our methods rely on tropical geometry and, in particular, on the study of tropicalization of spectrahedra. We show that, under genericity conditions, tropical spectrahedra encode Shapley operators associated with stochastic mean payoff games. As a result, a large class of semidefinite feasibility problems defined over Puiseux series can be solved efficiently using combinatorial algorithms designed for stochastic games. Conversely, we use tropical spectrahedra to introduce a condition number for stochastic mean payoff games. We show that this conditioning controls the number of value iterations needed to decide whether a mean payoff game is winning. In particular, we obtain a pseudopolynomial bound for the complexity of value iteration provided that the number of random positions is fixed.
The talk is based on joint works with X. Allamigeon, S. Gaubert, and R. Katz.
This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.
Strictly Necessary Cookies
Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.
If you disable this cookie, we will not be able to save your preferences. This means that every time you visit this website you will need to enable or disable cookies again.
