In the ever-changing environment of edge cloud systems, it is necessary to allocate diverse cloud resources in an efficient manner, at the same time, reducing energy consumption. A simple distributed resource allocation model is proposed in a previous study that utilizes a pseudo cost function of resource load, and it is shown that a convex function allows energy saving by pooling idle edge servers. In this paper, we extend this cost model beyond simple load, and present a method to balance computation and communication by merging multiple constraints into the cost function. We show trade-offs among soft constraints along with energy saving effects by simulation, using specific scenarios with computational and communication constraints. Our simulation results show that the combination of a convex function with a polynomial penalty function works well for balancing energy saving and other soft constraints.

In a ridesharing service, driver-rider matching affects the business in several ways. Not only does it cost money to find a route on a map, but it also has an impact on the business in terms of driver income and rider waiting times, and therefore their satisfaction. It is not practical to field test the matching. For example, an A/B test would take days. A simulator greatly accelerates matching experiments. We modeled ridesharing and developed a simulator based on it. The event-driven simulator enabled us to test matching algorithms with a variety of parameters while utilizing routing systems, such as OSRM. Tested matching techniques are back-to-back and reassignment, that determine the matching targets. The simulations showed that back-to-back reduced the average waiting time for riders by up to around 40% and reassignment reduced it by up to around 15%. It is also the contribution of this paper to show what ridesharing operators are thinking about in order to technically optimize their business.

The "Fediverse", a federation of decentralized social media servers, has emerged after a decade in which centralized platforms like X (formerly Twitter) have dominated the landscape. The structure of a federation should affect user activity, as a user selects a server to access the Fediverse and posts are distributed along the structure. This paper reports on the differences in user activity between Twitter and Mastodon, a prominent example of decentralized social media. The target of the analysis is Japanese posts because both Twitter and Mastodon are actively used especially in Japan. Our findings include a larger number of replies on Twitter, more consistent user engagement on mstdn.jp, and different topic preferences on each server.

We discuss key management for cryptocurrencies from the perspective of security and risk management. While we found many earlier research studies about the implementation and security of wallets, few of them provide a comprehensive analysis of real-world integration as a complex system. We particularly focus on cryptocurrency custodians, who have to tightly control the risk to meet business needs as well as regulatory requirements. Unlike individual use cases, to manage substantial amounts of various assets, they typically need more complex wallet configurations and operations, such as multiple layers of hot and cold wallets in combination with different types of implementations. Therefore, we discuss the suitability of various wallet techniques, including software, hardware, HSMs, smart contracts, or cryptographic methods. We also address several open challenges for custodians mentioned in earlier work. Furthermore, as the ultimate example, we propose Extreme-Cold, a reference cold wallet in an air-gapped environment. It is resistant to side-channel attacks studied in earlier research. The risk assessment we conduct on Extreme-Cold demonstrates the effectiveness of our systematized knowledge.

Virtual assets are globally recognized as a decentralized digital currency system. They are also being used to transfer criminal proceeds. In 2019, the Financial Action Task Force mandated the Travel Rule for virtual asset service providers (VASPs). However, as of March 2024, it has not been fully implemented worldwide due to the Sunrise issue. Complying with the Travel Rule poses challenges such as identifying the recipient VASP from a virtual asset address, proving ownership of the address, and ensuring communication protocols between the VASPs. In this paper, we focus on these three challenges and provide potential approaches for each, along with additional considerations. We have analyzed multiple existing protocols and categorized their characteristics. Our findings revealed that the majority of them are based on an alliance of VASPs, while there are a few solutions that suggest peer-to-peer messaging for every VASP or blockchain as a communication hub. Additionally, we offer insights into open challenges that need to be solved in the long term.

A blockchain network simulator SimBlock was developed to enable large-scale blockchain researches. Since it was released in June 2019, it has facilitated number of studies on blockchain performance and security. We demonstrate how such a simulator enables blockchain studies by showing experiments running on SimBlock.

Forks in a blockchain sacrifice security. In this paper, we propose a protocol for quickly propagating block generation notifications in the blockchain network quickly to reduce the fork rate. Block generation notifications contain a Bloom filter that represents transactions in the generated block. Thus, when nodes receive a block generation notification, they can start mining the next block. In experiments in which a simulator is used, we compared the propagation time of a block generation notification with that of a block in the existing protocol. As a result, the propagation time of the 50 %ile is 41.1 % of an existing protocol, the 90 %ile is 39.2 % of the existing protocol, and the fork rate calculated from the average propagation time is 40.8 % of the existing protocol.

In a public blockchain, the block propagation time has a significant impact on the performance, security and fairness of mining. Reducing the propagation time can increase the transaction processing performance, reduce the fork rate, and increase security. We propose a method to improve block propagation with block sender switchover, even if a node is receiving a block. The method is not vulnerable to eclipse attacks because the neighboring nodes are not changed. Our simulation shows that the proposed method improves the 90th percentile value of the propagation time by up to 18% and the fork rate by up to 7.9%.

Analysis of social networks with limited data access is challenging for third parties. To address this challenge, a number of studies have developed algorithms that estimate properties of social networks via a simple random walk. However, most existing algorithms do not assume private nodes that do not publish their neighbors’ data when they are queried in empirical social networks. Here we propose a practical framework for estimating properties via random walk-based sampling in social networks involving private nodes. First, we develop a sampling algorithm by extending a simple random walk to the case of social networks involving private nodes. Then, we propose estimators with reduced biases induced by private nodes for the network size, average degree, and density of the node label. Our results show that the proposed estimators reduce biases induced by private nodes in the existing estimators by up to 92.6% on social network datasets involving private nodes.

Skip Graph is a structured overlay that preserves the order of keys and provides efficient routing, especially for complex queries such as range queries. However, existing routing methods for range queries in Skip Graph have problems such as long path lengths and a large number of messages because of inefficiencies. In this paper, we propose a new routing method for range queries named Detouring Range Search (DRS), that provides more efficient routing by utilizing detour routes. In the proposed method, each node that receives a query divides the target range into subranges based on the center of the subordinate node sequence and delegates them to its neighbor nodes. Our evaluation experiments show that the proposed method can reduce the average path length by approximately 20% compared with that of an existing method when the number of nodes is sufficiently large.

Analyzing social graphs with limited data access is challenging for third-party researchers. To address this challenge, a number of algorithms that estimate structural properties via a random walk have been developed. However, most existing algorithms are limited to the estimation of local structural properties. Here we propose a method for restoring the original social graph from the small sample obtained by a random walk. The proposed method generates a graph that preserves the estimates of local structural properties and the structure of the subgraph sampled by a random walk. We compare the proposed method with subgraph sampling using a crawling method and the existing method for generating a graph that structurally resembles the original graph via a random walk. Our experimental results show that the proposed method more accurately reproduces the local and global structural properties on average and the visual representation of the original graph than the compared methods. We expect that our method will lead to exhaustive analyses of social graphs with limited data access.

In general, deep neural networks (DNNs) achieve higher accuracy as the amount of training data increases. However, training data are often privacy sensitive, and they may not be collected. There are several methods that leave the training data decentralized in a wide area network and share models. These methods update the models locally based on stochastic gradient descent (SGD) and communicate to aggregate the models. The network bandwidth, training data, and machines are heterogeneous in a wide area network unlike distributed DNNs which use a computer cluster. Due to heterogeneity, the methods using synchronous communication, such as all-reduce SGD, are not suitable, and gossip SGD using asynchronous communication is a dominant method. In this paper, we show that when the network bandwidth is heterogeneous, conventional gossip SGD causes network congestion, and the learning efficiency is not greatly different from the case in which the network bandwidth is homogeneous. We show that the congestion problem can be solved by adjusting the communication frequency, that is, by training multiple times and communicating once. In many works, learning in local nodes and communicating with other nodes are alternated. Furthermore, we propose a warm-up technique to improve the learning efficiency. This proposed technique decreases the amount of communication with nodes that require a long communication time. We verify the effect of the proposed technique in experiments using CIFAR-10 and CIFAR-100.

Skip Graph, one of the structured overlays, provides a scalable network owing to the routing path lengths of O (log n), where$n$denotes the total number of nodes. However, there is a problem that most of the routing paths are quite longer than the shortest paths because each node in the network knows only its neighbors, rather than the global topology. In general, long routing paths lead to long delay times and low fault tolerance. Herein, we propose Detouring Skip Graph, which shortens the path lengths through the use of detour routes. It does not require construction of extra links or modification of its topology; thereby, it can succeed in shortening them while maintaining the advantages of Skip Graph. The evaluation experiments show that the average path length was shortened by approximately 20%-30% in comparison with Skip Graph.

Publish/subscribe is a communication model for exchanging messages via a broker while providing loose coupling. So far, several studies have been conducted to address load concentration on the broker by forming distributed brokers. However, although they achieve higher throughput by load distribution among multiple brokers, these existing studies require an increased latency for message delivery. In this paper, we propose a novel method to construct and maintain an adaptive topology that features both scalability and immediacy in distributed publish/subscribe messaging. The proposed method is for topic-based publish/subscribe systems and uses a number of brokers to form an overlay network. Its topology changes dynamically to compose a subgraph for each topic in a single-hop or multi-hop manner according to the topic load (i.e., the number of clients). The experimental results show that compared to existing studies, the proposed method reduces the delivery path length, which is a principal factor that affects latency. Especially for low load topics, the reduction rate of the proposed method reaches values greater than 60%.

Improving transaction throughput is an important challenge for Bitcoin. However, shortening the block generation interval or increasing the block size to improve throughput makes it sharing blocks within the network slower and increases the number of orphan blocks. Consequently, the security of the blockchain is sacrificed. To mitigate this, it is necessary to reduce the block propagation delay. Because of the contribution of new Bitcoin protocols and the improvements of the Internet, the block propagation delay in the Bitcoin network has been shortened in recent years. In this study, we identify impacts of compact block relay—an up-to-date Bitcoin protocol—and Internet improvement on the block propagation delay and fork rate in the Bitcoin network from 2015 to 2019. Existing measurement studies could not identify them but our simulation enables it. The experimental results reveal that compact block relay contributes to shortening the block propagation delay more than Internet improvements. The block propagation delay is reduced by 64.5% for the 50th percentile and 63.7% for the 90th percentile due to Internet improvements, and by 90.1% for the 50th percentile and by 87.6% for the 90th percentile due to compact block relay.

In Bitcoin and Ethereum, nodes require large storage capacity to maintain all the blockchain data, such as transactions, UTXOs, and account states. As of May 2020, the storage size of the Bitcoin blockchain has expanded to 270 GB, and it will continue to increase. This storage requirement is a major hurdle to becoming a block proposer or validator. Although many studies have attempted to reduce the storage size, in the proposed methods, a node cannot keep all blocks or cannot generate a block. We propose an architecture called Trail that allows nodes to hold all blocks in a small storage and to generate and validate blocks and transactions. Trail does not depend on a consensus algorithm or fork choice rule. In this architecture, a client who issues transactions has the data to prove its own balances and can generate a transaction containing the proof of balances. The nodes in Trail do not store transactions, UTXOs and account balances: they keep only blocks. The blocksize is approximately 8 KB, which is 100 times smaller than that of Bitcoin. Further, the block size is constant regardless of the number of accounts and the number of transactions. Compared to traditional blockchains, clients who issue transactions must store additional data. However, we show that proper data archiving can keep the account device storage size small. Trail allows more users to be block proposers and validators and improves the decentralization of the blockchain.

Accurately analyzing graph properties of social networks is a challenging task because of access limitations to the graph data. To address this challenge, several algorithms to obtain unbiased estimates of properties from few samples via a random walk have been studied. However, existing algorithms do not consider private nodes who hide their neighbors in real social networks, leading to some practical problems. Here we design random walk-based algorithms to accurately estimate properties without any problems caused by private nodes. First, we design a random walk-based sampling algorithm that comprises the neighbor selection to obtain samples having the Markov property and the calculation of weights for each sample to correct the sampling bias. Further, for two graph property estimators, we propose the weighting methods to reduce not only the sampling bias but also estimation errors due to private nodes. The proposed algorithms improve the estimation accuracy of the existing algorithms by up to 92.6% on real-world datasets.

Several recently devised machine learning (ML) algorithms have shown improved accuracy for various predictive problems. Model searches, which explore to find an optimal ML algorithm and hyperparameter values for the target problem, play a critical role in such improvements. During a model search, data scientists typically use multiple ML implementations to construct several predictive models; however, it takes significant time and effort to employ multiple ML implementations due to the need to learn how to use them, prepare input data in several different formats, and compare their outputs. Our proposed framework addresses these issues by providing simple and unified coding method. It has been designed with the following two attractive features: i) new machine learning implementations can be added easily via common interfaces between the framework and ML implementations and ii) it can be scaled to handle large model configuration search spaces via profile-based scheduling. The results of our evaluation indicate that, with our framework, implementers need only write 55-144 lines of code to add a new ML implementation. They also show that ours was the fastest framework for the HIGGS dataset, and the second-fastest for the SECOM dataset.

Structured overlays enable the construction of application-level networks from multiple nodes, and the decentralized searching of data in the network. One such structured overlay is the skip graph, which supports range queries. Each node in a skip graph has multi-level shortcut links. The degree of each node is O(log N) on a network with N nodes. The paper, proposes Ballistic Skip Graph, a structured overlay that reduces the degree of each node to O(1) by limiting the number of shortcut links to a randomly selected single level while supporting range queries. Because the nodes are not grouped, the proposed method requires no extensive reconfiguration of the network when nodes join or leave. An evaluation experiment confirmed that the average routing table size is confined to a small constant.

In Skip Graph, a structured overlay, each node constructs its routing table by choosing connected nodes based on its membership vector. However, membership vectors are determined randomly; therefore, nodes do not always form an ideal topology. This can cause the route length to be long. Therefore, we propose Self-Refining Skip Graph, a structured overlay where each node refines its routing table toward an ideal Skip Graph topology. Our proposed method has shorter route length as approaching to an ideal topology while maintaining the robustness derived from the mechanism of membership vectors. Our evaluation confirms that the topology approaches to an ideal one and that the route length becomes shorter than that in Skip Graph.

A structured overlay running as the base of a DHT or ALM occasionally receives a large number of messages collectively. Those cases are opportunities for an overlay to bundle multiple different messages into a single message and achieve extraordinarily effective message deliveries. Such message bundling reduces the number packet transmissions on an underlay network such as an IP network. This paper presents Collective Forwarding, a message bundling technique for structured overlays. The technique not only reduces the number of packet transmissions but also improves throughput of message forwarding. In experiments, the number of packet transmissions and the time to get items were reduced to 12% and 9.7% respectively at best. Theoretical analysis matches and then supports the experimental results.

There have been proposed protocols to achieve causal consistency with a distributed data store that does not make safety guarantees. Such a protocol works with an unmodified data store if it is implemented as middleware or a shim layer while it can be implemented inside a data store. But the middleware approach has required modifications to applications. Applications have to specify explicitly data dependency to be managed. On the contrary, our Letting-It-Be protocol handles all the implicit dependency naturally resulting from data accesses though it is implemented as middleware. Our protocol does not require any modifications to either data stores or applications. It trades performance for the merit to some extent. Throughput declines from a bare data store were 21% in the best case and 78% in the worst case.

Development of a decent parallel simulator is challenging work. It should achieve enough performance, scalability and fault tolerance. Our proposal is utilizing general-purpose data processing engines such as MapReduce implementations for parallel simulation. Widely used and mature engines take away a large part of the development effort and support scalability and fault tolerance. We demonstrate that a parallel discrete-event simulator can be implemented on such engines, Apache Hadoop and Apache Spark, by modeling message passing of distributed systems on MapReduce key-value processing model. Implemented simulators could handle 108 nodes with 10 computers. Preliminary evaluation showed that our Spark-based simulator is about 20 times as fast as an existing simulator thanks to Time Warp.

Structured overlays enable a number of nodes to construct a logical network autonomously and search each other. Skip Graph, one of the structured overlays, constructs an overlay network based on Skip List structure and supports range queries for keys. Skip Graph manages routing tables based on random digits; therefore, the deviation of them disturbs effective utilization of the routing table entries and increases path length than the ideal value. We therefore propose FRT-Skip Graph, a novel structured overlay that solves the issues of Skip Graph and provides desirable features not in Skip Graph. FRT-Skip Graph is designed based on Flexible Routing Tables and supports range queries similarly to Skip Graph. Furthermore, it provides features derived from FRT, namely, dynamic routing table size and high extensibility.

An overlay network enables a large number of sensor nodes to perform effectively data collection and message delivery. Geographical routing is necessary for applications such as sensor network and it requires the overlay network to reflect nodes' locations. In addition, nodes' locations are generally biased and path lengths on the overlay should be short, in other words, the number of nodes relaying a message should be small. This paper describes a new overlay routing algorithm to perform geographical routing on a two-dimensional space satisfying the above requirements. The proposed algorithms provides unique and desirable features derived from Flexible Routing Tables (FRT), that is a design framework for structured overlays, because the algorithm is designed based on FRT. The derived features are dynamic routing table size and high extensibility. The proposed algorithm adopts P2P Delaunay Network as its topology and forms shortcut links based on estimated number of hops.

Using the Cloud for large-scale distributed simulations, such as agent-based traffic simulations, sounds like a good idea, as it is possible to provision and release easily processing nodes (e.g., Virtual machines) in the Cloud. However, the question is complex as it involves users' objectives, such as, time to process the simulation and cost of the simulation, and because the workload evolves in distributed simulations, in each node and the whole system, and this impact the resource provisioning plans. This paper proposes two main contributions: (i) a method for efficient utilization of computational resources for distributed agent-based simulations, providing a mechanism that adapts the resource provisioning to users' objectives and workload evolution, and (ii) a staged asynchronous migration technique to limit the migration overhead when the number of workers change. Our preliminary experimental results on a 24 hour scenario of traffic in the city of Tokyo show that our system outperforms a static provisioning by 12% in average and 23% during periods when workload changes a lot.

There have been P2P systems with simultaneous millions of nodes on Internet. But existing simulators and techniques cannot simulate such a large scale. Even parallelized simulators have not solved the scale problem. They provide large memory and hold a large number of nodes but the speed of simulation degrades significantly than sequential simulation due to much overhead of inter-server synchronization. We propose a simulation technique for large-scale P2P systems based on an optimistic parallel discrete event simulation model. The technique employs low cost synchronization techniques that are effective for P2P simulation.

A large fraction of structured overlays work efficiently as long as node identifiers follow a uniform distribution with high probability. There is another kind of structured overlay supporting non-uniform node identifier distributions and it enables a DHT to support range queries. This paper presents FRT-Chord#, such a structured overlay for non-uniform node identifier distributions. It is based on Flexible Routing Tables (FRT), a method for designing structured overlays, and inherits advantageous features of FRT, that existing overlays do not hold. Such features include extensibility, arbitrary routing table capacity.

In structured overlays, nodes forward a query hop by hop to deliver it to the responsible node for the query. Each node maintains its routing table and determines the next hop by referring to the routing table. Each node has its node identifier and determines which other nodes to be on its routing table based on node distance, that is defined by difference of node identifiers or the number of nodes between two nodes in identifier order. In existing structured overlays, routing table construction and maintenance based on node distance enable efficient lookup, that is a small number of hop counts to the responsible node. We found out that efficient lookup does not require node distance in routing table construction and maintenance. As an example, this paper presents Flow-based Flexible Routing Tables (FFRT), a routing table construction method solely based on query flows. In an FFRT-based overlay, a node calculates query flows, that is the amount of queries forwarded to each node on its routing table. And the node maintains its routing table toward a state in which all nodes on the table have equal query flows. FFRT also provides such a practical merit as it performs efficient lookups though node and queries' target identifiers are distributed nonuniformly. The merit enables range query support.

In many structured overlays, nodes strictly maintain their routing tables using node identifiers. However, building routing tables while taking account of the physical network is difficult. We propose proximity-aware flexible routing tables (PFRT) in this paper as a method to systematically design proximity-aware routing algorithms for structured overlays. PFRT was developed by extending the flexible routing tables (FRT) method such that network proximity is considered. Routing tables in FRT-and PFRT-based algorithms are updated according to the order of the set of all routing table patterns. FRT-based algorithms define a total order based on node identifiers, whereas PFRT-based algorithms define two total orders based on node identifiers and network proximity. Because PFRT is a simple extension of FRT, PFRT-based algorithms also have many of the advantageous features of FRT. We extended Chord to design PFRT-Chord, which is a PFRT-based algorithm. Experimental results showed that PFRT-Chord preserves the expected FRT-derived properties and it could take account of network proximity.

A cloud storage with persistence shows solid performance only with a read heavy or write heavy workload. There is a trade-off between the read-optimized and write-optimized design of a cloud storage. This is dominated by its storage engine, which is a software component for managing data stored on memory and disk. A storage engine can be pluggable with an adequate software design though today's cloud storages are not always modular. We developed a modular cloud storage called MyCassandra to demonstrate that such a cloud storage can be read-optimized and write-optimized with a modular design. Various storage engines can be introduced into MyCassandra and they determine with what workload the cloud storage can perform well. With MyCassandra we proved that such a modular design enables a cloud storage to adapt to workloads.

This paper presents Flexible Routing Tables (FRT), a method for designing routing algorithms for overlay networks. FRT facilitates extending routing algorithms to reflect factors other than node identifiers. An FRT-based algorithm defines a total order on the set of all patterns of a routing table, and performs identifier-based routing according to that order. The algorithm gradually refines its routing table along the order by three operations: guarantee of reachability, entry learning, and entry filtering. This paper presents FRT-Chord, an FRT-based distributed hash table, and gives proof that it achieves O(log N)-hop lookups. Experiments with its implementation show that the routing table refining process proceeds as designed. Grouped FRT (GFRT), which introduces node groups into FRT, is also presented to demonstrate FRT's flexibility. GFRT-Chord resulted in a smaller numbers of routing hops between node groups than both Chord and FRT-Chord.

Many structured overlays forward messages based not only on node identifiers but also on the other factors such as network proximity. It is an essential requirement for a visualization system to exhibit how the factors are considered in a overlay. Such a visualization system allows us to grasp intuitively characteristics of an overlay algorithm. If this is achieved, differences between algorithms become more distinguishable, and those who are unfamiliar with an algorithm are also able to know improvement between algorithms. Thus, such a visualization increases their interests in research activity in peer-to-peer computing. In this demonstration we propose a novel 3D visualization system for structured overlays. The system is practically able to visualize how routing algorithms consider node groups in an effective manner. We demonstrate the system with Chord and GFRT-Chord algorithms, but the system is able to visualize algorithms not limited to them.

This paper presents middleware enabling mutual and equal transfer of computing power between individuals, as in the original idea behind P2P, while also supporting large-scale distributed computation utilizing heterogeneous PCs. This goal is strongly supported by a network overlay over which peers can communicate with each other directly and bidirectionally. We made use of a general-purpose P2P library, JXTA, supporting the common requirements of P2P software, including network overlay. Other features of the P2P library, such as ad-hoc self-organization, discovery and grouping of peers, also support our middleware efficiently. In this paper, we propose and evaluate an application of those P2P concepts to virtual resource transfer and parallel computation with aggregated resources. However, such a P2P library imposes a certain amount of overhead on the middleware in terms of communication performance. Measured communication performance and throughput of an application program shows the feasibility of the application of P2P concepts. The middleware achieves 100 /spl times/ 10/sup 6/ bps communication performance and over a 20 fold increase in speed with 32 computers, even though the granularity of workunits is as fine as less than a second.