Compact Self-Healing and Routing Over Low Memory Nodes (COSHER)

Lead Research Organisation: Loughborough University
Department Name: Computer Science

Abstract

Computer Networks have permeated every sphere of our lives. For example, the Internet has almost instantaneously taken over global communications and networks now pervade every part of our professional, personal and social life. A major part of this revolution is computing devices coming together in an ad-hoc manner in the form of Peer-to-Peer (P2P) overlay networks. A good example is the digital currency Bitcoin built upon P2P technology. The next step in this revolution is the Internet of Things (IOT) which will involve everyday objects of our use fitted with small low memory sensors communicating with each other forming adhoc Peer-to-Peer networks. Such networks will also be highly dynamic with frequent additions, removals or failures of nodes.
In this scenario, my project will initiate research into the development of fault-tolerant routing for such large scale networks of devices with low memory. We plan to achieve this by developing mathematically rigorous novel compact self-healing routing distributed algorithms leveraging the intense research done in previous years in compact routing and in self-healing algorithms.

Self-healing is a paradigm for reconfigurable networks that restores the global state of a network by only local changes following an adversarial attack, and allows us to deal with node removals or additions. Routing is the essential requirement in any network of being able to transport packets of data from sender node(s) to receiver node(s) often using packet headers and routing tables on intermediate nodes. Compact routing attempts to make routing scalable for large networks by minimising the space requirements at the cost of some additional delay in delivery (this is called 'stretch'). In this proposal, I plan to design a series of self-healing compact routing algorithms for nodes with low memory. These algorithms shall be mathematically analysed and bench-tested for accuracy and efficiency (in terms of time, space and message complexities).

I will actively disseminate our algorithms and generate increased scientific interest in Queen's, the larger academic community and the general public towards this line of work. Success in development of such algorithms will have significant impact down the line in development of such technologies and contribute towards preparing the UK for technologies such as IOT.

Planned Impact

The project has significant potential impact in the short, medium and long term. This project uses mathematical and theoretical tools to address a challenging problem for present and future days network: that of sending messages in a network despite failures of members/components of that network. The project is relavant to many of EPSRC's research areas and themes such as the ICT Networks and Distributed Systems (ICT/Global Uncertainities/Digital Economy), Working together and Maths of Computing.

Impact will be achieved by activities such as training, publications, participation in meetings/conferences/fairs/forums, student projects, demonstrations, websites, social platforms and engagement with policy planners and advisors. The impact can be classified into the following categories with the given timeframes:

i) Impact on individuals (< 5 years):
- PI: The project shall help the PI cement his research credentials and achieve a more secure (post-probation) position in the UK academia.
-PDRA: Shall be most directly impacted. PDRA shall receive significant scientific, professional and managerial training during the course of the project from the research, interaction with the PI and specialised training from QUB and the Royal Society (Communications course).
- QUB and UK students: These shall benefit from resultant UG/PG projects and dissemination activities at local/national level (Open days/national seminars).
- UK/International academics: The project shall advance the state of art and disseminate in international conferences.

ii) Organisations (2 - 10 years):

- Industry: The project will propose solutions at a higher/theoretical level (for a seminal problem) which takes time to be adapted/adopted/implemented for industrial use. At the same time, the resultant fan out ensures a much higher impact than a single tailor made solution. The project impacts areas such as large scale networks and Internet of Things which will see wide adoption by industry ranging from Computing (Google, facebook etc) to electricity and power to automobiles. Solutions based on our results may potentially be adopted by any or all of them.

- Government (planning): The project shall maintain already established contact with government agencies such as RaISe (Northern Ireland) and POST (Westminster); agencies which are assisting in research planning and adoption of future technologies. This shall assist in maximising the impact across organisations and general public.

iii) General public (> 5 years): Technologies already in use and those to be adopted in near future (such as IOT) will be potentially impacted; this will benefit everyday life. Possible adaptation of concepts into text book and curricula will have lasting impact. Dissemination and outreach activities (such as open days/demonstrations etc) shall influence the next generation of students.

The 'pathways to Impact' document has more details.

Publications

10 25 50
publication icon
CastaƱeda A (2018) Self-healing Routing and Other Problems in Compact Memory in ArXiv e-prints

 
Description The project is in progress and is on schedule meeting the objectives as planned. The key development so far is development of a theoretical model (titled `compact memory model') for reasoning about large networks of low memory nodes and solving the problem of preprocessing for the first compact self-healing algorithm. We have also developed an early version of an educational and research oriented simulation software.
Exploitation Route The model (`compact memory model') has strong potential of influencing research if it is accepted by the research community as a useful model. As part of our research, we are moving on to development of the next (and more sophisticated) algorithms addressing more dynamic scenarios.
Sectors Digital/Communication/Information Technologies (including Software),Education,Other

URL https://arxiv.org/abs/1803.03042
 
Title Compact Memory Model and related algorithms 
Description We have invented a new model called the 'Compact Memory Model' to model large networks of low memory nodes and use this model to propose novel distributed algorithms. This model is envisaged to capture many features of upcoming networks such as the Internet of Things. 
Type Of Material Computer model/algorithm 
Year Produced 2018 
Provided To Others? Yes  
Impact The model is part of a conference submission (and an Arxiv preprrint) hence it's difficult to assess the impact at the moment. 
URL https://arxiv.org/abs/1803.03042
 
Description Research Collaboration (Mexico, Israel) 
Organisation Hebrew University of Jerusalem
Department School of Computer Science and Engineering
PI Contribution The PI initiated the project in collaboration with researchers, Prof. Danny Dolev at HUJI and Dr. Armando Castanader at UNAM. The final draft of the application was in fact written while visiting Dr. Castaneda at UNAM, Mexico as part of a Newton Fund travel grant. The PI and RA Dr. Lefevre have been in continuous touch and working actively on this collaboration.
Collaborator Contribution Prof. Dolev was the advisor of the PI (Dr. Trehan) while Dr. Trehan was an I-CORE (Israeli Centre of Research Excellence) fellow at Hebrew University of Jerusalem. He has actively contributed in developing the initial idea and has acted as an advisor and mentor to this project. Dr. Castanader has likewise been active in the research leading upto this grant and both were co-authors with the PI on the publication which formed the initial basis of the grant application. Dr. Castanader has since actively contributed to the research on this grant and has visited the research group at Loughborough at his own expense for 10 days (making an additional in-kind contribution) to work on this research.
Impact A paper titled 'Self-healing Routing and Other Problems in Compact Memory' has been submitted to PODC 2018 and has been put up on Arxiv - https://arxiv.org/abs/1803.03042
Start Year 2016
 
Description Research Collaboration (Mexico, Israel) 
Organisation National Autonomous University of Mexico
Country Mexico 
Sector Academic/University 
PI Contribution The PI initiated the project in collaboration with researchers, Prof. Danny Dolev at HUJI and Dr. Armando Castanader at UNAM. The final draft of the application was in fact written while visiting Dr. Castaneda at UNAM, Mexico as part of a Newton Fund travel grant. The PI and RA Dr. Lefevre have been in continuous touch and working actively on this collaboration.
Collaborator Contribution Prof. Dolev was the advisor of the PI (Dr. Trehan) while Dr. Trehan was an I-CORE (Israeli Centre of Research Excellence) fellow at Hebrew University of Jerusalem. He has actively contributed in developing the initial idea and has acted as an advisor and mentor to this project. Dr. Castanader has likewise been active in the research leading upto this grant and both were co-authors with the PI on the publication which formed the initial basis of the grant application. Dr. Castanader has since actively contributed to the research on this grant and has visited the research group at Loughborough at his own expense for 10 days (making an additional in-kind contribution) to work on this research.
Impact A paper titled 'Self-healing Routing and Other Problems in Compact Memory' has been submitted to PODC 2018 and has been put up on Arxiv - https://arxiv.org/abs/1803.03042
Start Year 2016
 
Title COSHER- Simulation 
Description This software is a simulation tool for the algorithms developed under the COSHER project. This software will be useful both for experimental validation and insights into the algorithms and also as an educational tool for developing understanding when fully developed. 
Type Of Technology Software 
Year Produced 2018 
Impact The product has so far informed development of the theoretical algorithms for the research team but will be able to have a larger educational impact when fully developed. 
 
Description Departmental Seminar, CS, Royal Holloway University of London 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Professional Practitioners
Results and Impact Department Seminar, Computer Science, Royal Holloway University of London. The PI presented the initial research from the project at the seminar. There were questions from the audience. There was also follow up in the form of email from students asking about technical aspects of the project and follow up research.
Year(s) Of Engagement Activity 2017
URL https://www.royalholloway.ac.uk/computerscience/events/eventsarticles/seminar-amitabh-trehan.aspx
 
Description The Royal Society Residential Communication and Media Skills Course 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact The Royal Society Residential Communication and Media Skills Course Nov 13-14, 2017. This course had attendees from Universities from UK and other countries with extensive training on using communication and media for scientific writing. The PI and the RA on the project (Dr. Lefevre) both attended. The major outcome from the workshop was the development of project website www.cosher.org and writing on the PI's blog www.huntforthetowel.wordpress.com.
Year(s) Of Engagement Activity 2017
URL http://www.royalsociety.org
 
Description Visit, Research and Seminar by Dr. Armando Castaneda, UNAM, Mexico 
Form Of Engagement Activity Participation in an open day or visit at my research institution
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Dr. Castaneda visited us (Loughborough) from Oct 18th to 30th with an objective of initiating and furthering research on the project (COSHER) and interacting with colleagues and students here. It was a very successful visit laying the foundation of a research paper we are close to publishing. Armando also gave a seminar talk which generated good interest and feedback from attending students.
Year(s) Of Engagement Activity 2017
 
Description Visti to the Parametrised Complexity Research group, University of Bergen 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact One week visit to the research group on Parametrised complexity at University of Bergen, Bergen, Norway. This visit was hosted by Prof. Saket Saurabh and the intention was to explore further research possibilities combining the active research areas of distributed algorithms (such as that in Cosher) with Parametrised algorithms (which is now a well established research area). From the UK, the PI (Dr. Trehan), the RA on Cosher grant (Dr. Lefevre) and PhD student Chhaya Trehan. Dr. Trehan and Dr. Lefevre gave a series of lectures and talks over the week to the researchers (`professors and graduate and postgraduate students) from the group. The research group at Bergen has expressed interest in continuing and following up on collaboration and collaborative research.
Year(s) Of Engagement Activity 2017
URL https://huntforthetowel.wordpress.com/2017/10/03/a-week-in-bergen/
 
Description Website: www.cosher.org 
Form Of Engagement Activity Engagement focused website, blog or social media channel
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Media (as a channel to the public)
Results and Impact The website www.cosher.org was designed for outreach and dissemination from the project including publications, news and educational simulation.
Year(s) Of Engagement Activity 2017,2018
URL http://www.cosher.org