Events: Data- och informationsteknik events at Chalmers University of TechnologyFri, 19 Jan 2018 10:41:51 +0100 Chatterjee, Computer Science and Engineering<p>EA, lecture hall, EDIT trappa C, D och H, EDIT</p><p>​Lock-free Concurrent Search</p><img src="/SiteCollectionImages/Institutioner/DoIT/Profile%20pictures/NS/Bapi.png" class="chalmersPosition-FloatRight" alt="" style="margin:5px" />The contemporary computers typically consist of multiple computing cores with high compute power. Such computers make excellent concurrent asynchronous shared memory system. On the other hand, though many celebrated books on data structure and algorithm provide a comprehensive study of sequential search data structures, unfortunately, we do not have such a luxury if concurrency comes in the setting. The present dissertation aims to address this paucity. We describe novel lock-free algorithms for concurrent data structures that target a variety of search problems.<p></p> <br /><ol><li> Point search (membership query, predecessor query, nearest neighbour query) for 1-dimensional data: Lock-free linked-list; lock-free internal and external binary searchtrees (BST). </li> <li>Range search for 1-dimensional data: A range search method for lock-free ordered set data structures - linked-list, skip-list and BST. </li> <li>Point search for multi-dimensional data: Lock-free kD-tree, specially, a generic method for nearest neighbour search.</li></ol> We prove that the presented algorithms are linearizable i.e. the concurrent data structure operations intuitively display their sequential behaviour to an observer of the concurrent system. The lock-freedom in the introduced algorithms guarantee overall progress in an asynchronous shared memory system. We present the amortized analysis of lock-free data structures to show their efficiency. Moreover, we provide sample implementations of the algorithms and test them over extensive micro-benchmarks. Our experiments demonstrate that the implementations are scalable and perform well when compared to related existing alternative implementations on common multi-core computers.<p></p> <br /> Our focus is on propounding the generic methodologies for efficient lock-free concurrent search. In this direction, we present the notion of help-optimality, which captures the optimization of amortized step complexity of the operations. In addition to that, we explore the language-portable design of lock-free data structures that aims to simplify an implementation from programmer’s point of view. Finally, our techniques to implement lock-free linearizable range search and nearest neighbour search are independent of the underlying data structures and thus are adaptive to similar data structures.<p></p> <br /> Fougstedt, Computer Science and Engineering<p>EA, lecture hall, EDIT trappa C, D och H, EDIT</p><p>​High-throughput power-efficient DSP for fiber-optic communication systems</p> Salem, Computer Science and Engineering<p>SB-H5, lecture hall, Arkitektur, Campus Johanneberg</p><p>​Shared Resources in Distributed Systems: Analytical Tools for Evaluation and Self-stabilizing Provisioning</p><img src="/SiteCollectionImages/Institutioner/DoIT/Profile%20pictures/NS/Iosif.jpg" class="chalmersPosition-FloatRight" alt="" style="margin:5px" />Distributed computing is an established computing paradigm of modern computing systems.The nodes of a distributed system interact either by sharing resources or via a communication network. In both cases, provisioning of shared resources is a challenge, for example when resource demand and supply varies or when the system is prone to failures. Analytical tools for evaluating system performance and for provisioning shared resources enhance system design and implementations.<p></p> <br /> In this thesis, we develop analytical tools for the evaluation and self-stabilizing provisioning of shared-resources in distributed systems. We first focus on systems where resource demand and supply varies, and study cases of reusable and non-reusable resources. We study shared-object systems, where system nodes demand mutually exclusive access to a number of objects in a continuous fashion. We develop analytical tools for computing the expected delay and throughput of such systems, in a wide range of system utilization scenarios, including saturation points. Moreover, we study systems where nodes share energy resources, and focus on optimizing the available resources on a system-level. We develop online algorithms that use the flexibility on resource demand, to optimize the utilization of the available supply, and prove their competitive ratios.<p></p> <br /> Recovery from failures is necessary for provisioning shared resources. Dynamic and complex systems are often designed based on a failure model, but it is important that they recover even after the occurrence of unexpected failures, outside the failure model. Such failures can include topological changes in the network, stale information in the nodes' memory, communication failures, etc. These failures are further amplified by the system's asynchrony. In these settings, we first focus on provisioning of network resources, in terms of network control and ordering of distributed events. We study Software-Defined Networks (SDNs) and specifically their control planes. We provide a self-stabilizing distributed algorithm for a fault-tolerant SDN control plane, that deals with communication failures, topological changes, as well as, with transient faults, that can bring the system in an arbitrary state. Moreover, we focus on ordering distributed events in asynchronous message-passing systems, in the absence of execution fairness. In these extreme asynchronous settings, we provide a practically-self-stabilizing distributed algorithm, that uses bounded memory and yet, can tolerate concurrent counter overflows, when counting distributed events, as well as transient faults.<p></p> <br /> new interconnection model for overlay networks<p>Conference room EDIT, 3364, EDIT-building</p><p>​Talk by Christian Scheideler, University of Paderborn.</p><strong><br />Abstract </strong><br />An overlay network based on a set of nodes has a link from node A to B whenever A can send information directly (via some underlying physical network such as the Internet) to B (because A knows B or because B granted A the right to send information to it). Overlay networks are a standard approach to model and study communication in distributed systems. In this talk I will present a new model for the management of links of overlay networks based on so-called relays. <br />As I will demonstrate via several examples, this model has various benefits. It is now possible for the nodes to rigorously perform access control and to realize anonymity and pseudonyms where, a priori, it cannot be determined whether they belong to the same node or different nodes. Also, certain denial-of-service and man-in-the-middle attacks can now be handled with algorithmic methods, and some important problems such as the problem whether a node can leave an overlay network without disconnecting it can now be solved. Therefore, the relay concept seems to be a very useful model for future algorithmic research on overlay networks, and I am looking forward to discussing it with the audience. <br /> and Over the Air Testing<p>Provinn, Kvarnbergsgatan 2</p><p>​Microwave road invites Chalmers employees and students to an interesting seminar on 5G and over the air testing.</p>​ <br />PROGRAM<br />16.00 –16.30 Registration and Coffee<br />16.30–16.40 Introduction of MWR<br />16.40–17.00 Mats Högberg, Huawei ”5G and why do we need Over The Air requirements”<br />17.00–17.30 Wei Fan, Aalborg University “Over-the-air radiated performance testing of 5G radios”<br />17.30–17.40 Coffee break<br />17.40–18.10 Bengt Svensson, Saab “Antenna measurement challenges at Saab”<br />18.10–18.40 Klas Arvidsson, Bluetest ”OTA Reverberation chamber opportunities”<br />18.40–19.10 Madeleine Schilliger Kildal, Chalmers &amp; RanLOS<br />”The Random-LOS Measurement System for Vehicular Communication”<br />19.10 –21.00 Beverage, food and continuation with Over The Air discussions<br /><br /><br /><strong>R.S.V.P: 24th january 2018<span style="display:inline-block"></span></strong><br />Registration: <a href=""></a><br />Parking: Nordstan or The Opera House<br /><br />Microwave Road, <span><a href="" target="_blank"></a><span style="display:inline-block"></span></span> Petig, Computer Science and Engineering<p>EA, lecture hall, EDIT trappa C, D och H, EDIT</p><p>​Topics in Distributed Algorithms: On Wireless Networks, Distributed Storage and Streaming</p>Distributed algorithms are executed on a set of computational instances. We refer to these instances as nodes. Nodes are running concurrently and are independent from each other. Furthermore, they have their own instructions and information. In this context, the challenges are to show that the algorithm is correct, regardless of computational, or communication delays and to show bounds on the usage of communication. We are especially interested the behaviour after transient faults and under the existence of Byzantine nodes.<p></p> <br /> This thesis discusses fundamental communication models for distributed algorithms. These models are implementing abstract communication methods. First, we address medium access control for a wireless medium with guarantees on the communication delay. We discuss time division multiple access (TDMA) protocols for ad-hoc networks and we introduce an algorithm that creates a TDMA schedule without using external references for localisation, or time. We justify our algorithm by experimental results.<p></p> <br /> The second topic is the emulation of shared memory on message passing networks. Both, shared memory and message passing are basic interprocessor communication models for distributed algorithms. We are providing a way of emulating shared memory on top of an existing message passing network under the presence of data corruption and stop-failed nodes. Additionally, we ensure the privacy of the data that is stored in the shared memory. <p></p> <br /> The third topic looks into streaming algorithms and optimisation. We study the problem of sorting a stream ofvehicles on a highway with several lanes so that each vehicle reaches its target lane. We look into optimality in terms of minimising the number of move operations, as well as, minimising the length of the output stream. We present an exact algorithm for the case of two lanes and show that NP-Hardness for a increasing number of lanes.<p></p> <br /> Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in Polylogarithmic Time<p>EA, lecture hall, EDIT trappa C, D och H, EDIT</p><p>​Talk by Volker Turau, Hamburg University of Technology</p><strong><br />Abstract </strong><br />It is known for some time that a random graph $G(n,p)$ contains with high probability a Hamiltonian cycle if $p$ is larger than the critical value $p_{crit}= (\log n + \log \log n + \omega_n)/n$. The determination of a concrete Hamiltonian cycle is even for values larger than $p_{crit}$ a nontrivial task. In this talk, we present a distributed algorithm $A_{HC}$ that finds with high probability a Hamiltonian cycle in a graph $G(n,p)$ provided $p\ge \sqrt{1/n}$. The algorithm works in the synchronous model and uses messages of size $O(\log n)$ and $O(\log n)$ memory per node. Algorithm $A_{HC}$ terminates in $O(\log^2 n)$ rounds. If $p\ge \sqrt{\log n/n}$ then $A_{HC}$ even terminates in $O(\log n)$ rounds. This is a considerable improvement over existing work which assumed $p \ge \sqrt{\log n}/n^{1/4}$ and proposed an algorithm that terminates in linear worst-case number of rounds, requires $O(n^{3/4 + \epsilon})$ rounds on expectation, and uses $O(n)$ space per node. <br /> seminar on Digitalisation Security & privacy | Machine Intelligence<p>RunAn, conference hall, Kårhuset, Campus Johanneberg</p><p>On 15 March 2018 at Chalmers conference centre, Runan.</p>​ <br />At the 2018 initiative seminar on Digitalisation we focus on the two themes Security/Privacy and Machine Intelligence. <a href="/en/areas-of-advance/ict/events/Digitalisation2018/Pages/default.aspx">More information on the seminar webpage &gt;</a>