Counting, clocking and colouring: Fault-tolerant distributed coordination

Lecturer : 
Joel Rybicki
Event type: 
Doctoral dissertation
Doctoral dissertation
Respondent: 
Joel Rybicki
Opponent: 
Professor Roger Wattenhofer, ETH Zurich, Switzerland
Custos: 
Professor Jukka Suomela, Aalto University School of Science, Department of Computer Science
Event time: 
2016-11-19 12:00 to 15:00
Place: 
lecture hall SOK A301 of the Aalto University Töölö Campus Main building, Runeberginkatu 14-16, Helsinki
Description: 

Abstract

This thesis studies fault-tolerant co-ordination and synchronisation in distributed systems. Such systems are prevalent in computing today: they range from large-scale communications networks to integrated hardware circuits. In essence, a distributed system consists of independent computational entities called nodes that solve some task together. In such a system, a common notion of time is critical for ensuring correct co-ordination and scheduling of actions.

However, distributed systems are prone to scenarios in which the system may experience arbitrary transient failures, for example, due to various external disruptions. During a transient failure, the system ceases to operate correctly for some time which may put the system into an inconsistent state or even permanently damage parts of the system. In particular, the nodes in the system can lose synchrony. This thesis proposes synchronisation and scheduling algorithms that efficiently recover from such failures.

The first part of this thesis considers self-stabilising Byzantine fault-tolerant algorithms. This means that we assume a strong adversarial fault model: the system starts from an arbitrary initial state and a large fraction of the nodes may be faulty. The faulty nodes may exhibit arbitrary misbehaviour, and in particular, give inconsistent information to other nodes. In this setting, we study the synchronous counting problem, which is a basic primitive for establishing a so-called digital clock. The task is to guarantee that eventually all correct nodes 

The main contribution of the first part is an array of techniques for designing fast and communication-efficient counting algorithms. In particular, we provide deterministic algorithms with asymptotically optimal stabilisation time and optimal resilience. That is, the algorithms quickly converge to correct behaviour and tolerate the largest possible number of faulty nodes. Compared to prior work, our solutions give an exponential improvement in the number of bits stored and transmitted by each node without resorting to randomisation or suboptimal resilience.

The second part of this thesis investigates computational algorithm design and synthesis techniques. That is, we show how to automatically construct correct algorithms or prove their non-existence using computers. This is particularly attractive in the context of fault-tolerant systems, in which finding correct solutions is often a difficult task. We propose synthesis techniques based on propositional satisfiability solvers that yield novel state-optimal counting algorithms and tight bounds on the exact time complexity of distributed graph colouring.

ULTRAHACK 2016 - Invitation to Apply

Event type: 
Event
Event time: 
2016-11-25 09:00 to 2016-11-27 17:00
Place: 
Vallilan Konepaja Bruno, Helsinki
Description: 

Applications for the Ultrahack Main Event are now open! 

Solve meaningful challenges, showcase your talent and network with key industry players and talented developers all over the globe. Unlike in any other hackathon, you may also get funding and access to accelerator programs during the Ultrahack tournament. This year we feature eight main challenges such as Fintech, Media, Health and Mobile Networks – and the latest tech like cognitive computing. Apply now and see where Ultrahack can take you!

We welcome applications from teams and individuals alike. Coding experience is not mandatory, since we have different roles available. 

See the full list of Ultrahack challenges and and apply now.

Ultrahack is an international innovation contest and hackathon tournament in which student teams, hacktivists, entrepreneurial minds, start-ups and corporations solve up-to-date challenges with the latest technologies. 

Search&Beyond, Kal Järvelin UTA, Andrew Howes UoB, Rob Capra UNC, Distinguished Speakers, HelsinCHI

Lecturer : 
Kal Järvelin UTA, Andrew Howes UoB, Rob Capra UNC
Event type: 
Guest lecture
Doctoral dissertation
Respondent: 
Opponent: 
Custos: 
Event time: 
2016-10-11 14:00 to 16:00
Place: 
Auditorium XIV, 3. floor, Päärakennus, Unioninkatu 34
Description: 

Search&Beyond, Distinguished Speakers, HelsinCHI



14:00 Welcome and Introduction

Giulio Jacucci, University of Helsinki 

Kalervo Järvelin, University of Tampere

14:30 Interfaces to Support Exploratory and Collaborative Search Tasks 

Rob Capra, University of North Carolina at Chapel Hill

15:00 The rational basis of sequential search for information

Andrew Howes, University of Birmingham

15:30 Concluding Remarks

Title: Interfaces to Support Exploratory and Collaborative Search Tasks
Search interfaces are used by millions of users every day and provide access to a vast array of information stored in web pages, document collections, and other data sources. The design of these interfaces mediates access to information and can influence our search processes. Search interfaces have evolved over time, but providing high-precision ranked lists of results is a primary focus of many systems. Current search engines are effective in helping users complete simple search tasks such as fact-finding, but provide less support in helping users with tasks that may involve exploration, analysis, comparison, evaluation, and collaboration.
In this talk I will present results from a series of projects conducted with colleagues to develop and evaluate innovative search interfaces to support exploratory and collaborative search tasks. Across these projects, we observed how interface components influenced users’ search behaviors and ways that users made use of contextual information displayed by the interfaces at different stages of their search processes. In my recent work, these observations helped inform the design of a novel search assistance tool that displays the search trails (paths) from previous users. The idea behind the tool is that users may benefit from seeing how someone else approached the same or similar task. Our implementation provides an interactive display with information about how another person searched, the queries they issued, results they clicked, and annotations made by the original searcher. I will report on a laboratory study that investigated factors that influence user interaction with the search trails and effects on outcome measures. Finally, I will conclude by discussing several exciting areas for future research on search interfaces.

Dr. Robert Capra is an Assistant Professor in the School of Information and Library Science at the University of North Carolina at Chapel Hill. His interests include human-computer interaction, interactive information retrieval, and personal information management. His research focuses on how people search for information in different contexts and on developing tools to support users’ search needs. He publishes regularly in top computer and information science conferences and journals and in 2016 was awarded a prestigious National Science Foundation CAREER grant.
He holds a Ph.D. in computer science from Virginia Tech and Master’s and Bachelor’s degrees in computer science from Washington University in St. Louis. At Virginia Tech, he was part of the Center for Human-Computer Interaction where he investigated multi-platform interfaces, information re-finding, and interfaces for digital libraries. Prior to Virginia Tech, he worked in corporate research and development, spending five years in the Speech and Language Technologies group at SBC Communications (now merged with AT&T Labs) where he focused on voice user interfaces, speech recognition, and natural language processing.
Dr. Capra is an active member in the HCI and information science communities. He has co-edited special issues of IEEE Computer, ACM Transactions on Information Systems (TOIS), and the journal Information Processing & Management. He has served on numerous conference program committees and in 2016, was co-chair of the newly formed ACM SIGIR Conference on Human Information Interaction and Retrieval (CHIIR).

Andrew Howes is Professor of Computer Science at University of Birmingham and Marshall Weinberg visiting professor at the University of Michigan. He has previously held academic posts at the University of Manchester, Cardiff University, Carnegie-Mellon University and the Medical Research Council, Cambridge. He is known for his work in Cognitive Science and Human-Computer Interaction and he focuses on computational rationality, that is in computational models of human behaviour that adapt to human cognitive capacities, as well as to the statistical structure of the environment. His recent book offers a general integrative framework for understanding human interaction with technology (Payne and Howes, 2013). Professor Howes is an Associate Editor at the International Journal of Human-Computer Studies and Cognitive Science journal. He has been an Associate Chair for ACM SIGCHI for a number of years and he is program chair for the Annual Meeting of the Cognitive Science Society (2017). His work has recently been funded by NASA (2015), by the US Air Force Research Laboratory (2013-2015), by the EU (SPEEDD: FP7-ICT-2013-11 2013-2017), and by the ESRC (ES/L00321X/1 2012-2014). A recent series of publications provide a start at over-turning the long held, and popular, misconception that human preferences are irrational (Howes et al, 2016). Inspired by work in machine learning, Howes and colleagues' Bayesian model of bounded optimal decision making shows when people make rational changes of preference (e.g. to a lottery with higher expected value but more risk). The work has potential applications in understanding the choices that people make with and through technology, for example, Lelis and Howes (2011). It also has the potential to provide a theoretical underpinning to recent interest in the use of information technology to drive behaviour change. Another contribution has been to show how framing the visual search problem faced by humans as a Partially Observable Markov Decision Problem can be used to explain otherwise puzzling phenomena in Human-Computer Interaction (Chen et al., 2015). Humans can only partially observe state because of the combined limitations of information visualisation technologies and the acuity of the human eye. With his colleagues, Howes's work shows how reinforcement learning methods can be used to predict the eye movement strategies deployed by users.

 

Information Search as Adaptive Interaction

Lecturer : 
Kumaripaba Athukorala
Event type: 
Doctoral dissertation
Doctoral dissertation
Respondent: 
Kumaripaba Athukorala
Opponent: 
Assistant Professor Robert Capra, University of North Carolina at Chapel Hill, USA
Custos: 
Professor Giulio Jacucci, University of Helsinki
Event time: 
2016-10-12 12:00 to 15:00
Place: 
Auditorium XIII, University Main building, Unioninkatu 34, Helsinki
Description: 

Abstract in English:

We use information retrieval (IR) systems to meet a broad range of information needs, from simple ones involving day-to-day decisions to complex and imprecise information needs that cannot be easily formulated as a question. In consideration of these diverse goals, search activities are
commonly divided into two broad categories: lookup and  exploratory. Lookup searches begin with precise search goals and end soon after reaching of the target, while exploratory searches center on learning or investigation activities with imprecise search goals. Although exploration is a prominent life activity, it is naturally challenging for users because they lack domain knowledge; at the same time, information needs are broad, complex, and subject to constant change. It is also rather difficult for IR systems to offer support for exploratory searches, not least because of the complex information needs and dynamic nature of the user. It is hard also to conceptualize exploration distinctly. In consequence, most of the popular IR systems are targeted at lookup searches only. There is a clear need for better IR systems that support a wide range of search activities.
 
The primary objective for this thesis is to enable the design of IR systems that support exploratory and lookup searches equally well.  I approached this problem by modeling information search as a rational adaptation of interactions, which aids in clear conceptualization of exploratory and lookup searches. In work building on an existing framework for examination of adaptive interaction, it is assumed that three main factors influence how we interact with search systems: the ecological structure of the environment, our cognitive and perceptual limits, and the goal of optimizing the tradeoff between information gain and time cost. This thesis contributes three models developed in research proceeding from this adaptive interaction framework, to 1) predict evolving information needs in exploratory searches, 2) distinguish between exploratory and lookup tasks, and 3) predict the emergence of adaptive search strategies. It concludes with development of an approach that integrates the proposed models for the design of an IR system that provides adaptive support for both exploratory and lookup searches.
 
The findings confirm the ability to model information search as adaptive interaction. The models developed in the thesis project have been empirically validated through user studies, with an adaptive search system that emphasizes the practical implications of the models for supporting several types of searches. The studies conducted with the adaptive search system further confirm that IR systems could improve information search performance by dynamically adapting to the task type. The thesis contributes an approach that could prove fruitful for future IR systems in efforts to offer more efficient and less challenging search experiences.

HIIT Kumpula Seminar: Using SAT to solve stable matching problems with couples

Lecturer : 
Fahiem Bacchus
Event type: 
HIIT seminar
Doctoral dissertation
Respondent: 
Opponent: 
Custos: 
Event time: 
2016-09-30 10:15 to 11:00
Place: 
Exactum B119
Description: 

Abstract:Stable matching problems are common in many application areas, e.g., matching doctors into hospital programs. These problems involve finding a matching between two groups of agents. The matching must be stable in the sense that it must be immune to unilateral defections (i.e., defections involving a pair of agents, one from each group). The classical algorithm for finding stable matchings is the deferred acceptance algorithm of Gale and Shapely (DA). When each agent has preferences independent of the other agents, DA runs in polynomial time, always finds a stable matching, and has a number of other nice properties. However, when complementarities exist between agent's preferences finding a stable matching often becomes NP-Complete. The practically important hospital residence matching problem, where residents might be grouped into couples who have shared preferences (SMP-C), is an example of an NP-Hard stable matching problem. In this talk we examine SAT and IP encodings for solving SMP-C. We arrive at a SAT encoding that works well in practice, and better than the IP encoding. We use the SAT encoding to investigate empirically the set of stable matches for matching problems generated according to different distributions.

This is joint work with Joanna Drummond and Andrew Perrault, both from the University of Toronto.

Bio: Fahiem Bacchus is a professor of computer science at the University of Toronto. His research fits broadly in the area of knowledge representation and reasoning, a subfield of artificial intelligence. He has made a number of key contributions during his career, including the development of logics for representing different forms of probabilistic knowledge and automated planning algorithms that can exploit domain specific control knowledge expressed in linear temporal logic (LTL). For the past 15 years his work has concentrated on automated reasoning algorithms for solving various forms of the satisfiability problem: finding a model (SAT), counting the number of models (#SAT), solving quantified Boolean formulas (QBF), and finding optimal models (MaxSAT). His group has been successful in building award winning solvers for all of these problems. He has served as the program chair of several major AI conferences, including Uncertainty in AI (UAI), the International Conference on Automated Planning and Scheduling (ICAPS) and the International Conference on Theory and Applications of Satisfiability Testing (SAT); and will serve as conference chair of IJCAI-17. Fahiem is also a Fellow of the Association for the Advancement of AI (AAAI).

Pages