Physics of Distributed Information Systems (PhysDIS)

5 May 2008, 08:00 → 31 May 2008, 17:00 Europe/Stockholm

<a href="http://www.nordita.se/">NORDITA</a>

Erik Aurell (KTH), Mikko Alava (HUT)

Content and scope

Statistical physics has recently applied been to understanding, analysis and design of large distributed information systems. These range from decoding algorithms (Belief Propagation) and phase transitions and typical-case hardness in combinatorial optimization problems to content distribution and dynamical phenomena on the Internet, to the modelling of distributed agent systems - Peer-to-Peer networks, auction mechanisms and more. The PhysDIS program aims to survey current trends in this exciting area, and foster new research into untapped directions.

Format and practicalities

The program will be one month in duration, and will take place at the premises of NORDITA in Stockholm, Sweden. The goal of the program is to produce scientific results and to set a future agenda for the field. The program will hence be light on formal meetings and talks. Participants are encouraged to describe their contribution upon registration and are expected to give talks about their work at NORDITA, and at other venues in the Stockholm area arranged by the program organizers. Details on accomodation and financial issues will be posted later, or communicated directly to interested parties.

Confirmed participants

John Ardelius, SICS, Sweden
Mikko Alava, TKK, Finland (P.I.)
Erik Aurell, KTH, Sweden (P.I.)
Axel Brandenburg, NORDITA, Sweden
Mads Dam, KTH Royal Institute of Technology, Sweden
György Dan, KTH Royal Institute of Technology, Sweden
Luca Dell'Asta, ICTP, Italy
Daniele Di Martino, SISSA, Italy
Meesoon Ha, KAIST, Korea
John Hertz, NORDITA, Sweden
Petter Holme, KTH Royal Institute of Technology, Sweden
Chin-Kun Hu, Academia Sinica, Taipei, Taiwan
Supriya Krishnamurthy, Swedish Institute of Computer Science, Sweden
Joachim Krug, Cologne, Germany
Florent Krzakala, ESPCI, France
Sang-hoon Lee, KAIST, Korea
Satya Majumdar, Orsay, France
Matteo Marsili, Abdus Salam ICTP, Trieste, Italy
Paolo Muratore-Ginanneschi, Helsinki, Finland
Mats Nordahl, Stockholm
Matteo Palassini, Barcelona, Spain
Luca Peliti, Naples, Italy
Heiko Rieger, Saarbrucken, Germany
Jesper Tegner, Karolinska Institute, Sweden
Olav Tirkkonen, Helsinki, Finland
Joanna Tyrcha, Stockholm University, Sweden
Massimo Vergassola, Institut Pasteur, France
Bing-Hong Wang, Hefei, China
Haijun Zhou, Chinese Academy of Sciences, Beijing, China

Previous meetings in this series

This NORDITA program follows upon a 2007 Statphys 23 satellite meeting, for which the program and list of attendees is available, and further a planned 2008 Kavli Institute of Theoretical Physics China (KITPC, Beijing, China) event CDInfos0803, for which the registration closes July 15, 2007.

Workshop

This program includes a three-day workshop, May 15-17, to which we expect to attract a larger set of participants, and for which registration is separate, see PhysDIS May 15-17 workshop.

Financial support

We are going to give a number of grants for scientists interested in participating in the program (2 week quanta), and the workshop. The former cover the accommodation and provide assistance for local expenses or travel. Half of the funds have been initially reserved, due to the nature of Nordita, for participants coming from the Nordic countries. We also offer for Nordic scientists smaller grants for participation in the program workshop. To be egligible for support please indicate the intention with your registration, and provide a short explanation of your interest to the program. The deadline for this is January 25th for the program.

Blog

The organizers maintain, to some extent, a program blog.

Monday 5 May

1 Opening of the program

Speakers: Prof. Erik Aurell (KTH), Mikko Alava (HUT, Espoo, Finland)

Slides NORDITA-PhysDIS-Intro.ppt

Tuesday 6 May

2 Sequence evolution in phenotypic space: An overview

While most of the genetic information is coded in the DNA sequence, the selection process acts on phenotypic traits. It may well be the case that, while mutations affect independently these traits, the selective effect (fitness) is a nonlinear function of the traits themselves. I shall recall a general approach to the description of this two-layered evolution process, and I shall discuss recent works in which evidence has been collected for it to take place in the evolutionary dynamics of transcription factor binding sites.

Speaker: Prof. Luca Peliti (Naples)

Slides pelitiphenotypic.pdf

Wednesday 7 May

3 On the scaling properties of 2d randomly stirred Navier–Stokes equation

We inquire the scaling properties of the 2d Navier-Stokes equation sustained by a forcing field with Gaussian statistics, white-noise in time and with power-law correlation in momentum space of degree 2-2*epsilon. This is at variance with the setting usually assumed to derive Kraichan's classical theory. We contrast accurate numerical experiments with the different predictions provided for the small epsilon regime by Kraichnan's double cascade theory and by renormalization group (RG) analysis. We give clear evidence that for all epsilon Kraichnan's theory is consistent with the observed phenomenology. Our results call for a revision in the RG analysis of (2d) fully developed turbulence.

Speaker: Dr Paolo Muratore-Ginanneschi (University of Helsinki)

Slides 2dns-sto.pdf

4 Self-organized Synchronization in Wireless Networks

In wireless networks it is beneficial for the nodes to share a notion of time, at least in a periodic (clock) sense. In existing cellular networks, nodes may get their timing from a centralized server. In networks without centralized control, however, such as ad hoc and sensor networks, time synchrony has to be generated in a self-organized manner. Each node decides its preferred timing based on information on the timings of other nodes. In the literature, synchronization algorithms based on (pulse) coupled oscillators have been widely studied, mostly in the setting of a fully connected network. In this talk, synchronization in networks with nearest neighbor coupling is studied. Synchronizatino based on pulse coupled oscillators is compared to simple cyclic averaging algorithms.

Speaker: Prof. Olav Tirkkonen (TKK)

Slides SONsyncNordita_Tirkkonen.pdf

Thursday 8 May

5 Languages along the Silk Road

The paper is focused on the part of the Silk Road in the Tarim Basin and adjacent areas. Today this region is located mostly within the Xinjiang Uyghur Autonomous Region of the People’s Republic of China, but in historical times it has been contested by many states and power structures and has served as a melting pot for many peoples, cultures and languages. The relatively modern concept of the Silk Road has been applied to the various trading routes linking China with the Western World, although it served more as a link between China and Central Asia. Since the latter part of the 19th century remarkable archaeological finds have given rise to new approaches to the study of Silk Road history, especially in the form of manuscripts in previously unknown languages like Tokharian and Saka. In this region, well-preserved mummies of Caucasian origin have been found, and this has led to wide-spread speculations about the migrations of mankind in this area, one of the last to the permanently settled in the world due to its harsh climatic conditions. Furthermore, the various interpretations of the history of this region have further deepened the ideological conflicts between the present-day majority population of the area, the Uyghurs, and the soon-to-be majority, the Han Chinese.

Speaker: Dr Joakim Enwall (Uppsala University)

6 The puzzle of the evolutionary dynamics of influenza

Influenza exhibits two apparently contradictory features: on the one hand, any given individual can get infected with the disease over and over again, since the virus mutates fast enough to escape acquired immunity; on the other hand, on any given epidemic season, the viral strain is sufficiently well-defined, so that an effective vaccine can be identified. It represents a problem in evolutionary dynamics in which the molecular level and the epidemiological level are tightly bound. Several mechanisms have been proposed to explain this behavior, but a satisfactory answer is still lacking. I shall review the recent debate on the subject and point out the most promising directions of research.

Speaker: Prof. Luca Peliti (Naples)

Slides flu.pdf

Friday 9 May

7 Large Deviation of the Top Eigenvalue of a Random Matrix

The statistical properties of the largest eigenvalue of a random matrix are of interest in diverse fields ranging from disordered systems to statistical data analysis and even to string theory. In this talk I'll discuss some recent developements on the theory of extremely rare fluctuations of the largest eigenvalue and its various applications.

Speaker: Prof. Satya Majumdar (Directeur de Recherche, CNRS, Universite Paris-Sud (ORSAY), FRANCE.)

Slides exmat5.pdf

8 Program reception

Monday 12 May

9 Biological strategies of motility

I shall discuss the challenges faced by living organisms trying to locate and move towards a source of nutrients, odors, pheromones, etc., i.e. substances emitted by the source and randomly transported by the environmental medium. Microorganisms, such as bacteria performing chemotaxis, can rely on local concentration gradients to guide them towards the source, yet they have to cope with the stochastic nature of the microscopic world and must reliably infer local gradients from noisy series of detections. Macro-organisms, such as insects and birds, are spared by molecular noise but they lack local cues pointing towards the location of the source because mixing in a flowing medium breaks up regions of high concentration into random and disconnected patches, carried by winds and currents. Thus macroscopic animals, e.g. sensing odors in air or water, detect them only intermittently as patches of odor sweep by, and they must devise a strategy of movement based upon sporadic cues and partial/missing information. Understanding of the strategies evolved by living organisms also has technological applications to robotics.

Speaker: Prof. Massimo Vergassola (Institut Pasteur)

Slides Karolinska_MV.ppt

Tuesday 13 May

10 Dynamics of microbial evolution

Abstract: Experimental evolution is an emerging field of evolutionary biology in which populations of microbes (bacteria, viruses, fungi) are propagated in the lab for thousands of generations and adaptive events are monitored in phenotypic and genotypic detail. In this talk I will review recent efforts at modeling such experiments, based on the classic Wright-Fisher model of population genetics. The talk will focus in particular on the phenomenon of clonal interference, the competition between different beneficial mutations that is believed to slow down the adaptation of asexual populations and hence to contribute to the evolutionary advantage of sex [1].

1. S.C. Park, J. Krug, PNAS 104, 18135 (2007)

Speaker: Prof. Joachim Krug (U Cologne)

Slides Stockholm.pdf

11 Angiogenesis and Vascular network remodeling in a growing tumor

During tumor growth the regular arterio-venous blood vessel network in normal tissue is transformed into a highly inhomogeneous tumor specific vasculature, involving a multitude of dynamical processes like cell proliferation, angiogenesis, vessel regression and cell death. A general characteristics is the compartmentalization of the tumor into several regions differing in vessel density, diameter and in necrosis. Prominent features are also "hot spots", which are regions of high vascular density and increased blood flow in the center of the tumor, and whose analysis is an important diagnostic tool in cancer treatment. We present a model for vascular remodeling in tumorv predicting that the formation of hot spots correlates with local inhomogeneities of the original arterio-venous vasculature of the healthy tissue. Probable locations for hot spots in the late stages of the tumor are locations of increased blood pressure gradients. The developing tumor vasculature is non-hierarchical but still complex displaying a fractal geometry and algebraically decaying density distributions.

Speaker: Prof. Heiko Rieger (Saarbrucken)

Slides Talk-Rieger.pdf

Wednesday 14 May

12 Peer-assisted content distribution systems

Peer-assisted content distribution systems can be characterized by two important properties: first, content is distributed to the consumers using the resources of other consumers; second, participation in the system and contribution to the system's resources is voluntary. Peer-assisted content distribution is best known due to the popularity of peer-to-peer file-sharing systems, but it is also promising for streaming content delivery, as well as it is the underlying principle of delay tolerant networking. In this talk we will discuss the challenges of peer-assisted content distribution systems with special focus on streaming content delivery and delay tolerant networks, and we will present some recent analytical results on the performance of these systems.

Speaker: Dr György Dan (KTH)

13 On state space structure and average case complexity in random KSAT problems

Licentiate presentation, J. Ardelius, KTH and SICS

Thursday 15 May

PhysDIS May 15-17 workshop, Day 1

The program of the PhysDIS May 15-17 workshop will be
announced on the
workshop website.

Friday 16 May

PhysDIS May 15-17 workshop Day 2

The program of the PhysDIS May 15-17 workshop will be
announced on the
workshop website.

Saturday 17 May

PhysDIS May 15-17 workshop Day 3

The program of the PhysDIS May 15-17 workshop will be
announced on the
workshop website.

Monday 19 May

14 Computing Structures and Properties of Proteins in Parallel computers

In this talk, I briefly review some recent developments in computing structures and properties of proteins in parallel computers. The topics under discussion include:

1. developments of algorithms and computer packages for all-atom simulations of proteins in parallel computers,
2. parallel tempering simulations of HP-36
3. development of algorithm to compute volume <emph>V</emph>, surface area <emph>A</emph>, and cavity of proteins by analytic equations in parallel computers,
4. new force replica exchange method and protein folding pathways probed by force-clamp technique and related problems.

Speaker: Prof. Chin-Kun Hu (Academica Sinica)

Slides 080519protein.ppt

Tuesday 20 May

15 Study of prisoner's dilemma game, snowdrift game, and naming game on complex network

Since the spatial structure is introduced into the evolutionary games by Nowak and May, there has been a continuous effort on exploring effects of spatial structures on the cooperation. It has been found that the spatial structure promotes evolution of cooperation in the prisoner's dilemma game (PDG), while in contrast often inhibits cooperative behavior in the snowdrift game (SG). In recent years, extensive studies indicate that many real networks are far different from regular lattices, instead, show small-world and scale-free topological properties. Hence, it is naturally to consider evolutionary games on networks with these kinds of properties. An interesting result found by Santos and Pacheco is that “Scale-free networks provide a unifying framework for the emergence of cooperation”. First, I will review some of our works in the field of evolutionary games. By means of some simple models, we have studied how an important topological structural feature, the average degree, affects the cooperative behavior. We found there is a highest cooperation level induced by an optimal value of average degree for different types of networks. Besides, we investigate the randomness effect on the cooperative behavior by introducing both topological and dynamical randomness. We found a resonance type phenomena reflected by the existence of highest level of cooperation in the case of appropriate randomness. Moreover, we propose a memory-based snowdrift game over complex networks. Some very interesting behaviors are observed, such as the nonmonotonous behavior of frequency of cooperation as a function of payoff parameter, spatial pattern transition and so on. Then, I shall discuss about a structured language game, the naming game. We propose an asymmetric negotiation strategy to investigate the influence of high-degree agents on the agreement dynamics in the naming game. We introduce a model parameter, which governs the frequency of high-degree agents acting as speakers in communication. It is found that there exists an optimal value of the parameter that induces the fastest convergence to a global consensus on naming an object for both scale-free and small-world naming games. This phenomenon indicates that, although a strong influence of high-degree agents favors consensus achievement, very strong influences inhibit the convergence process, making it even slower than in the absence of influence of high-degree agents. Investigation of the total memory used by agents implies that there is some trade-off between the convergence speed and the required total memory. Other quantities, including the evolution of the number of different names and the relationship between agents’ memories and their degrees, are also studied. The results are helpful for better understanding of the dynamics of the naming game with asymmetric negotiation strategy.

Speaker: Prof. Bing-Hong Wang (University of Science and Technology of China)

Slides 08-05-20_NORDITA_Evolutionary_games_on_networks.pdf

Wednesday 21 May

16 Effects of delay and noise in a negative-feedback genetic regulatory loop

Due to the small number of molecules involved in intracellular processes, stochastic fluctuations play an important role in gene regulation, and possible constructive effects of noise have received considerable attention. Another important, but often neglected, aspect of gene regulation are the long delays involved in the complex biochemical processes of transcription and translation. We study the interplay of intrinsic noise and delay in a model of the p53 core regulatory network. Recent experiments found pronounced coordinated oscillations in the concentrations of proteins p53 and Mdm2 in individual cells subjected to DNA damage. Oscillations have also been observed in other systems with negative feedback, such as the Hes1 and NF-$\kappa$B systems, and in circadian rhythms. Several mechanisms have been proposed to explain these findings, such as deterministic limit cycles (with or without delay) and noise-induced oscillations in the presence of a strong separation between fast and slow reactions. We consider a birth-and-death master equation model of the negative feedback loop between p53 and Mdm2, which does not assume a strong separation of reaction rates but takes into account the transcriptional and translational delay (at the price of analytical and computational complications due to the non-Markovian dynamics). Via exact stochastic simulations, we find pronounced noise-induced oscillations in a wide region of parameters for which there are no sustained oscillations in the deterministic limit, in qualitative agreement with the experimental results. We speculate that this may be a generic mechanism for oscillations in gene regulatory systems.

Speaker: Prof. Matteo Palassini (Barcelona)

Thursday 22 May

17 Extreme Value Statistics, Integer Partitions, and Bose Gas

Speaker: Prof. Satya Majumdar (Directeur de Recherche, CNRS, Universite Paris-Sud (ORSAY), FRANCE.)

Slides expart7.pdf

Friday 23 May

18 Googling social interactions: Web search engine based social network construction

Recently, massive digital records have made it possible to analyze a huge amount of data in social sciences such as social network theory. We investigate social networks between people by extracting information on the World Wide Web. Using famous search engines such as Google, we quantify relatedness between two people as the number of Web pages including both of their names and construct weighted social relatedness networks. The weight and strength distributions are found to be quite broad. A class of measure called the R{\'e}nyi disparity, characterizing the homogeneity of weight distribution for each node, is presented. We introduce the maximum relatedness subnetwork, which extracts the most essential relation for each individual. We analyze the members of the 109th United States Senate as an example and demonstrate that the methods of construction and analysis are applicable to various other social groups and weighted networks.

In addition, I will present some results of my recent works on phase transition in annealed scale-free networks, etc.

Speaker: Sang Hoon Lee (Complex Systems and Statistical Physics Lab, KAIST)

Slides GoogleCorr_PhysDIS.ppt

Monday 26 May

19 Multi-asset markets, empirical data, and theoretical modelling

Speaker: Dr Matteo Marsili (Abdus Salam ICTP)

Slides PhysDis08corr.pdf

Wednesday 28 May

20 Instability transitions and ensemble equivalence in diffusive flow

Speaker: Prof. Meesoon Ha (KAIST, Korea)

Slides HA_talk-physDIS.pdf

Thursday 29 May

21 A thermodynamic mechanism for the agglomeration of DNA-looping proteins

Speaker: Sumedha Sumedha (ISI, Torino, Italy)

Slides aggdnanordita.pdf

Friday 30 May

22 Peer-to-peer systems and physics

Speakers: Dr György Dan (KTH, EE), Dr Supriya Krishnamurthy (SICS)

Slides dandisc.pdf supdisc.pdf