Algorithms, Probability, Networks, and Games

Paul Spirakis is an eminent, talented, and influential researcher that contributed significantly to computer science. This article is a modest attempt of a biographical sketch of Paul, which we drafted with extreme love and honor.

I was lucky to be exposed to game theory by Paul Spirakis, moreover to have my first PhD student, Elad Schiller staying with Paul as his PostDoc. It was a great opportunity to examine and think about the combination of philosophical and social considerations when examining the rigorous mathematical settings, results and implications of Game Theory. Implications, that should reflect our real life situations. Especially when searching for game theory tools to be used automatically by societies of (users connected to) computers that form a distributed system.

“We are our connectome,” this is the tautology du jour. Everything we do, think, remember, say (or write), is merely a projection of our current neural configuration. So, here goes.

This is a brief essay in honor of Paul Spirakis on the occasion of his 60th birthday, and a prologue for the articles of this volume titled “Of concurrent data structures and iterations” and “Data-streaming and concurrent data-object co-design: overview and algorithmic challenges”.

Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the “best-reply” to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant’s advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties’ advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.

We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:

Duan and Mehlhorn and Duan, Garg, and Mehlhorn presented polynomial time combinatorial algorithms [DM13, DGM15] for the computation of equilibrium prices in linear exchange markets. I am currently implementing these algorithms. I discuss the questions that I hope to answer through the implementation.

Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification model, considered in this work, is that of Lengauer [21, 22], referred to as L-specifications. In this paper we discuss a restriction on the L-specifications resulting to graphs which we call Well-Separated (WS). This class is recognized in polynomial time.

We first show that RCP is \(\mathcal{PSPACE}\)-complete for WS L-specified hierarchical planar graphs. Second, we present a polynomial time 3-approximation algorithm as well as a more efficient asymptotic 10/3-approximation algorithm for RCP on graphs of this class. We note that, the best currently known approximation ratio for the RCP on ordinary (non-hierarchical) planar graphs of general degree is 5 / 3 asymptotically ([27, 28]).

Mobile Ad hoc Networks (MANETs) and especially Vehicular Ad hoc Networks (VANETs) have recently gained large interest and their performance is heavily studied. A great challenge in VANETs, especially in an urban setting, is the routing scheme used and the subsequent performance obtained. This work presents an experimental performance evaluation of routing mechanisms in VANETs, using simulation, within an urban Manhattan grid like environment. It also describes and evaluates an enhancement of the Greedy Perimeter Stateless Routing (GPSR) protocol that takes into account the motion of the vehicles and the nature of the urban environment. The simulation results demonstrate that the proposed enhancement to the GPSR protocol manages to significantly increase the delivery ratio without increasing the power consumption; nevertheless, in some cases the improvement on delivery ratio is achieved at the expense of slightly increased end-to-end delay.

In the Internet of Things era, every one of over a trillion everyday items will include at least some ability to store and process information. And, more important, to share that information over the global Internet with the other trillion items. In order to support this technological evolution, among the first problems that were addressed by the research community was that of basic network communication as existing, conventional (Internet-like) networking approaches were either unworkable or impractical. One of the solutions proposed is the so-called “Support Approach” that was proposed in 2000 and rigorously studied using a combination of theoretical and practical research. In this paper we present the main findings and we comment on the research methodology that led to these results.

We present an optimal deterministic O(n)-work parallel algorithm for finding a minimum spanning tree on an n-vertex planar graph. The algorithm runs in \(O(\log n)\) time on a CRCW PRAM and in \(O(\log n\log ^*n)\) time on an EREW PRAM. Our results hold for any sparse graph that is closed under taking of minors, as well as for a class of graphs with non-bounded genus.

In this work, we present a comprehensive treatment of weighted random sampling (WRS) over data streams. More precisely, we examine two natural interpretations of the item weights, describe an existing algorithm for each case [3, 8], discuss sampling with and without replacement and show adaptations of the algorithms for several WRS problems and evolving data streams.

We give a sketchy and mostly informal overview of research on algorithmic properties of congestion games in the last ten years. We discuss existence of potential functions and pure Nash equilibria in games with weighted players, simple and fast algorithms that reach a pure Nash equilibrium, and efficient approaches to improving the Price of Anarchy.

Processing big volumes of data generated on-line, implies needs to carry out computations on-the-fly, in the streams of data. In parallel data-stream computing, the underlying data objects can provide the means for exchanging the data so that the communication and the work imbalance between the concurrent threads performing the computation are reduced, while the pipeline parallelism is enhanced. By shedding light on the concurrent data objects and their role as articulation points in data-stream processing, we place some cornerstones to analyze the problems, propose appropriate new data structures suitable for a set of functions and identify new key challenges to improve data-stream processing through co-design with fine-grain efficient synchronization combined with the data exchange.

It is interesting to point out that research in distributed computing on multiprocessor efficient and consistent data sharing through fine-grain synchronization emerged from questions in concurrent database-related research; approximately three decades since then, it is interesting to see several returns of the fruits of this expedition, helping with the new problems in the massive-data research domain, with applications in e.g. cyberphysical systems.

Internet and other multimedia packet-switched networks are heterogeneous due to the simultaneous running (composition) of different contention-resolution protocols over different network hosts and the existence of various types of network links. Also, real networks are dynamic in their nature due to intentional or unintentional changes on network link service rates or tra nsient link failures. Our interest is focused on FIFO compositions with other contention-resolution protocols due to the FIFO popularity for offering best-effort services in packet-switched networks. A packet-switched network is stable, if the number of packets in the network remains bounded at all times against any adversary. We use an enhanced adversarial framework that is based on an adversary that controls packet injection rates, along with packet paths, and manipulates link slowdowns or capacities. Within this framework, we study the impact of specific compositions of FIFO with other protocols on the network stability using as a test-bed specific network topologies which have been proved forbidden for stability for a single protocol, fixed link slowdowns/capacities and packet paths without repeated links/edges. Our results suggest that the instability behavior of a network using FIFO compositions under adversarial attacks, that dynamically change link slowdowns/capacities, is not only maintained, but, also, may become worse than in the case of attacks that do not change slowdowns/capacities or when a single protocol, like FIFO, is employed on all network queues for contention-resolution. We believe that this study can advance the research for the provision of trustworthy heterogeneous networks.

The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches for the simplex method have been extensively studied in the literature due to the intensive computations required, especially for the solution of large linear problems (LPs). In this paper, first a detailed overview is given of the parallelization attempts concerning the standard and the revised simplex method made to date. Next, some of the most recent and significant relevant attempts are selected and presented in more detail along with experimental results. The latter include some impressive results obtained for the revised simplex method over a modern supercomputer, as well as the recent advances in GPU-based related attempts.

A temporal graph is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence \(G_1,G_2\ldots ,G_l\) of static graphs over the same (static) set of nodes V. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.

In the standard Random Surfer Model, the teleportation matrix is necessary to ensure that the final PageRank vector is well-defined. The introduction of this matrix, however, results in serious problems and imposes fundamental limitations to the quality of the ranking vectors. In this work, building on the recently proposed NCDawareRank framework, we exploit the decomposition of the underlying space into blocks, and we derive easy to check necessary and sufficient conditions for random surfing without teleportation.

Bulk operations on data structures are widely used both on user-level but also on programming language level. Iterations are a good example of such bulk operations. In the sequential setting iterations are easy to design on top of an algorithmic construction of a data structure and is not considered as a challenge. In a concurrent environment, such as a multicore system, the situation is completely different and the issue of extending concurrent data structure designs to support iteration operations opens new research challenges in concurrent algorithmic data structure implementations, with respect to consistency and efficiency. In this paper we take a journey through this young and evolving research topic. More precisely we describe recent advances in the area together with an overview of iteration implementations that have appeared in the research literature as well as in widely-used programming environments and we outline a range of application targets and challenging future directions.

In this paper, we consider a simple, yet general family of random graph models, namely Random Intersection Graphs (RIGs), which are motivated by applications in secure sensor networks, social networks and many more. In such models there is a universe \(\mathcal{M}\) of labels and each one of n vertices selects a random subset of \(\mathcal{M}\). Two vertices are connected if and only if their corresponding subsets of labels intersect. In particular, we briefly review the state of the art and we present key results from our research on the field, that highlight and take advantage of the intricacies and special structure of random intersection graphs. Finally, we present in more detail a particular result from our research, which concerns maximum cliques in the uniform random intersection graphs model (in which every vertex selects each label independently with some probability p), namely the Single Label Clique Theorem.

We review here some recently proposed models of non-cooperative network creation games where the nodes of a network perform edge swaps in order to improve their communication costs. Our focus is on examining the structure of stable (equilibrium) networks that correspond to efficient notions of equilibria, in the sense that the nodes of the network are able to decide which links to add and which to remove in order to achieve a minimal cost, given the strategies of the other nodes. We also review results on the capability of the network nodes of converging into an equilibrium network by performing local selfish improvement steps.

We consider here the problem of answering range product queries on an n-node unrooted tree labelled with elements of a semigroup provided with an associative operator only. We present simple parallel dynamic algorithms for one of the weakest models of parallel computation (EREW PRAM). Our main result is an algorithm which answers a query in \(O(\alpha (n))\) time using a single processor after \(O(\log n)\)-time and O(n)-work preprocessing, where \(\alpha (n)\) is the inverse of Ackermann’s function. The data structures set up during preprocessing are updated in \(O(\log n)\) time and \(O(n^\beta )\) work, for any (arbitrarily small) constant \(0<\beta <1\), after a dynamic change in the label of a tree node.