Physical Algorithms

摘要

This is the accompanying paper to an ICALP 2010 invited talk, intending to encourage research in physical algorithms. The area of physical algorithms deals with networked systems of active agents. These agents have access to limited information for varying reasons; examples are communication constraints, evolving topologies, various types of faults and dynamics. The networked systems we envision include traditional computer networks, but also more generally networked systems, such as social networks, highly dynamic and mobile networks, or even networks of entities such as cars or ants. In other words, the world is becoming algorithmic, and we need the means to analyze this world!