Randomized Algorithms for Computer Networks

Lead Research Organisation: King's College London
Department Name: Informatics

Abstract

The basic theme of this research is how to use randomized algorithms to improve network exploration, organisation and structure. The good thing about randomized algorithms is that they are easy to visualise and implement, and are often highly effective both in theory and in practice.

In the case of networks, these algorithms can often be modelled by particles moving more or less randomly on the network. The word particle is a generic term for agents, messages, robots. We assume the particles are used with a distinct purpose in relation to the network. Examples include searching the network, modifying its structure, passing messages or opinions between vertices of the network, distributing or hiding information, or validating the integrity of the network structure and content. The outcome of this process, although random in detail, is designed to do useful work. Moreover the particles are assumed to be cheap and to impose low processing costs on the network, so that the desired results can be obtained easily.

The remarkable fact about randomized algorithms, is that although the local behaviour is random, the global outcome is often quite predictable. With all randomized algorithms, the work is in the intellectual design of the process rather than its deployment in practice. It seems to us that it is best to have a well designed product which is simple and easy to use. Moreover, such processes are often very robust, and will continue to work effectively in practice in situations more general than the ones they were designed for.

Many large networks can be found in modern society, and obtaining information about these networks, or improving their functionality is an important problem. Examples of such networks include the world wide web, connections between internet routers, peer to peer networks, social networks (Twitter, Facebook) , and repositories of videos, photos (YouTube, Flickr) etc. Such networks are very large, change over time and are essentially unknowable or do not need to be known in detail.

Searching, sampling and ordering the content of such networks is a major application area and a substantial user of computer time. The evolving use of these networks is changing social behaviour, and improving our ability to explore such networks is of value to us all.

Random walks are a good example of a randomized algorithm. They are a simple method of network exploration, and are particularly suitable for searching massive networks. A random walk traverses a network by moving from its current position to a neighbouring vertex chosen at random. Decisions about where to go next can be taken locally, and only limited resources are needed for the search. The exploration is carried out in a fully distributed manner, and can adapt easily to dynamic networks. The long run behaviour of the walk acts as a distributed voting mechanism, in which the number of visits to a vertex is proportional to its popularity or accessability.

Fundamental questions are: At any time how much of the network has the walk seen, and what is the structure of the part left behind? Are there large chunks of the network which have been completely ignored, or are the unvisited fragments rather small and of uniform size? How can we alter the behaviour of the walk to improve uniformity of searching, or to reduce search time? How can we use information gleaned by the walk to improve the quality of recommendations provided about the system?

Speeding up random walks to reduce search time, or altering their behaviour to make searching more uniform and effective are fundamental questions in the theory of computing. The price of these improvements is typically some extra work which is performed locally by the walk. It is important to understand how well this can be done, as it can be useful in practice.

Planned Impact

Our research opens new directions in the study of randomized algorithms on networks, and inspires possible new applications.

In the past two decades the way we access information and services on a day to day basis has changed beyond recognition. Searching large networks to extract information content is a major data processing application, and the efficiency of search engine design, for example, is a matter of concern to all. Our use of online networks affects the way we communicate ideas, organise our lives and make personal choices. Their performance however is sometimes less than perfect. Although they offer an easy way to go shopping, for example, the range of products they suggest often seems out of line with our personal tastes or immediate needs.


This research has potential for impact on the design of information search and retrieval in the \WWW, the latency and robustness of the internet, and the autonomous construction and evolution of peer-to-peer networks for file sharing and distribution of music or films, and the quality of recommendations on social networks. In today's world, the world wide web; its related infrastructure, the internet; and autonomous and social networks such as Facebook and Twitter are a major industry. The successful entrepreneurs of the future will be those who develop the most appropriate apps for our tablet phones. The evolution and refinement of these networks will define the way our world function be in the future, and 10 or 20 years time we can expect it to have changed almost unrecognisably.

The research can have applied impact in many areas. Specific examples include the following:

Information and social networks.
Improved searching of networks for location of files and web page information content can lead to reduced processing overheads, improved web crawling strategies, improved file indexing and decreased user response times in queries on search engines and social network pages. It can lead to more effective methods of viral advertising in networks such as Twitter. Viral advertising can be seen as a particle process on the Twitter network.

Ad-hoc and peer-to-peer networks.
Our research can lead to better methods for the distributed structuring and maintenance of networks, leading to improved distribution and retrieval of fragmented data files (such as films, music etc), with the consequent reduction in processing and response time. This is particularly important for ad-hoc networks of sensors, mobile phones etc, with limited power supplies.

Shopping and personal recommender applications.
Our work here includes the development of low cost recommender systems (already ongoing from the Samsung GRO award). This study on the use of random walks in recommender systems for mobile phone apps, typifies the need for low cost algorithms. It is no exaggeration to say that in the future, whatever you want, you will probably be using an app on a hand held device to search for it. However much the manufacturers push the boundaries of memory and processing power on these devices, the online networks are growing at a faster rate, and their variety proliferating.

Business, information security and health applications.
Our work on distributed random processes and self-modifying networks offers ways to repair failures in networks such as business intra-nets. Our work on management of epidemic type processes through overlay networks has potential applications in the areas of public health and network security. An example of this is limitation of spreading biological or computer viruses: Infection spreads by direct person to person transmission, or direct computer to computer communication, and prevention occurs by communicating information by a social network (phone, email or Twitter), or a peer-to-peer overlay network.

Publications

10 25 50
 
Description The main work has been on efficient randomized methods to search and find structure of large networks, and to obtain cnesensus in distributed systems. Basically if the structure of a network is unknown it is not straightforward to find where things are and what typically the network looks like. Similary it is difficult to reach agreement (consensus) without any imposed authority. Randomized algorithms can provide reasonable ways to do these things based on local interactions.
Exploitation Route Algorithms can be implemented in real cases with sufficient attention to detail.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description Attend Workshop on "Counting complexity and phase transitions" at Simons Institute for Theory of Computing 
Organisation University of California, Berkeley
Department Simons Institute for the Theory of Computing
Country United States 
Sector Academic/University 
PI Contribution Attend Workshop on "Counting complexity and phase transitions" at Simons Institute for Theory of Computing at UC Berkley for March 2016.
Collaborator Contribution Supported local costs of attendence (up to a total of $135 * 35 days= $4725)
Impact Ongoing research
Start Year 2016
 
Description Research collaboration with A. Frieze CMU 
Organisation Carnegie Mellon University
Department Department of Mathematical Sciences
Country United States 
Sector Academic/University 
PI Contribution Research visit to A. Frieze CMU from 24th July-17 August 2015. Research on the vacant set of random walks, and models of distributed voting on graphs.
Collaborator Contribution Research on the vacant set of random walks, and models of distributed voting on graphs. Provision of office accommodation at CMU.
Impact Outcome publication currently submitted to ICALP 2016. (Cooper, Dyer, Frieze, Rivera. Discordant voting processes on finite graphs. submitted)
 
Description Research cooperation with University of Kyushu (Fukuoka, Japan) 
Organisation Kyushu University
Country Japan 
Sector Academic/University 
PI Contribution Yamashita Group at Kyushu University is a cooperating partner on the EPSRC project. Visit to the research group 5th Nov-2nd Dec 2015, by C. Cooper and PhD student N. Rivera. We worked with the Kyushu group on a range of problems in distributed computing. We gave a research seminar.
Collaborator Contribution Office space. Paid local accomodation and subsistence costs for King's PhD student N. Rivera, and contributed to C. Cooper local expenses.
Impact The outputs are publications, and research cooperation. Coalescing walks on rotor-router systems. (C. Cooper, T. Radzik, N. Rivera, T.Shiraga). Sirocco 2015. Constructing self-stabilizing oscillators in population protocols. (C. Cooper, A. Lamani, G. Vigiletta, M. Yamashita, Y. Yamauchi) SSS 2015. Fast consensus for voting on general expander graphs. (C. Cooper, R. Elsaesser, T. Radzik, N. Rivera, T.Shiraga). DISC 2015 (Symposium on Distributed Computing). A. Lamani, T. Shiraga, M. Yamashita, Y. Yamauchi are from the TCS group at Kyushu.
Start Year 2014
 
Description Research visit to C. Greenhill UNSW Monday 3rd July -- Wednesday 18th July 2017 
Organisation University of New South Wales
Country Australia 
Sector Academic/University 
PI Contribution Work on Markov Processes used to generate and randomize large networks. Models of random graphs with clustering properties typical of social networks.
Collaborator Contribution Work on Markov Processes used to generate and randomize large networks. Models of random graphs with clustering properties typical of social networks.
Impact The recent outcomes are research publications which are still work in progress.
 
Description Visit to Yamashita Labs, University of Kyushu, Department of Computer Science, Japan 6th-28th March 2017 
Organisation Kyushu University
Country Japan 
Sector Academic/University 
PI Contribution Work on consensus algorithms for distributed computer systems, and models of species interaction in the population protocol model. Much of this work was with T. Shiraga who is now at Chuo University Tokyo, and will be visiting research fellow at King's (Department of Informatics) from March 1st-20th 2018
Collaborator Contribution Work on consensus algorithms for distributed computer systems, and models of species interaction in the population protocol model.
Impact The outputs are academic publications, listed in the publications section.
Start Year 2008
 
Description Vist to Alan Frieze at Carnegie Mellon University. Pittsburgh USA. 13th February--3rd march 2018 
Organisation Carnegie Mellon University
Department Department of Mathematical Sciences
Country United States 
Sector Academic/University 
PI Contribution Work on rank of random Boolean matrices, dispersion processes and problems in discrete random walks. A full list of publications can be found at https://www.math.cmu.edu/~af1p/papers.html
Collaborator Contribution Work on rank of random Boolean matrices, dispersion processes and problems in discrete random walks with A. Frieze and W. Pegden. Provision of office space and use of facilities at CMU.
Impact The outputs are academic publications, and are listed in the publications section.
 
Description Vist to Alan Frieze at Carnegie Mellon University. Pittsburgh USA. 17th July-7 August 2016 
Organisation Carnegie Mellon University
Department Department of Mathematical Sciences
Country United States 
Sector Academic/University 
PI Contribution Work with Prof. Frieze on problems relating to Random Walks and Random Processes. This work is ongoing and is in preparation for EPSRC proposal EP/M005038/1 Randomized Algorithms for Computer Networks.
Collaborator Contribution Made some progress on diameter of multi-type branchings, and random walks on dynamic graphs
Impact Outputs from this collaboration are listed in publications portfolio
Start Year 2016
 
Description Workshop "Random walks on random graphs and applications" 
Organisation Eindhoven University of Technology
Country Netherlands 
Sector Academic/University 
PI Contribution We organized the theme of the above workshop, nominated and invited the speakers. The workshop took place from 14-16th April 2015 under our supervision, chairing the sessions etc. The workshop focused on 'Discrete random walks and related processes. Analysis on random graph models, and algorithmic applications to large networks'. It was designed to fit the theme of the EPSRC project, an dpromote research in this area at international level. There were 26 speakers.
Collaborator Contribution The EURANDOM facility provided the workshop location, (T.U. Eindhoven), local organization and administrative support.
Impact The intended outcome is promotion of, and increasing interest in the topic area. EPSRC was a listed sponsor for publicity purposes.
Start Year 2014
 
Description Workshop on Random Graphs and Random Processes. Tuesday 25 April 2017. Kings College London. 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Postgraduate students
Results and Impact The purpose of the workshop was to promote interest in randomized algorithms and random structures and processes at university postgraduate and academic level, and to develop relationships between compter science and mathematics.
Year(s) Of Engagement Activity 2017
URL https://nms.kcl.ac.uk/rasp/rasp_workshop/programme_for_website.pdf
 
Description Workshop to promote research in randomized algorithms. Workshop on random graphs and random processes. April 17th, 2018 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Study participants or study members
Results and Impact The Second King's Workshop on Random Graphs and Random Processes
Tuesday 17th April 2018
Year(s) Of Engagement Activity 2018
URL https://nms.kcl.ac.uk/rasp/rasp_workshop/2018_programme_for_website.pdf