We study robust and efficient distributed algorithms for building and maintaining distributed data structures in dynamic Peer-to-Peer (P2P) networks. P2P networks are characterized by a high level of dynamicity with abrupt heavy node churn (nodes that join and leave the network continuously over time). We present a novel algorithmic framework to build and maintain, with high probability, a skip list for poly(n) rounds despite a churn rate of 𝒪(n/log n), which is the number of nodes joining and/or leaving per round; n is the stable network size. We assume that the churn is controlled by an oblivious adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Importantly, the maintenance overhead in any interval of time (measured in terms of the total number of messages exchanged and the number of edges formed/deleted) is (up to log factors) proportional to the churn rate. Furthermore, the algorithm is scalable in that the messages are small (i.e., at most polylog(n) bits) and every node sends and receives at most polylog(n) messages per round. To the best of our knowledge, our work provides the first-known fully-distributed data structure and associated algorithms that provably work under highly dynamic settings (i.e., high churn rate that is near-linear in n). Furthermore, the nodes operate in a localized manner. Our framework crucially relies on new distributed and parallel algorithms to merge two n-element skip lists and delete a large subset of items, both in 𝒪(log n) rounds with high probability. These procedures may be of independent interest due to their elegance and potential applicability in other contexts in distributed data structures. Finally, we believe that our framework can be generalized to other distributed and dynamic data structures including graphs, potentially leading to stable distributed computation despite heavy churn.

Ridesharing platforms have gained prominence as a primary transportation mode in urban areas due to their accessibility, cost-effectiveness, and increased convenience. However, their centralized nature introduces apprehensions regarding privacy vulnerabilities and susceptibility to single-point of failure attacks. In response to these challenges, blockchain-based ridesharing systems have emerged as a potential solution, offering decentralization and enhanced privacy features to instil trust among users in the system. The existing decentralized systems do not coordinate route choices among drivers, which results in drivers prioritizing routes with the highest passenger density. This phenomenon leads to spatial convergence of drivers at specific locations, which consequently diminishes the platform’s utility. To overcome this, we propose a game theory-based route planning framework wherein drivers collaborate to determine the optimal route, considering the collective actions of all the drivers involved. We demonstrate that the routing game converges to Nash equilibrium by constructing a potential function for the game and proving it is a potential game. The potential nature of the game allows the proposed model to apply a distributed algorithm which converges to Nash equilibrium within a few iterations. Since fairness is an important criterion for the long-term stability of the system, we integrate fairness into the architecture of our system and propose a cooperative fair potential route planning game wherein the income of all the drivers is optimized. Experimental results demonstrate superior performance by our proposed model in comparison to the existing baselines.

Federated learning has emerged as a promising paradigm for collaborative machine learning, enabling multiple clients to train a model while preserving data privacy jointly. Tailored federated learning takes this concept further by accommodating client heterogeneity and facilitating the learning of personalized models. While the utilization of transformers within federated learning has attracted significant interest, there remains a need to investigate the effects of federated learning algorithms on the latest focal modulation-based transformers. In this paper, we investigate this relationship and uncover the detrimental effects of federated averaging (FedAvg) algorithms on Focal Modulation, particularly in scenarios with heterogeneous data. To address this challenge, we propose TransFed, a novel transformer-based federated learning framework that not only aggregates model parameters but also learns tailored Focal Modulation for each client. Instead of employing a conventional customization mechanism that maintains client-specific focal modulation layers locally, we introduce a learn-to-tailor approach that fosters client collaboration, enhancing scalability and adaptation in TransFed. Our method incorporates a hyper network on the server, responsible for learning personalized projection matrices for the focal modulation layers. This enables the generation of client-specific keys, values, and queries.Furthermore, we provide an analysis of adaptation bounds for TransFed using the learn-to-customize mechanism. Through intensive experiments on datasets related to pneumonia classification, we demonstrate that TransFed, in combination with the learn-to-tailor approach, achieves superior performance in scenarios with non-IID data distributions, surpassing existing methods. Overall, TransFed paves the way for leveraging focal Modulation in federated learning, advancing the capabilities of focal modulated transformer models in decentralized environments.

In recent years, ride-hailing services have emerged as a popular means of transportation for the residents of urban areas. There is an inequality in the spatio-temporal distribution of demand and supply, which requires the proper recommendation of routes to drivers in order to guide them towards riders optimally. This paper provides a review of different route recommendation strategies that have been applied in ride-hailing platforms with the main focus on fairness, and environmental issues. It is important to consider the environmental aspects of route recommendation systems as the transportation sector is one of the major sources of air pollution and has reduced the life expectancy of people around the globe. Moreover, there is an unfair distribution of resources and opportunities among the drivers and riders of the platform which has affected their long-term sustainability in the market. In this paper, we highlight the critical challenges and opportunities inherent in the design of green and fair route recommendation systems and indicate some possible directions for future research.

Recommending routes by their probability of having a rider has long been the goal of conventional route recommendation systems. While this maximizes the platform-specific criteria of efficiency, it results in sub-optimal outcomes with the disparity among the income of drivers who work for similar time frames. Pioneer studies on fairness in ridesharing platforms have focused on algorithms that match drivers and riders. However, these studies do not consider the time schedules of different riders sharing a ride in the ridesharing mode. To overcome this shortcoming, we present the first route recommendation system for ridesharing networks that explicitly considers fairness as an evaluation criterion. In particular, we design a routing mechanism that reduces the inequality among drivers and provides them with routes that have a similar probability of finding riders over a period of time. However, while optimizing fairness the efficiency of the platform should not be affected as both of these goals are important for the long-term sustainability of the system. In order to jointly optimize fairness and efficiency we consider repositioning drivers with low income to the areas that have a higher probability of finding riders in future. While applying driver repositioning, we design a future-aware policy and allocate the areas to the drivers considering the destination of requests in the corresponding area. Extensive simulations on real-world datasets of Washington DC and New York demonstrate superior performance by our proposed system in comparison to the existing baselines.

In signed networks, each edge is labeled as either positive or negative. The edge sign captures the polarity of a relationship. Balance of signed networks is a well-studied property in graph theory. In a balanced (sub)graph, the vertices can be partitioned into two subsets with negative edges present only across the partitions. Balanced portions of a graph have been shown to increase coherence among its members and lead to better performance. While existing works have focused primarily on finding the largest balanced subgraph inside a graph, we study the network design problem of maximizing balance of a target community (subgraph). In particular, given a budget b and a community of interest within the signed network, we aim to make the community as close to being balanced as possible by deleting up to b edges. Besides establishing NP-hardness, we also show that the problem is non-monotone and non-submodular. To overcome these computational challenges, we propose heuristics based on the spectral relation of balance with the Laplacian spectrum of the network. Since the spectral approach lacks approximation guarantees, we further design a greedy algorithm, and its randomized version, with provable bounds on the approximation quality. The bounds are derived by exploiting pseudo-submodularity of the balance maximization function. Empirical evaluation on eight real-world signed networks establishes that the proposed algorithms are effective, efficient, and scalable to graphs with millions of edges.

We use queueing networks to present a new approach to solving Laplacian systems. Our distributed solver works for a large and important class of Laplacian systems that we call "one-sink" Laplacian systems, i.e., systems of the form Lx = b where exactly one of the coordinates of b is negative. Our solver is a distributed algorithm that takes ~O(thit dmax) time (where ~O hides poly log n factors) to produce an approximate solution where thit is the worst-case hitting time of the random walk on the graph, which is Θ(n) for a large set of important graphs, and dmax is the generalized maximum degree of the graph. The class of one-sink Laplacians includes the important voltage computation problem and allows us to compute the effective resistance between nodes in a distributed setting. As a result, our Laplacian solver can be used to adapt the approach by Kelner and Madry (2009) to give the first distributed algorithm to compute approximate random spanning trees efficiently.