Some results with MWMR registers by H. Fauconnier
,
University Paris Diderot –
Abstract:
Abstract:
What is the number of registers required to solve a task? Many years ago, Ellen and al. have proved a lower bound of square root of n registers to (obstruction free) solve the consensus, but today there is no known consensus algorithm using less than n registers. In a system of n processes, if each process has its own SWMR register, it is possible to emulate any number of registers, but what of tasks can be solved with less than n registers?
Before considering this question, what’s happens when we only have MWMR registers? A trivial way may be to assign each process one MWMR: given an array C of MWMR registers, C[i] will be assigned to process i. But if the n processes have ids drawn from a very large set of N identifiers, the size of C depends on N not on n. Renaming algorithms may help but they use a non linear (on n) number of MWMR registers.
We give a solution without renaming that implements for each process a SWMR register using only n MWMR registers. This implementation is only non-blocking, but we get with 2(n-1) MWMR a wait-free implementation. Moreover we prove that n is a lower bound to such implementation. We also prove that n MWMR registers are sufficient to solve any wait-free task solvable with any number of (MWMR or SWMR) registers.
If the number of MWMR is less than n, we prove that some tasks may nevertheless been (obstruction-free) solved. For example, we prove that 2 registers are necessary and sufficient to (Obstruction-Free) solve the set-agreement problem.
This a joint work with C. Delporte, H. Fauconnier, E. Gafni and S. Rajbaum (ICDCN 2013). A recent extension to the adaptive case has been made jointly with L. Lamport ( DISC 2013)
Bio:
H. Fauconnier received his Ph.D. in 1982 and HDR degree in 2001 in Computer Science from the University Paris-Diderot, after Master degrees in Mathematics and Computer Science. He is a top level expert in Fault Tolerance Distributed Computing and he has published papers in many journals like JACM, Distributed Computing, TOPLAS and in top level conferences of this aera (PODC, DISC, DSN, ICDCS, …). He has been program committee members of established conferences in Distributed Computing such as PODC, DISC, IEEEE ICDCS, OPODIS…He is currently at LIAFA, University Paris Diderot.
Date: 2013-Dec-04 Time: 11:00:00 Room: 336
For more information:
Upcoming Events
Seminar: Combining Reasoning and Learning for Discovery
07 June, 1.30pm, at Sala José Tribolet in Pavilhão Informática II at IST.
Artificial Intelligence (AI) is a rapidly advancing field inspired by human intelligence. AI systems are now performing at human and even superhuman levels on various tasks, such as image identification, face and speech recognition, and chatbots such as chatGPT. The tremendous AI progress that we have witnessed in the last decade has been largely driven by deep learning advances and heavily hinges on the availability of large, annotated datasets to supervise model training. However, often we only have access to small datasets and incomplete data. We amplify a few data examples with human intuitions and detailed reasoning from first principles and prior knowledge for discovery. I will talk about our work on AI for accelerating the discovery for new solar fuels materials, which has been featured in Nature Machine Intelligence, in a cover article entitled, Automating crystal-structure phase mapping by combining deep learning with constraint reasoning [1]. In this work, we propose an approach called Deep Reasoning Networks (DRNets), which seamlessly integrates deep learning and reasoning via an interpretable latent space for incorporating prior knowledge. and tackling challenging problems. DRNets requires only modest amounts of (unlabeled) data, in sharp contrast to standard deep learning approaches. DRNets reach super-human performance for crystal-structure phase mapping, a core, long-standing challenge in materials science, enabling the discovery of solar-fuels materials. DRNets provide a general framework for integrating deep learning and reasoning for tackling challenging problems. For an intuitive demonstration of our approach, using a simpler domain, we also solve variants of the Sudoku problem. The article DRNets can solve Sudoku, speed scientific discovery [2] provides a perspective for a general audience about DRNets. DRNets is part of SARA, the Scientific Reasoning Agent for materials discovery [3]. Finally, I will also talk about the effectiveness of a novel curriculum learning with restarts strategy to boost a reinforcement learning framework [4]. We show how such a strategy is characterized by left heavy-tails and can outperform specialized solvers for Sokoban, a prototypical AI planning problem.
Professor Carla P. Gomes: Department of Computer Science, Cornell University
Carla Gomes is the Ronald C. and Antonia V. Nielsen Professor of Computing and Information Science, the director of the Institute for Computational Sustainability at Cornell University, and co-director of the Cornell University AI for Science Institute. Gomes received a Ph.D. in computer science in artificial intelligence from the University of Edinburgh. Her research area is Artificial Intelligence with a focus on large-scale constraint reasoning, optimization, and machine learning. Recently, Gomes has become deeply immersed in research on scientific discovery for a sustainable future and, more generally, in research in the new field of Computational Sustainability. Computational Sustainability aims to develop computational methods to help solve some of the key environmental, economic, and societal challenges to help put us on a path toward a sustainable future. Gomes was the lead PI of two NSF Expeditions in Computing awards. Gomes has (co-)authored over 200 publications, which have appeared in venues spanning Nature, Science, and a variety of conferences and journals in AI and Computer Science, including five best paper awards. Gomes was named the “most influential Cornell professor” by a Merrill Presidential Scholar (2020). Gomes was also the recipient of the Association for the Advancement of Artificial Intelligence (AAAI) Feigenbaum Prize (2021) for “high-impact contributions to the field of artificial intelligence, through innovations in constraint reasoning, optimization, the integration of reasoning and learning, and through founding the field of Computational Sustainability, with impactful applications in ecology, species conservation, environmental sustainability, and materials discovery for energy” and of the 2022 ACM/AAAI Allen Newell Award, for contributions bridging computer science and other disciplines. Gomes is a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI), a Fellow of the Association for Computing Machinery (ACM), and a Fellow of the American Association for the Advancement of Science (AAAS).
INESC-ID ESR Talks – June 2023
If you are a masters/PhD student or a postdoctoral fellow, come and present your work in an informal and friendly environment – and savour some tasty snacks!
Individual talks will be 10-15 minutes plus time for feedback. Enroll on your selected date by emailing pedro.ferreira[at]inesc-id.pt.
Happening on the second Wednesday of every month (4pm-5pm):
- 14 June (Alves Redol, Room 9)
- 12 July (Alves Redol, Room 9)
We hope to see you there!
OLISSIPO Summer School in Lisbon | Computational phylogenetics to analyse the evolution of cells and communities
We are happy to announce the OLISSIPO Summer School on Computational phylogenetics to analyse the evolution of cells and communities, which will be held in Lisbon, Portugal, at INESC-ID, between July 2-7, 2023.
Keynote speakers:
David Posada, University of Vigo (class)
João Alves, University of Vigo (hands-on)
Nadia El-Mabrouk, Université de Montréal (class)
Mattéo Delabre, Université de Montréal (hands-on)
Ran Libeskind-Hadas, Claremont McKenna College (class and hands-on)
Russell Schwartz, Carnegie Mellon University (class and hands-on)
See the preliminary agenda at: https://olissipo.inesc-id.pt/tree-tango-school
Registration is mandatory. You can register at: https://forms.gle/VsASFHW5E7MJvaCc9
The registration fee is 250€ for students and OLISSIPO members and 350€ for postdocs or other researchers (meals indicated at the schedule of the school are included, accommodation and flights are not). All details will be made available upon registration.
We will have slots for flash talks (3-10 min depending on the number of submissions) to present yourself and the work you have been developing in your research.
The 13th Lisbon Machine Learning School | LxMLS 2023
The Lisbon Machine Learning Summer School (LxMLS) takes place yearly at Instituto Superior Técnico (IST). LxMLS 2023 will be a 6-day event (14-20 July, 2023), scheduled to take place as an in-person event.
The school covers a range of machine learning topics, from theory to practice, that are important in solving natural language processing problems arising in different application areas. It is organized jointly by Instituto Superior Técnico (IST), a leading Engineering and Science school in Portugal, the Instituto de Telecomunicações, the Instituto de Engenharia de Sistemas e Computadores, Investigação e Desenvolvimento em Lisboa (INESC-ID), the Lisbon ELLIS Unit for Learning and Intelligent Systems (LUMLIS), Unbabel, Zendesk, and IBM Research.
Check online for information about past editions: LxMLS 2011, LxMLS 2012, LxMLS 2013, LxMLS 2014, LxMLS 2015, LxMLS 2016, LxMLS 2017, LxMLS 2018, LxMLS 2019, LxMLS 2020, LxMLS 2021, LxMLS 2022 (you can also watch the videos of the lectures for 2016, 2017, 2018, and 2020).
31st International Conference on Information Systems Development (ISD 2023)
The 31st International Conference on Information Systems Development (ISD 2023) conference provides a forum for research and developments in the field of information systems. The theme of ISD 2023 is “Information systems development, organizational aspects and societal trends”. New trends in developing information systems emphasize the continuous collaboration between developers and operators in order to optimize the software delivery time. The conference promotes research on methodological and technological issues and how IS developers and operators are transforming organizations and society through information systems.
The ISD 2023 conference held this year also provides an opportunity for researchers and practitioners to promote their research, practical experience, and to discuss issues related to Information Systems through papers, posters, and journal-first paper presentations.
ISD 2023 will be hosted by Instituto Superior Técnico, in Lisbon, Portugal, on August 30–September 1, 2023.