# Anonymous Network - Explore the Science & Experts | ideXlab

## Anonymous Network

The Experts below are selected from a list of 13836 Experts worldwide ranked by ideXlab platform

### Roger Wattenhofer – One of the best experts on this subject based on the ideXlab platform.

• ##### DISC – Randomness vs. Time in AnonymousNetworks
Lecture Notes in Computer Science, 2015
Co-Authors: Jochen Seidel, Jara Uitto, Roger Wattenhofer

Abstract:

In an Anonymous Network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the algorithm.

Since any randomized Anonymous Network algorithm can be decomposed into a randomized 2-hop coloring stage and a deterministic stage, we tackle the question by focusing on the randomized stage. We establish that for any reasonable target function f, there is a randomized 2-hop coloring scheme running in $$\mathcal {O} fn$$ time. Our coloring scheme allows to trade an increase in runtime by a factor of d for a decrease by the $$d^\text {th}$$ root in the random bit complexity.

To show that the achieved trade-off is asymptotically optimal for any choice of f, we establish a trade-off lower bound. Our bounds yield that it is sufficient to consider the cases when f is between $$\Omega \log ^*n$$ and $$\mathcal {O} \log \log n$$. We obtain that for the two extreme cases, i.e., where $$f \in \Theta \log ^*n$$ and $$f \in \Theta \log \log n$$, the random bit complexity is $$\Theta \root d \of {n}$$ and $$\Theta \log n$$, respectively, for any constant d. The trade-off achieved by our scheme is asymptotically optimal for any f, i.e., reducing the runtime must lead to an increase in the random bit complexity.

• ##### Randomness vs. Time in AnonymousNetworks
, 2015
Co-Authors: Jochen Seidel, Jara Uitto, Roger Wattenhofer

Abstract:

In an Anonymous Network, symmetry breaking tasks can only be solved if randomization is available. But how many random bits are required to solve any such task? As it turns out, the answer to this question depends on the desired runtime of the algorithm. Since any randomized Anonymous Network algorithm can be decomposed into a randomized 2-hop coloring stage and a deterministic stage, we tackle the question by focusing on the randomized stage. We establish that for any reasonable target function f, there is a randomized 2-hop coloring scheme running in O(f(n)) time. Our coloring scheme allows to trade an increase in runtime by a factor of d for a decrease by the dth root in the random bit complexity. To show that the achieved trade-off is asymptotically optimal for any choice of f, we establish a trade-off lower bound. Our bounds yield that it is sufficient to consider the cases when f is between Ω(log∗ n) and O(log log n). We obtain that for the two extreme cases, i.e., where f ∈ Θ(log∗ n) and f ∈ Θ(log log n), the random bit complexity is Θ( d√ n) and Θ(log n), respectively, for any constant d. The trade-off achieved by our scheme is asymptotically optimal for any f, i.e., reducing the runtime must lead to an increase in the random bit complexity.

• ##### Computability in AnonymousNetworks: Revocable vs. Irrecovable Outputs
Automata Languages and Programming, 2014
Co-Authors: Yuval Emek, Jochen Seidel, Roger Wattenhofer

Abstract:

What can be computed in an Anonymous Network, where nodes are not equipped with unique identifiers? It turns out that the answer to this question depends on the commitment of the nodes to their first computed output value: Two classes of problems solvable in Anonymous Networks are defined, where in the first class nodes are allowed to revoke their outputs and in the second class they are not. These two classes are then related to the class of all centrally solvable Network problems, observing that the three classes form a strict linear hierarchy, and for several classic and/or characteristic problems in distributed computing, we determine the exact class to which they belong.Does this hierarchy exhibit complete problems? We answer this question in the affirmative by introducing the concept of a distributed oracle, thus establishing a more fine grained classification for distributed computability which we apply to the classic/characteristic problems. Among our findings is the observation that the three classes are characterized by the three pillars of distributed computing, namely, local symmetry breaking, coordination, and leader election.

### Olivier Festor – One of the best experts on this subject based on the ideXlab platform.

• ##### A Bird’s Eye View on the I2P Anonymous File-sharing Environment
, 2012
Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier Festor

Abstract:

Anonymous communications have been gaining more and more interest from Internet users as privacy and anonymity problems have emerged. Among Anonymous enabled services, Anonymous file-sharing is one of the most active one and is increasingly growing. Large scale monitoring on these systems allows us to grasp how they behave, which type of data is shared among users, the overall behaviour in the system. But does large scale monitoring jeopardize the system anonymity? In this work we present the first large scale monitoring architecture and experiments on the I2P Network, a low-latency message-oriented Anonymous Network. We characterize the file-sharing environment within I2P, and evaluate if this monitoring affects the anonymity provided by the Network. We show that most activities within the Network are file-sharing oriented, along with Anonymous web-hosting. We assess the wide geographical location of nodes and Network popularity. We also demonstrate that group-based profiling is feasible on this particular Network.

• ##### NSS – A bird’s eye view on the I2P Anonymous file-sharing environment
Network and System Security, 2012
Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier Festor

Abstract:

Anonymous communications have been gaining more and more interest from Internet users as privacy and anonymity problems have emerged. Among Anonymous enabled services, Anonymous filesharing is one of the most active one and is increasingly growing. Large scale monitoring on these systems allows us to grasp how they behave, which type of data is shared among users, the overall behaviour in the system. But does large scale monitoring jeopardize the system anonymity?

In this work we present the first large scale monitoring architecture and experiments on the I2P Network, a low-latency message-oriented Anonymous Network. We characterize the file-sharing environment within I2P, and evaluate if this monitoring affects the anonymity provided by the Network.

We show that most activities within the Network are file-sharing oriented, along with Anonymous web-hosting. We assess the wide geographical location of nodes and Network popularity. We also demonstrate that group-based profiling is feasible on this particular Network.

• ##### TMA – I2P’s usage characterization
Traffic Monitoring and Analysis, 2012
Co-Authors: Juan Pablo Timpanaro, Isabelle Chrisment, Olivier Festor

Abstract:

We present the first monitoring study aiming to characterize the usage of the I2P Network, a low-latency Anonymous Network based on garlic routing. We design a distributed monitoring architecture for the I2P Network and show through three one-week measurement experiments the ability of the system to identify a significant number of all running applications, among web servers and file-sharing clients.

### Seiichiro Tani – One of the best experts on this subject based on the ideXlab platform.

• ##### Compression of View on AnonymousNetworks—Folded View—
IEEE Transactions on Parallel and Distributed Systems, 2012
Co-Authors: Seiichiro Tani

Abstract:

View is a labeled directed graph containing all information about the Network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an Anonymous Network (i.e., a Network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an Anonymous n-party Network of any topology in at most 2n rounds with O(n6\log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n6\log n). This is the first view-construction algorithm that runs in O(n) rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the Network in O(n6\log n) time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in O(n) rounds with polynomial bit and time complexity on an Anonymous n-party Network of any topology.