In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge e is assigned l_e labels, each drawn uniformly at random from (0,1], where the numbers l_e are independent random variables following the same discrete probability distribution. In the second, the discrete model, the l_e labels of each edge e are chosen uniformly at random from a set {1,2,…,T}. In both models we study the existence of δ-temporal motifs. Here a δ-temporal motif consists of a pair (H,P), where H is a fixed static graph and P is a partial order over its edges. A temporal graph 𝒢 = (G,λ) contains (H,P) as a δ-temporal motif if 𝒢 has a simple temporal subgraph on the edges of H whose time labels are ordered according to P, and whose life duration is at most δ. We prove sharp existence thresholds for all δ-temporal motifs, and we identify a qualitatively different behavior from the analogous static thresholds in Erdős-Rényi random graphs. Applying the same techniques, we then characterize the growth of the largest δ-temporal clique in the continuous variant of our random temporal graphs model. Finally, we consider the doubling time of the reachability ball centered on a small set of vertices of the random temporal graph as a natural proxy for temporal expansion. We prove sharp upper and lower bounds for the maximum doubling time in the continuous model.

A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time step, where Δ is a given period length. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are “stretched”, compared to their distances in the underlying static graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple algorithm which guarantees an approximation strictly smaller than Δ. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges.

We present a comprehensive analysis of Round-Delayed Amnesiac Flooding (RDAF), a variant of Amnesiac Flooding that introduces round-based asynchrony through adversarial delays. We establish fundamental properties of RDAF, including termination characteristics for different graph types and decidability results under various adversarial models. Our key contributions include: (1) a formal model of RDAF incorporating round-based asynchrony, (2) a proof that flooding always terminates on acyclic graphs despite adversarial delays, (3) a construction showing non-termination is possible on any cyclic graph, (4) a demonstration that termination is undecidable with arbitrary computable adversaries, and (5) the introduction of Eventually Periodic Adversaries (EPA) under which termination becomes decidable. These results enhance our understanding of flooding in communication-delay settings and provide insights for designing robust distributed protocols.

In the distributed localisation problem (DLP), n anonymous robots (agents) A_0, ..., A_{n-1} are located at arbitrary points p_0, ..., p_{n-1} ∈ S, where S is a Euclidean space. Initially, each agent A_i operates within its own coordinate system in S, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p_0, ..., p_{n-1} in S. Extensive research on DLP has primarily focus on the feasibility and complexity of achieving consensus when agents have limited access to inter-agent distances, often due to missing or imprecise data. In contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, if needed. Specifically, we introduce a novel variant of population protocols, referred to as the spatial population protocols model. In this variant each agent can memorise one or a fixed number of coordinates, and when agents A_i and A_j interact, they can not only exchange their current knowledge but also either determine the distance d_{ij} between them in S (distance query model) or obtain the vector v_{ij} spanning points p_i and p_j (vector query model). We propose and analyse several distributed localisation protocols, including: 1) Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2) Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)^{1/(k+1)}log n) in k-dimensions. 3) Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time.

Geometry optimization of atomic structures is a common and crucial task in computational chemistry and materials design. Following the learning to optimize paradigm, we propose a new multi-agent reinforcement learning method called Multi-Agent Crystal Structure optimization (MACS) to address the problem of periodic crystal structure optimization. MACS treats geometry optimization as a partially observable Markov game in which atoms are agents that adjust their positions to collectively discover a stable configuration. We train MACS across various compositions of reported crystalline materials to obtain a policy that successfully optimizes structures from the training compositions as well as structures of larger sizes and unseen compositions, confirming its excellent scalability and zero-shot transferability. We benchmark our approach against a broad range of state-of-the-art optimization methods and demonstrate that MACS optimizes periodic crystal structures significantly faster, with fewer energy calculations, and the lowest failure rate.

In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex at any given timestep. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that this problem is NP-complete for both star graphs (for k ≥ 2 robots), and planar graphs (for any number of robots). Finally, we provide positive results for path, cycle, and tadpole graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal duration of a path of length n in O ( k m n ) , O ( k m n 2 ) time, and O ( k 3 m 4 n ) time respectively.

In a temporal network with discrete time-labels on its edges, information can only "flow" along sequences of edges with non-decreasing (resp.increasing) time-labels.In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges.By naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation, and we systematically investigate its algorithmic behavior.Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a temporal graph G is transitively orientable.In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether G is strictly transitively orientable.Additionally we introduce further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots . In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph are removed. Removed edges are called excess edges . The main problem investigated in this paper is: Given a target graph G , design an algorithm that outputs a process that grows G , called a growth schedule . Additionally, we aim to minimize the total number of slots k and of excess edges ℓ used by the process. We provide both positive and negative results, with our main focus being either schedules with sub-linear number of slots or with no excess edges.

Abstract In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle $$C^{\prime } \ne C$$ C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree $$\delta $$ δ and maximum degree $$\Delta $$ Δ . We provide a linear-time algorithm for computing a cycle $$C^{\prime } \ne C$$ C ′ ≠ C of length at least $$n-4\alpha (\sqrt{n}+2\alpha )+8$$ n - 4 α ( n + 2 α ) + 8 , where $$\alpha = \frac{\Delta -2}{\delta -2}$$ α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of $$\frac{\Delta }{\delta } = o(\sqrt{n})$$ Δ δ = o ( n ) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every $$0 0 < p ≤ 0.02 , if the minimum degree of G is at least $$\frac{8}{p} \log \sqrt{8}n + 4$$ 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least $$1 - \frac{1}{n}\left( \frac{50}{p^4} + 1 \right) $$ 1 - 1 n 50 p 4 + 1 in $$poly(n) \cdot 2^{4pn}$$ p o l y ( n ) · 2 4 p n time. This result implies that, when the minimum degree $$\delta $$ δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when $$\delta = \omega (\log n)$$ δ = ω ( log n ) , our probabilistic algorithm works in $$2^{o(n)}$$ 2 o

A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to determine the smallest total number of time-labels |λ| needed to ensure temporal connectivity, where |λ| denotes the sum, over all edges, of the size of the set of labels associated to an edge. The basic problem, called Minimum Labeling (ML) can be solved optimally in polynomial time. We introduce the Min. Aged Labeling (MAL) problem, which involves connecting the graph with an upper-bound on the maximum label, the Min. Steiner Labeling (MSL) problem, focusing on connecting specific important vertices, and the age-restricted version of MSL, Min. Aged Steiner Labeling (MASL). We show that MAL is NP-complete, MASL is W[1]- hard, and while MSL remains NP-hard, it is FPT with respect to the number of terminals.

Abstract. A Nash equilibrium of a routing game is a stable state where no (randomizing) user could benefit from a unilateral deviation. We consider the simplest case of the parallel links network, where links are related. The Social Cost of a Nash equilibrium is the expected maximum latency. We seek the worst-case Nash equilibrium [E. Koutsoupias and C. H. Papadimitriou, Comput. Sci. Rev., 3 (2009), pp. 65–69], which maximizes Social Cost. We continue the study of the fully mixed Nash equilibrium conjecture, abbreviated as the FMNE Conjecture, stating that the worst-case Nash equilibrium is the fully mixed Nash equilibrium, where each user assigns strictly positive probability to every link. Through an extensive combinatorial analysis, we confirm the FMNE Conjecture for the two basic cases where there are either (i) two users on related links, or (ii) many users on two identical links.

Modern classification problems tackled by using Decision Tree (DT) models often require demanding constraints in terms of accuracy and scalability. This is often hard to achieve due to the ever-increasing volume of data used for training and testing. Bayesian approaches to DTs using Markov Chain Monte Carlo (MCMC) methods have demonstrated great accuracy in a wide range of applications. However, the inherently sequential nature of MCMC makes it unsuitable to meet both accuracy and scaling constraints. One could run multiple MCMC chains in an embarrassingly parallel fashion. Despite the improved run-time, this approach sacrifices accuracy in exchange for strong scaling. Sequential Monte Carlo (SMC) samplers are another class of Bayesian inference methods that also have the appealing property of being parallelizable without trading off accuracy. Nevertheless, finding an effective parallelization for the SMC sampler is difficult, due to the challenges in parallelizing its bottleneck, redistribution, in such a way that the workload is equally divided across the processing elements, especially when dealing with variable-size models such as DTs. This study presents a parallel SMC sampler for DTs on Shared Memory (SM) architectures, with an$O(log_{2} N)$parallel redistribution for variable-size samples. On an SM machine mounting 32 cores, the experimental results show that our proposed method scales up to a factor of 16 compared to its serial implementation, and provides comparable accuracy to MCMC, but 51 times faster.

Abstract Let V be a set of n vertices, $${\mathcal M}$$ M a set of m labels, and let $${\textbf{R}}$$ R be an $$m \times n$$ m × n matrix ofs independent Bernoulli random variables with probability of success p; columns of $${\textbf{R}}$$ R are incidence vectors of label sets assigned to vertices. A random instance $$G(V, E, {\textbf{R}}^T {\textbf{R}})$$ G ( V , E , R T R ) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely $$[{\textbf{R}}^T {\textbf{R}}]_{v,u}$$ [ R T R ] v , u ) between any two vertices u, v for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given $$G(V, E, {\textbf{R}}^T {\textbf{R}})$$ G ( V , E , R T R ) we wish to find a partition of V into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized. In particular, we initially prove that the weight of a maximum cut of $$G(V, E, {\textbf{R}}^T {\textbf{R}})$$ G ( V , E , R T R ) is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, $$m=n^{\alpha }, \alpha <1$$ m = n α , α < 1 ), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case $$n=m$$ n = m and constant average degree (i.e. $$p = \frac{\Theta (1)}{n}$$ p = Θ ( 1 ) n ), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in $$G(V, E, {\textbf{R}}^T {\textbf{R}})$$ G ( V , E , R T R ) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system $$\Sigma $$ Σ with incidence matrix $${\textbf{R}}$$ R (i.e. minimum imbalance over all sets in $$\Sigma $$ Σ ). We exploit this connection by proposing a (weak) bipartization algorithm for the case $$m=n, p = \frac{\Theta (1)}{n}$$ m

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or Delta-TVC for time-windows of a fixed-length Delta) have been established as natural extensions of the classic Vertex Cover problem on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and Delta-TVC on sparse graphs. Our main result shows that for every Delta geq 2, Delta-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between Delta-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover.

In the food and beverage industry many foods, beers and soft drinks usually need to get pasteurized, a process that holds a significant role in the quality and taste of the final product but is difficult to monitor due to the process nature. Soft sensing techniques, also called virtual sensing or surrogate sensing, can be leveraged to monitor the product quality, by using information available from other measurements and process parameters to calculate an estimation of the quantity of interest. In this paper, we develop a soft sensing methodology that is based on machine learning algorithms for continuous, end-to-end estimation of the temperature of products during the pasteurization process, with the vision to serve as an intermediate step towards monitoring live the final quality of the pasteurized products. This work studies a real beer pasteurization process in collaboration with Heineken’s plant in Patras, Greece and the results demonstrate notable performance in temperature prediction accuracy, with average root mean square error (RMSE) of 1.85°C in the test sets. Thus, we claim that it is possible to obtain measurements quite similar to the ones by the respective physical sensors with sufficient accuracy, and our methodology can be considered as a virtual low-cost solution for monitoring product quality in legacy pasteurizer operation.

A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|λ|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,λ)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MIN. AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,λ)$. Second we consider the problem MIN. STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of "terminals" vertices which lie in a subset $R\subseteq V$. This relaxed problem resembles STEINER TREE in static graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MIN. AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL is NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder.

In this paper we consider a known variant of the standard population protocol model in which agents can be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time. The main focus in this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. - We propose and analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n). - The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016]. - We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart. - We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0.

Abstract We study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network $$G_s$$ G s to a target network $$G_f$$ G f from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the total edge activations , the maximum activated edges per round , and the maximum activated degree of a node . We give (poly)log( n ) time algorithms for the task of transforming any $$G_s$$ G s into a $$G_f$$ G f of diameter (poly)log( n ), while minimizing the edge-complexity. Our main lower bound shows that $$\varOmega (n)$$ Ω ( n ) total edge activations and $$\varOmega (n/\log n)$$ Ω ( n / log n ) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of $$\varTheta (\log n)$$ Θ ( log n ) rounds. We give three distributed algorithms for our general task. The first runs in $$O(\log n)$$ O ( log n ) time, with at most 2 n active edges per round, a total of $$O(n\log n)$$ O ( n log n ) edge activations, a maximum degree $$n-1$$ n - 1 , and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter $$O(\log n)$$ O ( log n ) and uses O ( n ) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog( n ) then we can achieve $$o(\log ^2 n)$$ o ( log 2 n ) running time. </

Allergic diseases and, in particular, allergic rhinitis are among the most common chronic diseases, inducing disturbances in daily activities. They are caused primarily by the pollens of allergenic plants and symptoms can deteriorate due to various ambient conditions which work as irritants, such as humidity. In this paper, we present the development of an eHealth/mHealth holistic platform that utilizes the technologies of Internet of Things (IoT), Mobile Crowdsensing (MCS), Social Networking Services, Natural Language Processing (NLP), and Machine Learning (ML), in order to work as a sentinel and disease prevention tool for patients with allergic rhinitis symptoms. By efficiently combining human with machine intelligence, we provide a complementary sensing method for the comprehensive and large-scale monitoring of the disease in broad regions, and in real-time. Moreover, the users of our platform are encouraged to engage in the sensing process through a personalized health monitoring system in order to keep a constant awareness of their symptoms and, thus, deliver a successful adherence to their treatment. As an important use case, we adapted our platform to the USA region, but it can be easily extended to any other area with minor modifications. The design and complete implementation of our platform has been performed and validated in close cooperation with well-recognized academic medical doctors based in Greece who specialize in the control of allergic diseases (and rhinitis in particular) and provided valuable insights and detailed requirements analysis about the functionality and usability of the platform. To the best of our knowledge, this is the first study that examines allergic rhinitis monitoring in a complementary manner and on large scale, with the utilization of hybrid data sources.

The effective utilization of real-world data is an integral part of any IoT monitoring or AI-assisted system. Thus, data collection and annotation is an important step towards the successful development and realization of such systems. Nevertheless, in order to create reliable datasets, current data collection and annotation methodologies often require a controlled environment while also the presence of the volunteer contributing to the process, or any subject for that matter, and an expert, monitoring the procedure, is mandatory. These processes are heavily restrained by the recent COVID-19 pandemic outbreak.To address such issues, in this paper we propose a human-centered Web-based dataset creation and annotation tool that utilizes the Web Bluetooth API. The user can effectively collect gestures from a nearby device that supports the BLE protocol, assign tags to the collected data, and store them remotely, in real-time. The data storage, as well as its annotation, can also be performed remotely by an expert stakeholder. An off-the-shelf wearable sensorial device has been used indicatively for our tool demonstration purposes. To the best of our knowledge, this is the first attempt that exploits the Web Bluetooth API capabilities for the development of a Browser-based real-time data collection, storage, and annotation tool. Our tool can be also expanded to other applications that use the sensing device with only minor configuration changes and is also operable through any smart-device that supports a Web-Browser. Furthermore, our tool’s performance matches that of native applications’. Finally, the tool is successfully deployed and validated by integrating it into our ongoing ML platform that is related to allergic rhinitis gesture recognition.

In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

We study the problem of finding an exact solution to the Consensus Halving problem. While recent work has shown that the approximate version of this problem is PPA -complete [29] , [30] , we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP -hard, and deciding whether there exists a solution with fewer than n cuts is ETR -complete. Along the way, we define a new complexity class, called BU , which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP ⊆ BU ⊆ TFETR and that LinearBU = PPA , where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit .

With solar parks being established as one of the most important renewable energy systems, there is a strong need for more efficient use of the services they provide, as well as error detection and performance issues confrontation. Internet of Things (IoT) technology, aims to fill the gap, by offering low cost and sustainable solutions towards the efficient operation of these parks. In this paper, we present an in situ monitoring and alerting system, based on WSN technologies, regarding the early detection of Potential Induced Degradation (PID) and Hotspots failures, that can cause a significant drop in solar panels' performance. In order to do so, specific non-trivial attributes such as temperature, humidity, irradiance, current and voltage are continuously monitored at panel level, and processed in a cloud based platform to early identify these phenomena. In particular, sensor nodes send data to a centralized local sink module using a multi-hop WSN architecture, in order to establish a robust and large coverage area. Afterwards, the information is propagated to the cloud server, where deterministic diagnostic algorithms are applied. We present the reference architecture of our approach, alongside the corresponding hardware and software structural, individual components, as well as the integration process and the use case that runs over a real solar park.

A lot of research has been contributed towards smart energy harvesting, efficient energy management and energy storage/supply capabilities, as they are considered a major bottleneck in Wireless Sensor Networks (WSNs). Similarly, there is an extreme interest to design new algorithms and protocols regarding energy harvesting prediction, load's energy consuming profiling, etc. Although those techniques improve energy efficiency, it still remains to solve the fundamental problem of energy provisioning in a more practical, real-life manner, as the majority of the hardware solutions choose to produce simple and robust implementations. In this paper, we present a smart energy management platform for low-power IoT systems that implements both energy harvesting and storage technologies but dynamically sets different power modes based on online monitoring measurements and energy harvesting prediction. With respect to power specifications our solution succeeds to both supply and inform the load system for future energy provisioning capability. Thus, our prototype can be characterised as a load agnostic device w.r.t. specification values, that can adjust to different conditions and use cases towards an effective system energy provisioning.

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph $G$ and a Hamiltonian cycle $C_0$ of $G$, how can we compute a second Hamiltonian cycle $C_1 \neq C_0$ of $G$? Cedric Smith proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is an algorithm which computes the second Hamiltonian cycle in time $O(n \cdot 2^{(0.3-\varepsilon)n})$ time, for some positive constant $\varepsilon>0$, and in polynomial space, thus improving the state of the art running time for solving this problem. Our algorithm is based on a fundamental structural property of Thomason's lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a Hamiltonian graph $G$ with a given Hamiltonian cycle $C_0$ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least $n - 4α(\sqrt{n}+2α)+8$, where $α= \frac{Δ-2}{δ-2}$ and $δ,Δ$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network Gs to a target network Gf from a family of networks having some good properties, like small diameter.

We study Crystal Structure Prediction, one of the major problems in computational chemistry. This is essentially a continuous optimization problem, where many different, simple and sophisticated, methods have been proposed and applied. The simple searching techniques are easy to understand, usually easy to implement, but they can be slow in practice. On the other hand, the more sophisticated approaches perform well in general, however almost all of them have a large number of parameters that require fine tuning and, in the majority of the cases, chemical expertise is needed in order to properly set them up. In addition, due to the chemical expertise involved in the parameter-tuning, these approaches can be biased towards previously-known crystal structures. Our contribution is twofold. Firstly, we formalize the Crystal Structure Prediction problem, alongside several other intermediate problems, from a theoretical computer science perspective. Secondly, we propose an oblivious algorithm for Crystal Structure Prediction that is based on local search. Oblivious means that our algorithm requires minimal knowledge about the composition we are trying to compute a crystal structure for. In addition, our algorithm can be used as an intermediate step by any method. Our experiments show that our algorithms outperform the standard basin hopping, a well studied algorithm for the problem.

Abstract In this paper, we study games with continuous action spaces and non-linear payoff functions. Our key insight is that Lipschitz continuity of the payoff function allows us to provide algorithms for finding approximate equilibria in these games. We begin by studying Lipschitz games, which encompass, for example, all concave games with Lipschitz continuous payoff functions. We provide an efficient algorithm for computing approximate equilibria in these games. Then we turn our attention to penalty games, which encompass biased games and games in which players take risk into account. Here we show that if the penalty function is Lipschitz continuous, then we can provide a quasi-polynomial time approximation scheme. Finally, we study distance biased games, where we present simple strongly polynomial time algorithms for finding best responses in $$L_1$$ L1 and $$L_2^2$$ L22 biased games, and then use these algorithms to provide strongly polynomial algorithms that find 2/3 and 5/7 approximate equilibria for these norms, respectively.

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) Gt of G, where t≥1. In this paper we study stochastic temporal graphs, i.e. stochastic processes G whose random variables are the snapshots of a temporal graph on G. A natural feature observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; i.e. the probability an edge e∈E appears at time step t depends on its appearance (or absence) at the previous k steps. We study the hierarchy of models of memory-k, k≥0, in an edge-centric network evolution setting: every edge of G has its own independent probability distribution for its appearance over time. We thoroughly investigate the complexity of two naturally related, but fundamentally different, temporal path problems, called Minimum Arrival and Best Policy.

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other “path-related” temporal notions, only few attempts have been made to investigate “non-path” temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.

Abstract We study a security game over a network played between adefenderandkattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of $$\lambda $$ λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizingdefense-optimalnetworks which allow for the bestequilibrium defense ratio; this is the ratio ofkover the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for $$\lambda $$ λ constantly close to 1 orn. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is $${\mathtt {NP}}$$ NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for thePrice of Defensefor any $$\lambda $$ λ ; this is the worst equilibrium defense ratio over all graphs.

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519–532, 2016) to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex—the “median”—which minimises a potential $$\varPhi $$ among the vertices of the candidates’ set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates’ set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential $$\varGamma $$ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential $$\varGamma $$ that allows querying approximate medians.

In this work we consider temporal networks, i.e. networks defined by a labeling $$\lambda $$ assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by $$\lambda $$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer $d$ we construct rather simple games with cost functions of degree at most $d$ which have a PoS of at least $\varOmega(\Phi_d)^{d+1}$, where $\Phi_d\sim d/\ln d$ is the unique positive root of the equation $x^{d+1}=(x+1)^d$. This almost closes the huge gap between $\varTheta(d)$ and $\Phi_d^{d+1}$. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of $\varOmega((1+1/\alpha)^d/d)$ on the PoS of $\alpha$-approximate Nash equilibria for singleton games. All our lower bounds hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of $\alpha$-approximate Nash equilibria, which is sensitive to the range $W$ of the player weights and the approximation parameter $\alpha$. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most $(d+3)/2$; the equilibrium's approximation parameter ranges from $\varTheta(1)$ to $d+1$ in a smooth way with respect to $W$. Second, we show that for unweighted congestion games, the PoS of $\alpha$-approximate Nash equilibria is at most $(d+1)/\alpha$.

We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n^60) states (O(1) + 60 log n bits of memory per agent) with probability 1-O((log log n)/n). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with omega(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.

In this work, we study the following basic question: “How much parallelism does a distributed task permit?” Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. For example, we may ask: “Can a given task be solved by a protocol that always has at least two processes in the same role at the same time?” (i.e., by a protocol that never elects a unique leader). We choose to initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. In particular, we define the role of a process at a given time to be equivalent to the state of the process at that time. Moreover, we isolate the symmetry that is due to the protocol (inherent symmetry) by focusing on those schedules that maximize symmetry for that protocol and observing how much symmetry breaking the protocol is forced to achieve in order to solve the problem. To allow for such symmetry maximizing schedules we consider parallel schedulers that in every step may select a whole collection of pairs of nodes (up to a perfect matching) to interact and not just a single pair. Based on these definitions of symmetric computation, we (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $$\Theta (N_{min})$$ , where $$N_{min}$$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates (that have some essentially different properties) and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol. The latter immediately generalizes to a subset of the predicates that are not closed under doubling.

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GREEDYMATCHING. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GREEDYMATCHING is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GREEDYMATCHING is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider three natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and computational tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GREEDYMATCHING on a special class of weighted graphs, called bushgraphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is ρ, then for every ε > 0 the randomized MRG algorithm of (Aronson et al. 1995) gives a (ρ − ε)-approximation for the maximum cardinality matching. We conjecture that a tightbound for ρ is 2/3; we prove our conjecture true for four subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem (Poloczek and Szegedy 2012). This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.

In this work, we study theoretical models of programmable matter systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes A and B can be transformed to each other is in P. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in PSPACE and study the problem of determining the minimum seeds that can make feasible otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes A,B of the same number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is Theta(n^2). We improve this to O(n) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by [Emamjomeh-Zadeh et al., STOC, 2016] to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates’ set for the target, while each query asks an appropriately chosen vertex– the "median"–which minimises a potential \Phi among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential \Gamma that allows querying approximate medians.

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels.

In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Population Protocol (APP) model, embarking from the well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In the APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of the size of the population), each of which can store an element from a totally ordered set S of samples. Whenever two agents interact with each other, they update their states and the values stored in their registers according to a joint transition function. This transition function is also restricted; it only allows (a) comparisons and (b) copy / paste operations for the sample values that are stored in the registers of the two interacting agents. Agents can only meet in pairs via a fair scheduler and are required to eventually converge to the same output value of the function that the protocol globally and stably computes. We present two different APPs for stably computing the median of the input values, initially stored on the agents of the population. Our first APP, in which every agent has 3 registers and no states, stably computes (with probability 1) the median under any fair scheduler in any strongly connected directed (or connected undirected) interaction graph. Under the probabilistic scheduler, we show that our protocol stably computes the median in O(n^6) number of interactions in a connected undirected interaction graph of n agents. Our second APP, in which every agent has 2 registers and O(n^2 log{n}) states, computes to the correct median of the input with high probability in O(n^3 log{n}) interactions, assuming the probabilistic scheduler and the complete interaction graph. Finally we present a third APP which, for any k, stably computes the k-th smallest element of the input of the population under any fair scheduler and in any strongly connected directed (or connected undirected) interaction graph. In this APP every agent has 2 registers and n states. Upon convergence every agent has a different state; all these states provide a total ordering of the agents with respect to their input values.

In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours. The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.

The $$3$$ -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter $$4$$ . Moreover, assuming the Exponential Time Hypothesis (ETH), $$3$$ -coloring cannot be solved in time $$2^{o(n)}$$ on graphs with $$n$$ vertices and diameter at most $$4$$ . In spite of extensive studies of the $$3$$ -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most $$2$$ , or at most $$3$$ , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most $$2$$ , we provide the first subexponential algorithm for $$3$$ -coloring, with complexity $$2^{O(\sqrt{n\log n})}$$ . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for $$3$$ -coloring on graphs with diameter $$2$$ that have at least one articulation neighborhood. For graphs with diameter at most $$3$$ , we establish the complexity of $$3$$ -coloring by proving for every $${\varepsilon \in [0,1)}$$ that $$3$$ -coloring is NP-complete on triangle-free graphs of diameter $$3$$ and radius $$2$$ with $$n$$ vertices and minimum degree $$\delta =\varTheta (n^{\varepsilon })$$ . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every $${\varepsilon \in [0,1)}$$ subexponential asymptotic lower bounds for the complexity of $$3$$ -coloring on triangle-free graphs with diameter $$3$$ and minimum degree $${\delta =\varTheta (n^{\varepsilon })}$$ . Finally, we provide a $$3$$ -coloring algorithm with running time $${ 2^{O\left( \min \{\delta \varDelta ,\ \frac{n}{\delta }\log \delta \}\right) }}$$ for arbitrary graphs with diameter $$3$$ , where $$n$$ is the number of vertices and $$ \delta $$ (resp. $$\varDelta $$ ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with $${\delta =\omega (1)}$$ and for graphs with $${\delta =O(1)}$$ and $$\varDelta =o(n)$$ . Due to the above lower bounds of the complexity of $$3$$ -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is $$\delta =\varTheta (n^{\varepsilon })$$ , where $${\varepsilon \in [\frac{1}{2},1)}$$ , as its time complexity is $${2^{O\left( \frac{n}{\delta } \log \delta \right) } = 2^{O\left( n^{1-\varepsilon } \log n\right) }}$$ and the corresponding lower bound states that there is no $$2^{o\left( n^{1-\varepsilon }\right) }$$ -time algorithm.

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into k supernodes, each being a line of log k nodes, for the largest such $k$. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.

In this work we consider temporal networks, the links of which are available only at random times (randomly available temporal networks). Our networks are {\em ephemeral}: their links appear sporadically, only at certain times, within a given maximum time (lifetime of the net). More specifically, our temporal networks notion concerns networks, whose edges (arcs) are assigned one or more random discrete-time labels drawn from a set of natural numbers. The labels of an edge indicate the discrete moments in time at which the edge is available. In such networks, information (e.g., messages) have to follow temporal paths, i.e., paths, the edges of which are assigned a strictly increasing sequence of labels. We first examine a very hostile network: a clique, each edge of which is known to be available only one random time in the time period {1,2, ..., n} (n is the number of vertices). How fast can a vertex send a message to all other vertices in such a network? To answer this, we define the notion of the Temporal Diameter for the random temporal clique and prove that it is Θ(log n) with high probability and in expectation. In fact, we show that information dissemination is very fast with high probability even in this hostile network with regard to availability. This result is similar to the results for the random phone-call model. Our model, though, is weaker. Our availability assumptions are different and randomness is provided only by the input. We show here that the temporal diameter of the clique is crucially affected by the clique's lifetime, a, e.g., when a is asymptotically larger than the number of vertices, n, then the temporal diameter must be Ω(a/nlog n ). We, then, consider the least number, r, of random points in time at which an edge is available, in order to guarantee at least a temporal path between any pair of vertices of the network (notice that the clique is the only network for which just one instance of availability per edge, even non-random, suffices for this). We show that r is Ω(log n) even for some networks of diameter 2. Finally, we compare this cost to an (optimal) deterministic allocation of labels of availability that guarantees a temporal path between any pair of vertices. For this reason, we introduce the notion of the Price of Randomness and we show an upper bound for general networks.

We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned “fitness” value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r > 0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r ≥ 1) and of extinction (for all r > 0).

As the Internet of Things (IOT) arises, the use of low-end devices on a daily basis increases. The wireless nature of communication that these devices provide raises security and privacy issues. For protecting a user's privacy, cryptography offers the tool of zero knowledge proofs (ZKP). In this paper, we study well-established ZKP protocols based on the discrete logarithm problem and we adapt them to the Elliptic Curve Cryptography (ECC) setting, which consists an ideal candidate for embedded implementations. Then, we implement the proposed protocols on Wiselib, a generic and open source algorithmic library. For the first time, we present a thorough evaluation of the protocols on two popular hardware platforms equipped with low end microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers, in terms of code size, execution time, message size and energy requirements. This work's results can be used from developers who wish to achieve certain levels of privacy in their applications.

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.

In this work, we overview some results concerning communication combinatorial properties in random intersection graphs and uniform random intersection graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we present and discuss results concerning the existence of large independent sets of vertices whp in random instances of each of these models. As the main contribution of our paper, we introduce a new, general model, which we denote G(V, χ, f). In this model, V is a set of vertices and χ is a set of m vectors in ℝm. Furthermore, f is a probability distribution over the powerset 2χof subsets of χ. Every vertex selects a random subset of vectors according to the probability f and two vertices are connected according to a general intersection rule depending on their assigned set of vectors. Apparently, this new general model seems to be able to simulate other known random graph models, by carefully describing its intersection rule.

We propose a new theoretical model for passively mobile wireless sensor networks, called P M , standing for passively mobile machines . The main modification w.r.t. the population protocol model (Angluin et al., 2006) [30] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE ( f ( n ) ) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O ( f ( n ) ) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O ( log n ) memory, and use it to provide an exact characterization of the classes PMSPACE ( f ( n ) ) when f ( n ) = Ω ( log n ) : they are precisely the classes of all symmetric predicates in NSPACE ( n f ( n ) ) . As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω ( log n ) . We next explore the computability of the PM model when the protocols use o ( log log n ) space per machine and prove that SEM = PMSPACE ( f ( n ) ) when f ( n ) = o ( log log n ) , where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O ( log log n ) .

We propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver,from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.

We examine multi-player pervasive games that rely on the use of ad-hoc mobile sensor networks. The unique feature in such games is that players interact with each other and their surrounding environment by using movement and presence as a means of performing game-related actions, utilizing sensor devices. We briefly discuss the fundamental issues and challenges related to these type of games and the scenarios associated with them. We have also developed a framework, called Fun in Numbers (FinN) that handles a number of these issues, such as such as neighbors discovery, localization, synchronization and delay-tolerant communication. FinN is developed using Java and is based on a multilayer architecture, which provides developers with a set of templates and services for building and operating new games

Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the game authority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes’ freedom of choice. Namely, we reduce the price of malice.

We investigate random intersection graphs, a combinatorial model that quite accurately abstracts distributed networks with local interactions between nodes blindly sharing critical resources from a limited globally available domain. We study important combinatorial properties (independence and hamiltonicity) of such graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we prove that, interestingly, a small constant number of random, resource selections suffices to make the graph Hamiltonian and we provide tight evaluations of the independence number of these graphs.

In this work we study the problem of scheduling tasks with dependencies in multiprocessor architectures where processors have different speeds. We examine the energy-efficiency and time efficiency of scheduling in an asymmetric system.

We consider algorithmic questions concerning the existence, tractability, and quality of Nash equilibria, in atomic congestion games among users participating in selfish coalitions. We introduce a coalitional congestion model among atomic players and demonstrate many interesting similarities with the noncooperative case. For example, there exists a potential function proving the existence of pure Nash equilibria (PNE) in the unrelated parallel links setting; in the network setting, the finite improvement property collapses as soon as we depart from linear delays, but there is an exact potential (and thus PNE) for linear delays. The price of anarchy on identical parallel links demonstrates a quite surprising threshold behavior: It persists on being asymptotically equal to that in the case of the noncooperative KP-model, unless the number of coalitions is sublogarithmic . We also show crucial differences, mainly concerning the hardness of algorithmic problems that are solved efficiently in the noncooperative case. Although we demonstrate convergence to robust PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized fully mixed Nash equilibrium that can be efficiently constructed in most cases. Finally, we propose a natural improvement policy and prove its convergence in pseudopolynomial time to PNE which are robust against (even dynamically forming) coalitions of small size.

Today we are experiencing a major reconsideration of the computing paradigm, as witnessed by the abundance and increasing frequency of use of terms such as ambient intelligence, ubiquitous computing, disappearing computer, grid computer, global computing and mobile ad-hoc networks. Systems that can be described with such terms are of a dynamic, with no clear physical boundary, nature and it seems that it is impossible (or, at least, difficult) to define sharply a number of important properties holding with certainty as well as holding throughout the whole lifetime of the system. One such system property, which is important for the viability of a system, is trust. Our departure point is the assumption that it seems very difficult to define static system properties related to trust and expect that they hold eternally in the rapidly changing systems falling under the new computing paradigm. One should, rather, attempt to define trust in terms of properties that hold with some limiting probability as the system grows and try to establish conditions that ensure that "good" properties hold almost certainly. Based on this viewpoint, in this paper we provide a new framework for defining trust through formally definable properties that hold, almost certainly, in the limit in randomly growing combinatorial structures that model "shapeless" computing systems (e.g., ad-hoc networks), drawing on results that establish the threshold behavior of predicates written in the first and second order logic

Wireless sensor networks are comprised of a vast number of ultra-small autonomous computing, communication and sensing devices, with restricted energy and computing capabilities, that co-operate to accomplish a large sensing task. Such networks can be very useful in practice, e.g. in the local monitoring of ambient conditions and reporting them to a control center. In this paper we propose a distributed group key establishment protocol that uses mobile agents (software) and is particularly suitable for energy constrained, dynamically evolving ad-hoc networks. Our approach totally avoids the construction and the maintenance of a distributed structure that reflects the topology of the network. Moreover, it trades-off complex message exchanges by performing some amount of additional local computations in order to be applicable at dense and dynamic sensor networks. The extra computations are simple for the devices to implement and are evenly distributed across the participants of the network leading to good energy balance. We evaluate the performance of our protocol in a simulated environment and compare our results with existing group key establishment protocols. The security of the protocol is based on the Diffie-Hellman problem and we used in our experiments its elliptic curve analog. Our findings basically indicate the feasibility of implementing our protocol in real sensor network devices and highlight the advantages and disadvantages of each approach given the available technology and the corresponding efficiency (energy, time) criteria.

Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [12, 26]. A Leader can decrease the coordination ratio by assigning flow αr on M, and then all Followers assign selfishly the (1 - α)r remaining flow. This is a Stackelberg Scheduling Instance (M,r,α), 0 ≤ α ≤ 1. It was shown [23] that it is weakly NP-hard to compute the optimal Leader's strategy.For any such network M we efficiently compute the minimum portion βM of flow r needed by a Leader to induce M's optimum cost, as well as his optimal strategy.Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling αr flow can induce ≤ 1 α times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example.

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 scheduling mechanisms, while the latter is defined as the number of update operations performed on rates of individual sessions until max-min fairness is reached. Optimistic algorithms allow any session to intermediately receive a rate larger than its max-min fair rate; bottleneck algorithms finalize the rate of a session only if it is restricted by a certain, highly congested link of the network. In this work, we present a comprehensive collection of lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, bottleneck, rate-based flow control algorithms. Say that an algorithm is oblivious if its scheduling mechanism uses no information of either the session rates or the network topology. We present a novel, combinatorial construction of a capacitated network, which we use to establish a fundamental lower bound of $\frac{dn}{4} + \frac{n}{2}$ on the convergence complexity of any oblivious algorithm, where n is the number of sessions laid out on a network, and d, the session dependency, is a measure of topological dependencies among sessions. Moreover, we devise a novel simulation proof to establish that, perhaps surprisingly, the lower bound of $\frac{dn}{4} + \frac{n}{2}$ on convergence complexity still holds for any partially oblivious algorithm, in which the scheduling mechanism is allowed to use information about session rates, but is otherwise unaware of network topology. On the positive side, we prove that the lower bounds for oblivious and partially oblivious algorithms are both tight. We do so by presenting optimal oblivious algorithms, which converge after $\frac{dn}{2} + \frac{n}{2}$ update operations are performed in the worst case. To complete the picture, we show that linear convergence complexity can indeed be achieved if information about both session rates and network topology is available to schedulers. We present a counterexample, nonoblivious algorithm, which converges within an optimal number of n update operations. Our results imply a surprising convergence complexity collapse of oblivious and partially oblivious algorithms, and a convergence complexity separation between (partially) oblivious and nonoblivious algorithms for optimistic, bottleneck rate-based flow control.

We present the NanoPeers architecture paradigm, a peer-to-peer network of lightweight devices, lacking all or most of the capabilities of their computer-world counterparts. We identify the problems arising when we apply current routing and searching methods to this nanoworld, and present some initial solutions, using a case study of a sensor network instance; Smart Dust. Furthermore, we propose the P2P Worlds framework as a hybrid P2P architecture paradigm, consisting of cooperating layers of P2P networks, populated by computing entities with escalating capabilities. Our position is that: (i) experience gained through research and experimentation in the field of P2P computing, can be indispensable when moving down the stair of computing capabilities, and that (ii) the proposed framework can be the basis of numerous real-world applications, opening up several challenging research problems.

We introduce a new model of ad-hoc mobile networks, which we call hierarchical, that are comprised of dense subnetworks of mobile users (corresponding to highly populated geographical areas, such as cities), interconnected across access ports by sparse but frequently used connections (such as highways). For such networks, we present an efficient routing protocol which extends the idea (introduced in [4]) of exploiting the co-ordinated motion of a small part of an ad-hoc mobile network (the "support") to achieve very fast communication between any two mobile users of the network. The basic idea of the new protocol presented here is, instead of using a unique (large) support for the whole network, to employ a hierarchy of (small) supports (one for each city) and also take advantage of the regular traffic of mobile users across the interconnection highways to communicate between cities. We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the basic "support" idea presented in [4].

Article An efficient communication strategy for ad-hoc mobile networks Share on Authors: Ioannis Chatzigiannakis Computer Technology Institute, Patras, Greece Computer Technology Institute, Patras, GreeceView Profile , Sotiris Nikoletseas Computer Technology Institute, Patras, Greece Computer Technology Institute, Patras, GreeceView Profile , Paul Spirakis Computer Technology Institute, Patras, Greece Computer Technology Institute, Patras, GreeceView Profile Authors Info & Claims PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computingAugust 2001 Pages 320–322https://doi.org/10.1145/383962.384053Published:01 August 2001 34citation438DownloadsMetricsTotal Citations34Total Downloads438Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we analyze the stability properties of the FIFO protocol in the Adversarial Queueing model for packet routing. We show a graph for which FIFO is stable for any adversary with injection rate r ≰ 0.1428. We generalize this results to show upper bound for stability of any network under FIFO protocol, answering partially an open question raised by Andrews et al. in [2]. We also design a network and an adversary for which FIFO is non-stable for any r ≱ 0.8357, improving the previous known bounds of [2].

A new model for intrusion and its propagation through various attack schemes in networks is considered. The model is characterized by the number of network nodes, and two parameters f and g. Parameter f represents the probability of failure of an attack to a node and is a gross measure of the level of security of the attacked system and perhaps of the in truder's skills;g represents a limit on the number of attacks that the intrusion software can ever try, when it issues them from a particular (broken) network node,due to the danger to be discovered. The success of the attack scheme is characterized by two factors: the number of nodes captured (the spread factor) and the number of virtual links that a defense mechanism has to trace from any node where the attack is active to the origin of the intrusion (the traceability factor). The goal of an intruder is to maximize both factors. In our model, we present four different ways (attack schemes) by which an intruder can organize his attacks. Using analytic and experimental methods, we first show that for any O < f < 1, there exists a constant g for which any of our attack schemes can achieve a Θ (n) spread and traceability factor with high probability, given sufficient propagation time. We also show for three of our attack schemes that the spread and the traceability factors are, with high probability, linearly related during the whole duration of the attack propagation. This implies that it will not be easy for a detection mechanism to trace the origin of the intrusion, since it will have to trace a number of links proportional to the nodes captured.

We study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network users, each employing a mixed strategy which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum expected latency over all links is minimized. We consider both uniform and non-uniform link capacities.

No abstract available.

We present a combinatorial framework for the study of a natural class of distributed optimization problems that involve decision-making by a collection of n distributed agents in the presence of incomplete information; such problems were originally considered in a load balancing setting by Papadimitriou and Yannakakis (Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, pp. 61–64, August 1991). For any given decision protocol and assuming no communication among the agents, our framework allows to obtain a combinatorial inclusion-exclusion expression for the probability that no “overflow” occurs, called the winning probability, in terms of the volume of some simple combinatorial polytope.

In this work we propose simple and efficient protocols for counting and leader election in mobile networks.For mobile networks with fixed base stations we provide a new and very efficient protocol for counting the number of mobile hosts.The main part of the work concentrates on ad-hoc networks (no fixed subnetwork).We provide a model for these networks and leader election (and a special form of counting) protocols for both named and anonymous mobile hosts.In this work we define two protocol classes, the Non-Compulsoryprotocols, which do not affect the motion of the hosts and the Compulsory, which determine the motion of some or all the hosts.By assuming that the mobile hosts move as if each one is doing a continuous random walk on their allowable space S of motions, and by assuming a universal time, we show that our leader election protocol terminates (with high probability and also on the average) in time asymptotically linear to the size of the space S, measured as its volume divided by the volume of the sphere defined by the range of transmission of each mobile host.We also provide a simple but very efficient Compulsory (forced random walks) Las Vegas protocol for leader election in ad-hoc networks, which also allows counting, with termination detection.Our analysis techniques for the meeting time of concurrent random walks extend the known facts and are tight.They may be used as an analysis tool in the design of many other distributed protocols.This is the first algorithmic and characterization work, to our knowledge, for ad-hoc networks.

In this paper we present an efficient general simulation strategy for computations designed for fully operational BSP machines of n ideal processors, on n-processor dynamic-fauhprone BSP machines.The fault occurrences are fail-stop and fully dynamic, i.e., they are ahowed to happen on-line 'This work was partially

In this paper general simulations of algorithms designed for fully operational BSP machines on BSP machines with faulty processors or unavailable processors are developed. The fail-stop model is considered, that is, if a processor fails or becomes unavailable it remains so until the end of the computation. The faults are random, that is, a processor may fail independently with probablility a, a is a constant. Two possible settings for fault occurence are considered: the faults are either static (the faulty or unavailable processors are already known at the start of the computation) or dynamic (the processors become faulty or unavailable during the computation). In the case of static faults, a simulation of an n-processor fault-free BSP machine on a faulty n-processor BSP machine is presented with constant slowdown per local computation step and O(log n \\Delta maxfL; gg) slowdown per communication step, given that a preprocessing has been done that needs O(log 2 n \\Delta maxfL; gg)...

We present a unified approach for delivering hypermedia/multimedia objects over broadband networks. Documents are stored in various multimedia servers, while the inline data may reside in their own media servers, attached to the multimedia servers. The described service consists of several multimedia servers and a set of functions that intend to present to the end user interactive information in real time. Users interact with the service requesting multimedia documents on demand. Various media streams are transmitted over different parallel connections according to their transmission requirements. The hypermedia documents are structured using a hypermedia markup language that keeps information of the spatio temporal relationships among document's media components. In order to deal with the variant network behavior, buffering manipulation mechanisms and grading of the transmitted media quality techniques are proposed to smooth presentation and synchronization anomalies.

No abstract available.

A quantitative comparison of the BSP and LogP models for parallel computation is developed.Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis.It is also shown that the two models can be implemented with similar performance on most point-to-point networks.In conclusion, within the limits of our analysis that is mainly of asymptotic nature, BSP and LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation.BSP seems somewhat preferable due to greater simplicity and portability, and slightly greater power.

Let X1,…,Xc be variables which together constitute a composite register. These variables are shared by a number of processes which operate in a totally asynchronous and wait-free manner. An operation by a process on the composite register is either a write to one of the variables or a read of the values of all variables. All operations are required to be atomic, i.e. an execution of any number of them (including reads) must be linearizable, in a way consistent with the values returned by the reads. In a single reader composite register no two reads can concurrently access the composite register. We give a new protocol implementing a single reader composite register for the case when there is a single writer per variable. Our construction uses time-stamps that may take values as large as the number of operations performed. The advantages of our construction over previous (bounded time-stamps) solutions are: (i) Both the protocol and its formal correctness proof are easy to understand. (ii) The time complexity of an operation of our construction (i.e. the number of its sub-operations) and the number of the subregisters used in our construction are at most equal to the number of processes that can concurrently access the composite register.

This paperl discusses the efi-iciency of a parallel text retrieval system that is based on the Vector Space Model.Specifically, we describe a general parallel retrieval algorithm for use with this model, the application of the algorithm in the FIRE system [I], and its implementation on the high performance GCe131512 Parsytec parallel machine [2].The use of this machine's t we-dimensional grid of processors provides an efficient baais for the virtual tree that lies at the heart of our retrieval algorithm.Analytical and experimental evidence is presented to demonstrate the efficiency of the algorithm.

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c*/spl ap/4.2. We provide the first non-trivial upper bound on the value of c*, showing that for c>4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.>

No abstract available.

We address the problem of reading several variables (components) X/sub 1/,...,X/sub c/, all in one atomic operation, by only one process, called the reader, while each of these variables are being written by a set of writers. All operations (i.e., both reads and writes) are assumed to be totally asynchronous and wait-free. For this problem, only algorithms that require at best quadratic time and space complexity can be derived from the existing literature. (The time complexity of a construction is the number of suboperations of a high-level operation and its space complexity is the number of atomic shared variables it needs) In this paper, we provide a deterministic protocol that has linear (in the number of processes) space complexity, linear time complexity for a read operation, and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Also, introducing randomness in the location where the reader gets the value that it returns, we get a conceptually very simple probabilistic algorithm. This algorithm has an overwhelmingly small, controllable probability of error. Its space complexity, and also the time complexity of a read operation, are sublinear. The time complexity of a write is constant. On the other hand, under the Archimedean time assumption, we get a protocol whose time and space complexity do not depend on the number of writers, but are linear in the number of components only. (The time complexity of a write operation is still constant.).>

This paper shows that the problem of testing whether a graph G contains an induced subgraph of vertex (edge) connectivity at least k is P-complete for any fixed $k \geqslant 3$. Moreover, if $k_{\max } $ is the largest vertex (edge) connectivity of any subgraph of G, it is shown that unless ${\text{P}} = {\text{NC}}$ there is no NC algorithm that approximates $k_{\max } $ within any approximation factor $\frac{1}{2} < c < 1$ (such an algorithm is by definition one that outputs a number in the interval $[ck_{\max } ,k_{\max } ]$). In contrast, it is known that the problem of finding the Tutte (triconnected) components of G (i.e., the maximal subgraphs of G such that for any four vertices in any of them, any two of these vertices can be connected by a path in G that avoids the other two) is in NC. On the positive side, it is shown, by proving extremal graph results, that the maximum k for which there is a k-edge-connected induced subgraph of G can be approximated in NC for any approximation factor strictly less than $\frac{1}{2}$ and that the same is true for vertex connectivity for any approximation factor strictly less than $\frac{1}{4}$.

Article Free Access Share on Combining tentative and definite executions for very fast dependable parallel computing Authors: Z. M. Kedem Ecole des Hautes Etudes en Informatique, Université René Descartes, 45, rue des Saints-Pères, 75006 Paris, France and Department of Computer Science, New York University, 251 Mercer St., New York, NY Ecole des Hautes Etudes en Informatique, Université René Descartes, 45, rue des Saints-Pères, 75006 Paris, France and Department of Computer Science, New York University, 251 Mercer St., New York, NYView Profile , K. V. Palem IBM Research Division, T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NYView Profile , A. Raghunathan Computer Science Division, University of California, Davis, CA and New York University Computer Science Division, University of California, Davis, CA and New York UniversityView Profile , P. G. Spirakis Computer Technology Institute, Patras University, P. O. Box 1122, 26110 Patras, Greece Computer Technology Institute, Patras University, P. O. Box 1122, 26110 Patras, GreeceView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 381–390https://doi.org/10.1145/103418.103459Published:03 January 1991Publication History 57citation260DownloadsMetricsTotal Citations57Total Downloads260Last 12 Months14Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Multistage interconnection networks with crossbar switches are a major component of parallel machines. In this paper we analyze Banyan networks of k by k switches and with finite buffers. The exact solution of the steady state distribution of the first stage is derived in the situation where packets are lost when they encounter a full buffer (Assumption A). The solution is a linear combination of k-1 geometrics. We use this to get an approximation for the steady state distributions in the second stage and beyond. As a side effect, the infinite buffer case is solved, confirming known results. Our results are validated by extensive simulations. An alternate situation of networks where full buffers may block previous switches is also analyzed through an approximation technique (Assumption B).

A parallel computing system becomes increasingly prone to failure as the number of processing elements in it increases.In this paper, we describe a completely general strategy that takes an arbitrary step of an ideal CRCW PRAM and automatically translates it to run efficiently and robustly on a PRAM in which processors are prone to failure.The strategy relies on efficient robust algorithms for solving a core problem, the Certified Write-All Problem.This problem characterizes the core of robustness, because, as we show, its complexity is equal to that of any general strategy for realizing robustness in the model.We analyze the expected parallel time and work of various algorithms for solving this problem.Our results are a non-trivial generalization of Brent's

It is shown that the problem of testing whether a graph G contains a vertex- (edge-) connected induced subgraph of cardinality k is P-complete for any fixed k>or=3. Moreover, it is shown that approximating within a factor c>1/2 the maximum d for which there is a d-vertex-(d-edge-) connected induced subgraph of G is not in NC, unless P=NC. In contrast, it is known that the problem of finding the Tutte (triconnected) components of G is in NC. On the positive side, it is shown by proving extremal-graph results, that the maximum d for which there is a d-edge-connected induced subgraph of G can be approximated in NC within any factor c>

Article Free Access Share on Lower bounds and efficient algorithms for multiprocessor scheduling of dags with communication delays Authors: H. Jung Mathematics Dept., Humboldt Univ., GDR Mathematics Dept., Humboldt Univ., GDRView Profile , L. Kirousis Computer Technology Institute, Patras Univ., Greece Computer Technology Institute, Patras Univ., GreeceView Profile , P. Spirakis Computer Technology Institute, Patras Univ., Greece and Courant Inst. Math. Sciences, NYU Computer Technology Institute, Patras Univ., Greece and Courant Inst. Math. Sciences, NYUView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 254–264https://doi.org/10.1145/72935.72962Published:01 March 1989Publication History 24citation304DownloadsMetricsTotal Citations24Total Downloads304Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Although many sophisticated parallel algorithms now exist, most of them are not sensitive to properties of the input which can be determined only at run-time. For example, in the case of parallel addition in shared memory models, we intuitively understand that we should not add those inputs whose value is zero. A technique which exploits this idea may beat the general lower bound for addition if the count of nonzero operants is much smaller than the numbers to be added. In this paper, we device such algorithms for two fundamental problems of parallel computation. Our model of computation is the CRCW PRAM. We first provide a randomized algorithm for parallel addition which never errs and computes the result in O (log m ) expected parallel time, where m is the count of nonzero entries among the n numbers to be added. This algorithm uses O ( m ) shared space. We then use this result to solve an interesting problem of processor identification. All our techniques enjoy the following properties: 1. (1) They never produce an erroneous answer. 2. (2) If T is the actual parallel time and E ( T ) its expected value, then Prob { T > k · E ( T )} ≤ n − c , where k is arbitrary and c > 1 is linear on k and can be specified by the implementor of the algorithm. 3. (3) Our algorithms do not know m initially, but they produce an accurate estimate for it.

Our work deals with the analysis of the queueing delays of buffered multistage Banyan networks of multiprocessors. We provide tight upper bounds on the mean delays of the second stage and beyond, in the case of infinite buffers. Our results are validated by simulations performed on a network simulator constructed by us. The analytic work for network stages beyond the first, provides a partial answer to open problems posed by previous research.

When serially re-usable multi-unit resources are shared among many processes, each of which has exclusive control over some resource units, it is possible for deadlocks to happen. The work of Holt (1971) stated the problem of deadlock detection as a directed multigraph problem. In this paper we examine the possibility of existence of fast parallel algorithms for deadlock detection. Although many graph problems have efficient parallel solutions (in parallel polylogarithmic time, by using only a polynomial number of processors), we present strong evidence that this is not the case for the general deadlock detection problem. We show that the problem is complete in Punder log-space reductions and thus probably not efficiently parallelizable. Fortunately, when the problem is restricted (e.g., single-unit requests of processes or single-unit resources), then it falls in NC. We present efficient parallel algorithms for the restricted versions of the deadlock detection problem.

Article Free Access Share on A semantic approach to correctness of concurrent transaction executions Authors: Alexander Tuzhilin View Profile , Paul G. Spirakis View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 85–95https://doi.org/10.1145/325405.325416Published:25 March 1985Publication History 5citation98DownloadsMetricsTotal Citations5Total Downloads98Last 12 Months15Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean “flag” variables, each of which can be written by only one process and read by at most one other process. No global bounds in the speeds of processes are assumed. Processes with speed zero are considered dead. However, when their speed is nonzero then they execute their programs correctly. Dead processes do not harm our algorithms’ performance with respect to pairs of other running processes. When the rate of change of the ratio of speeds of neighbour processes (i.e., relative acceleration) is bounded, then any two of these processes will establish communication within a constant number of steps of the slowest process with high likelihood. So, our implementation has the property of achieving relative real time response. We can use our techniques to solve other problems such as resource allocation and implementation of parallel languages such as CSP and Ada. Note that we do not have any probability assumptions about the system behaviour, although our algorithms use the technique of probabilistic choice.

We have obtaincd some results in pebble coordination problems and the diameter of permutation groups.

This paper considers a fixed (possibly infinite) set of distributed asynchronous processes, which at various times are willing to communicate with each other.Each process has various ports, each of which is used for communication with a distinct neighbor process.Each process can have at most one port open at any time, and its other ports must be closed.Two processes handshake over a time interval A if their respective ports are open for mutual communication during this interval.Note that the handshake relation is a matching.Successful communication requires a handshake of at least one step of each process; during the one-step overlap a message can be transmitted between processes.The problem is to synchronize processes (via a distributed scheduler) so that they can successfully handshake at their will, given that the means of synchronization is some low-level construct that does not guarantee the handshake property if used in an unsophisticated way.Probabilistic distributed algorithms for synchronizing processes so that they can handshake at will are described.A process is considered to be tame over a time interval A if its speed varies within certain arbitrarily fixed nonzero bounds.Our synchronization algorithms are shown to have real-time response: If a pair of processers are mutually willing to communicate within a time interval A of length at least a given constant and the pair are tame on A, then they establish communication within A with high likelihood (for the worst case behavior of the system), and the expected time for establishment of communication is also constant.Our model and algorithms are applied to solve a large class of real-time resource allocation problems, as well as real-time implementation of the synchronization primitives of Hoare's multiprocessing language CSP.

In this paper we consider a resource allocation problem which is local in the sense that the maximum number of users competing for a particular resource at any time instant is bounded and also at any time instant the maximum number of resources that a user is willing to get is bounded. The problem may be viewed as that of achieving matchings in dynamically changing hypergraphs, via a distributed algorithm. We show that this problem is related to the fundamental problem of handshake communication (which can be viewed as achieving matchings in a dynamically changing graph, via distributed algorithms) in that an efficient solution to each of them implies an efficient solution to the other. We provide real-time solutions to the resource allocation problem (that is, we give distributed algorithms with real time response). We make essential use of probabilistic techniques as first used by [Rabin, 80b], where processes are allowed to make independent probabilistic choices. On the other hand, no probability assumptions about the system behavior are made. One of our solutions assumes the existence of an underlying real-time handshake communication system, as described in [Reif, Spirakis, 81]. Our other solution is based on efficient synchronization by flag variables, which are written only by one process and read by at most one other process. The special case of equi-speed processes is first examined. Then we generalize to asynchronous processes. Applications are made to dining philosophers, scheduling and two-phase locking in databases.

This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per real time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean "flag" variables, each of which can be written by only one process and read by at most one other process.No global bounds in the speeds of processes are assumed. Processes with speed zero are considered dead. However, when their speed is nonzero then they execute their programs correctly. Dead processes do not harm our algorithms' performance with respect to pairs of other running processes. When the rate of change of the ratio of speeds of neighbour processes (i.e., relative acceleration) is bounded, then any two of these processes will establish communication within a constant number of steps of the slowest process with high likelihood. Thus our implementation has the property of achieving relative real time response. We can use our techniques to solve other problems such as resource allocation and implementation of parallel languages such as CSP and ADA. Note that we do not have any probability assumptions about the system behavior, although our algorithms use the technique of probabilistic choice.

This paper considers a fixed (possibly infinite) set π of distributed asynchronous processes which at various times are willing to communicate with each other.

We introduce a new random structure generalizing matroids. These random matroids allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs.