Quantitative Life Sciences seminar - 18 May 2015

[Quantitative Life Sciences]

QUANTITATIVE LIFE SCIENCES SEMINAR

Seminar web page: http://indico.ictp.it/event/7456/

MONDAY, 18 MAY 2015, 14:30
L. STASI Seminar room - ICTP Leonardo Bldg., First floor


Prof. Niloy GANGULY
Department of Computer Science
Indian Institute of Technology, Kharagpur, India


Title:
Coverage maximization under resource constraints using random walk based 
strategies

Abstract:
Information dissemination and search in networks are the most frequently 
performed operations in any large scale distributed system. Maximization 
of the number of distinctly visited nodes (coverage) under constraints 
is the prime target of any proposed algorithm for these operations. In 
order to quickly achieve high coverage, the existing algorithms tend to 
proliferate message packets at higher rate. Due to the nondeterministic 
nature of the algorithms, the blind proliferations create many redundant 
visits in the network which reduces the utilization of available 
resource. For the first time, we formally capture this existing tradeoff 
between the available time and available resource to achieve a certain 
amount of coverage in the network. Using methods from statistical 
mechanics, we showed that coverage can be optimized, without using any 
memory, for a certain combinations of resource and time. We also provide 
the algorithm which can achieve that optimal coverage. For the rest of 
the combinations of resource and time, we provide a notion of optimality 
employing a very little amount memory. We test our hypothesis through 
extensive computer simulations in various kinds of network topologies.


-- 
Erica Sarnataro
Group Secretary
Quantitative Life Sciences
The Abdus Salam International Centre for Theoretical Physics (ICTP)
Trieste,  Italy
Tel. +39-040-2240623
e-mail: qls at ictp.it