Browsing by Author "Spirakis, Paul G."
Now showing items 1-20 of 38
-
Book Chapter
Algorithmic Game Theory and Applications
Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Spirakis, Paul G. (John Wiley & Sons, Inc., 2007)Methods from game theory and mechanism design have been proven to be a powerful mathematical tool in order to understand, control, and efficiently design dynamic, complex networks, such as the Internet. Game theory provides ...
-
Article
Approximate Equilibria and Ball Fusion
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul G. (2003)We consider selfish routing over a network consisting of m parallel links through which n selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the ...
-
Article
A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks
Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2004)Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
-
Article
A comparative study of protocols for efficient data propagation in smart dust networks
Chatzigiannakis, Ioannis; Dimitriou, Tassos D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Smart ...
-
Article
Computing on a partially eponymous ring
Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2009)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
-
Article
Computing on a partially eponymous ring
Mavronicolas, Marios; Michael, Loizos; Spirakis, Paul G. (2006)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
-
Article
A cost mechanism for fair pricing of resource usage
Mavronicolas, Marios; Panagopoulou, P. N.; Spirakis, Paul G. (2005)We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand
-
Article
The cost of concurrent, low-contention Read&Modify&Write
Busch, Costas; Mavronicolas, Marios; Spirakis, Paul G. (2005)The possibility or impossibility and the corresponding costs of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system were addressed. A natural class ...
-
Article
Cost sharing mechanisms for fair pricing of resource usage
Mavronicolas, Marios; Panagopoulou, P. N.; Spirakis, Paul G. (2008)We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand
-
Article
Direct routing: Algorithms and complexity
Busch, Costas; Magdon-Ismail, M.; Mavronicolas, Marios; Spirakis, Paul G. (2006)Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct ...
-
Article
Direct routing: Algorithms and complexity
Busch, Costas; Magdon-Ismail, M.; Mavronicolas, Marios; Spirakis, Paul G. (2004)Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three ...
-
Conference Object
Efficiency of oblivious versus non-oblivious schedulers for optimistic, rate-based flow control
Fatourou, Panagiota; Mavronicolas, Marios; Spirakis, Paul G. (ACM, 1997)Lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, rate-based flow control algorithms are established. It is shown that randomness can be exploited to yield an even simpler ...
-
Article
Efficiency of oblivious versus nonoblivious schedulers for optimistic, rate-based flow control
Fatourou, Panagiota; Mavronicolas, Marios; Spirakis, Paul G. (2005)Two important performance parameters of distributed, rate-based flow control algorithms are their locality and convergence complexity. The former is characterized by the amount of global knowledge that is available to their ...
-
Article
Extreme Nash equilibria
Gairing, M.; Lucking, T.; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul G. (2003)We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume ...
-
Article
A glimpse at Christos H. Papadimitriou
Mavronicolas, Marios; Spirakis, Paul G. (2009)Christos H. Papadimitriou is one of the most influential and colorful researchers in Computer Science today. This glimpse is the outcome of a modest attempt of us to a biographical introduction to Christos, which we have ...
-
Article
A graph-theoretic network security game
Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2005)Consider a network vulnerable to viral infection. The system security software can guarantee safety only to a limited part of the network. We model this practical network scenario as a non-cooperative multi-player game on ...
-
Article
A graph-theoretic network security game
Mavronicolas, Marios; Lesta, Vicky Papadopoulou; Philippou, Anna; Spirakis, Paul G. (2008)Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, ...
-
Article
The impact of network structure on the stability of greedy protocols
Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2003)A packet-switching network is stable if the number of packets in the network remains bounded at all times. A very natural question that arises in the context of stability and instability properties of such networks is how ...
-
Article
The impact of network structure on the stability of greedy protocols
Koukopoulos, D.; Mavronicolas, Marios; Nikoletseas, Sotiris E.; Spirakis, Paul G. (2005)Some examples of the impact network structure has on stability behavior of greedy protocols and networks were presented. An important problem was to study the impact of network structure parameters on other greedy protocols. ...
-
Article
The increase of the instability of networks due to Quasi-Static link capacities
Koukopoulos, D.; Mavronicolas, Marios; Spirakis, Paul G. (2007)In this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. Especially, we consider the Adversarial, Quasi-Static Queuing Theory model, ...