
Becker, F., Kosowski, A., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., et al. (2015). Allowing each node to communicate only once in a distributed system: shared whiteboard models. Distrib. Comput., 28(3), 189–200.
Abstract: In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graphtheoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.



Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2021). The role of randomness in the broadcast congested clique model. Inf. Comput., 281, 104669.
Abstract: We study the role of randomness in the broadcast congested clique model. This is a messagepassing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.
This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:
If more than one round is allowed, public randomness is as powerful as private randomness.
Oneround publiccoin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds.
Oneround publiccoin algorithms can be exponentially more powerful than oneround privatecoin algorithms.
Oneround privatecoin algorithms can be exponentially more powerful than oneround deterministic algorithms.



BorquezParedes, D., Beghelli, A., Leiva, A., Jara, N., Lozada, A., Morales, P., et al. (2022). Agentbased distributed protocol for resource discovery and allocation of virtual networks over elastic optical networks. J. Opt. Commun. Netw., 14(8), 667–679.
Abstract: Network virtualization is a key enabling technology for “Infrastructure as a Service” provisioning, increasing the flexibility and cost savings offered to customers. By extending the concept of server virtualization to the network infrastructure, the allocation of different, independent virtual networks over a single physical network is carried out on demand. A fundamental challenge in network virtualization systems is to choose which physical nodes and links to use for hosting virtual networks in the physical infrastructure, known as the “virtual network allocation” problem. All virtual network allocation proposals on elastic optical networks assume a centralized operation, deploying a single node with access to the network state global information and assigning resources accordingly. However, such configuration might exhibit the inherent problems of centralized systems: survivability and scalability. In this paper, we present a distributed protocol for resource discovery, mapping, and allocation of network virtualization systems. The distributed protocol is generic enough as to be used with different substrate networks. However, in this paper, it has been adapted to work over an elastic optical network infrastructure, where further considerations regarding the spectrum continuity and contiguity constraints must also be taken into account. The distributed protocol is based on the concept of alliances: upon the arrival of a virtual network request, agents located in the physical network nodes compete to form the first alliance able to host the virtual network. Because the first alliances to be formed are also the ones composed by nearby nodes, a good network resource usage is achieved. The feasibility of the distributed protocol was studied by evaluating its ability to successfully establish virtual networks within acceptable time and with low bandwidth consumption from the coordination messages.



Canessa, E., & Riolo, R. L. (2006). An agentbased model of the impact of computermediated communication on organizational culture and performance: an example of the application of complex systems analysis tools to the study of CIS. J. Inf. Technol., 21(4), 272–283.
Abstract: Organizations that make use of computer information systems (CIS) are prototypical complex adaptive systems (CAS). This paper shows how an approach from Complexity Science, exploratory agentbased modeling (ABM), can be used to study the impact of two different modes of use of computermediated communication (CMC) on organizational culture (OC) and performance. The ABM includes stylized representations of (a) agents communicating with other agents to complete tasks; (b) an OC consisting of the distribution of agent traits, changing as agents communicate; (c) the effect of OC on communication effectiveness (CE), and (d) the effect of CE on task completion times, that is, performance. If CMC is used in a broad mode, that is, to contact and collaborate with many, new agents, the development of a strong OC is slowed, leading to decreased CE and poorer performance early on. If CMC is used in a local mode, repeatedly contacting the same agents, a strong OC develops rapidly, leading to increased CE and high performance early on. However, if CMC is used in a broad mode over longer time periods, a strong OC can develop over a wider set of agents, leading to an OC that is stronger than an OC which develops with local CMC use. Thus broad use of CMC results in overall CE and performance that is higher than is generated by local use of CMC. We also discuss how the dynamics generated by an ABM can lead to a deeper understanding of the behavior of a CAS, for example, allowing us to better design empirical longitudinal studies.



Goles, E., & Moreira, A. (2012). NumberConserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs. J. Cell. Autom., 7(2), 151–165.
Abstract: We perform a numerical exploration of numberconserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only nontrivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.



Goles, E., Guillon, P., & Rapaport, I. (2011). Traced communication complexity of cellular automata. Theor. Comput. Sci., 412(30), 3906–3916.
Abstract: We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.



Goles, E., Meunier, P. E., Rapaport, I., & Theyssier, G. (2011). Communication complexity and intrinsic universality in cellular automata. Theor. Comput. Sci., 412(12), 2–21.
Abstract: The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of spacetime rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.



Goles, E., Moreira, A., & Rapaport, I. (2011). Communication complexity in numberconserving and monotone cellular automata. Theor. Comput. Sci., 412(29), 3616–3628.
Abstract: One third of the elementary cellular automata (CAs) are either numberconserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved.



Gonzalez, E., Epstein, L. D., & Godoy, V. (2012). Optimal number of bypasses: minimizing cost of calls to wireless phones under Calling Party Pays. Ann. Oper. Res., 199(1), 179–191.
Abstract: In telecommunications, Calling Party Pays is a billing formula that prescribes that the person who makes the call pays its full cost. Under CPP landline to wireless phone calls have a high cost for many organizations. They can reduce this cost at the expense of installing wireless bypasses to replace landline to wireless traffic with wirelesstowireless traffic, when the latter is cheaper than the former. Thus, for a given timehorizon, the cost of the project is a tradeoff between traffic towireless and the number of bypasses. We present a method to determine the number of bypasses that minimizes the expected cost of the project. This method takes into account hourly varying traffic intensity. Our method takes advantage of parallels with inventory models for rental items. Examples illustrate the economic value of our approach.



Jimenez, D., Barrera, J., & Cancela, H. (2023). Communication Network Reliability Under Geographically Correlated Failures Using Probabilistic Seismic Hazard Analysis. IEEE Access, 11, 31341–31354.
Abstract: The research community's attention has been attracted to the reliability of networks exposed to largescale disasters and this has become a critical concern in network studies during the last decade. Earthquakes are high on the list of those showing the most significant impacts on communication networks, and simultaneously, they are the least predictable events. This study uses the Probabilistic Seismic Hazard Analysis method to estimate the network element state after an earthquake. The approach considers a seismic source model and ground prediction equations to assess the intensity measure for each element according to its location. In the simulation, nodes fail according to the building's fragility curves. Similarly, links fail according to a failure rate depending on the intensity measure and the cable's characteristics. We use the sourceterminal, and the diameter constrained reliability metrics. The approach goes beyond the graph representation of the network and incorporates the terrain characteristics and the component's robustness into the network performance analysis at an affordable computational cost. We study the method on a network in a seismic region with almost 9000 km of optical fiber. We observed that for sourceterminal that are less than 500 km apart the improvements are marginals while for those that are more than 1000 km apart, reliability improves near a 30% in the enhanced designs. We also showed that these results depend heavily on the robustness/fragility of the infrastructure, showing that performance measures based only the network topology are not enough to evaluate new designs.



Mascareno, A., Goles, E., & Ruz, G. A. (2016). Crisis in complex social systems: A social theory view illustrated with the chilean case. Complexity, 21(S2), 13–23.
Abstract: The article argues that crises are a distinctive feature of complex social systems. A quest for connectivity of communication leads to increase systems' own robustness by constantly producing further connections. When some of these connections have been successful in recent operations, the system tends to reproduce the emergent pattern, thereby engaging in a nonreflexive, repetitive escalation of more of the same communication. This compulsive growth of systemic communication in crisis processes, or logic of excess, resembles the dynamic of selforganized criticality. Accordingly, we first construct the conceptual foundations of our approach. Second, we present three core assumptions related to the generative mechanism of social crises, their temporal transitions (incubation, contagion, restructuring), and the suitable modeling techniques to represent them. Third, we illustrate the conceptual approach with a percolation model of the crisis in Chilean education system. (c) 2016 Wiley Periodicals, Inc. Complexity 21: 1323, 2016



Villenas, F. I., Vargas, F. J., & Peters, A. A. (2023). A KalmanBased Compensation Strategy for Platoons Subject to Data Loss: Numerical and Empirical Study. Mathematics, 11(5), 1228.
Abstract: This article considers a homogeneous platoon with vehicles that communicate through channels prone to data loss. The vehicles use a predecessorfollowing topology, where each vehicle sends relevant data to the next, and data loss is modeled through a Bernoulli process. To address the lossy communication, we propose a strategy to estimate the missing data based on the Kalman filter with intermittent observations combined with a linear extrapolation stage. This strategy enables the followers to better deal with data dropouts. We compare this approach to one purely based on the linear extrapolation of previous data. The performance of both strategies is analyzed through Monte Carlo simulations and experiments in an ad hoc testbed, considering various data loss and transmission loss probabilities depending on the intervehicle distance. The results show that for the considered cases, the proposed strategy outperforms the linear extrapolation approach in terms of tracking and estimation error variances. Our results also show that the proposed strategy can achieve string stability for the mean and variance for both the tracking and estimation errors in scenarios where the basic extrapolation strategy cannot.

