text:
Distributed Agreement in Dynamic Peer-to-Peer Networks1footnote 11footnote 1A preliminary version of this paper appeared in the Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA), 2012, 551-569.

# Distributed Agreement in Dynamic Peer-to-Peer Networks111A preliminary version of this paper appeared in the Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA), 2012, 551-569.

John Augustine Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India. E-mail: augustine@cse.iitm.ac.in. Work done while at the Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371.    Gopal Pandurangan Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 and Department of Computer Science, Brown University, Box 1910, Providence, RI 02912, USA. E-mail: gopalpandurangan@gmail.com. Work supported in part by the following grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, US NSF grant CCF-1023166, and a grant from the US-Israel Binational Science Foundation (BSF).    Peter Robinson Department of Computer Science, National University of Singapore. E-mail: robinson@comp.nus.edu.sg    Eli Upfal Department of Computer Science, Brown University, Box 1910, Providence, RI 02912, USA. E-mail: eli@cs.brown.edu
###### Abstract

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results:

1. An -round ( is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i.e., , for some small constant ), assuming 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). Our algorithm requires only polylogarithmic in bits to be processed and sent (per round) by each node.

2. An -round randomized algorithm that achieves almost-everywhere agreement with high probability under up to churn per round (for some small ), where is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). This algorithm requires up to polynomial in bits (and up to bits) to be processed and sent (per round) by each node.

Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

## 1 Introduction

Peer-to-peer (P2P) computing is emerging as one of the key networking technologies in recent years with many application systems, e.g., Skype, BitTorrent, Cloudmark etc. However, many of these systems are not truly P2P, as they are not fully decentralized — they typically use hybrid P2P along with centralized intervention. For example, Cloudmark [25] is a large spam detection system used by millions of people that operates by maintaining a hybrid P2P network; it uses a central authority to regulate and charge users for participation in the network. A key reason for the lack of fully-distributed P2P systems is the difficulty in designing highly robust algorithms for large-scale dynamic P2P networks. Indeed, P2P networks are highly dynamic networks characterized by high degree of node churn — i.e., nodes continuously join and leave the network. Connections (edges) may be added or deleted at any time and thus the topology changes very dynamically. In fact, measurement studies of real-world P2P networks [33, 40, 64, 65] show that the churn rate is quite high: nearly 50% of peers in real-world networks can be replaced within an hour. (However, despite a large churn rate, these studies also show that the total number of peers in the network is relatively stable.) We note that peer-to-peer algorithms have been proposed for a wide variety of computationally challenging tasks such as collaborative filtering [19], spam detection [25], data mining [28], worm detection and suppression [55, 67], and privacy protection of archived data [38]. However, all algorithms proposed for these problems have no theoretical guarantees of being able to work in a network with a dynamically changing topology and a linear churn rate per round. This is a major bottleneck in implementation and wide-spread use of these algorithms.

In this paper, we take a step towards designing robust algorithms for large-scale dynamic peer-to-peer networks. In particular, we study the fundamental distributed agreement problem in P2P networks (the formal problem statement and model is given in Section 2). An efficient solution to the agreement problem can be used as a building block for robust and efficient solutions to other problems as mentioned above. However, the distributed agreement problem in P2P networks is challenging since the goal is to guarantee almost-everywhere agreement, i.e., almost all nodes 222In sparse, bounded-degree networks, an adversary can always isolate some number of non-faulty nodes, hence almost-everywhere is the best one can hope for in such networks [32]. should reach consensus, even under high churn rate. The churn rate can be as much as linear per time step (round), i.e., up to a constant fraction of the stable network size can be replaced per time step. Indeed, until recently, almost all the work known in the literature (see e.g., [32, 44, 45, 46, 66]) have addressed the almost-everywhere agreement problem only in static (bounded-degree) networks and these approaches do not work for dynamic networks with changing topology. Such approaches fail in dynamic networks where both nodes and edges can change by a large amount in every round. For example, the work of Upfal [66] showed how one can achieve almost-everywhere agreement under up to a linear number — up to , for a sufficiently small — of Byzantine faults in a bounded-degree expander network ( is the network size). The algorithm required rounds and polynomial (in ) number of messages; however, the local computation required by each processor is exponential. Furthermore, the algorithm requires knowledge of the global topology, since at the start, nodes need to have this information “hardcoded”. The work of King et al. [47] is important in the context of P2P networks, as it was the first to study scalable (polylogarithmic communication and number of rounds) algorithms for distributed agreement (and leader election) that are tolerant to Byzantine faults. However, as pointed out by the authors, their algorithm works only for static networks; similar to Upfal’s algorithm, the nodes require hardcoded information on the network topology to begin with and thus the algorithm does not work when the topology changes. In fact, this work ([47]) raises the open question of whether one can design agreement protocols that can work in highly dynamic networks with a large churn rate.

### 1.1 Our Main Results

Our first contribution is a rigorous theoretical framework for the design and analysis of algorithms for highly dynamic distributed systems with churn. We briefly describe the key ingredients of our model here. (Our model is described in detail in Section 2.) Essentially, we model a P2P network as a bounded-degree expander graph whose topology — both nodes and edges — can change arbitrarily from round to round and is controlled by an adversary. However, we assume that the total number of nodes in the network is stable. The number of node changes per round is called the churn rate or churn limit. We consider a churn rate of up to some , where is the stable network size. Note that our model is quite general in the sense that we only assume that the topology is an expander at every step; no other special properties are assumed. Indeed, expanders have been used extensively to model dynamic P2P networks333Expander graphs have been used extensively as candidates to solve the agreement and related problems in bounded degree graphs even in static settings (e.g., see [32, 44, 45, 46, 66]). Here we show that similar expansion properties are beneficial in the more challenging setting of dynamic networks. in which the expander property is preserved under insertions and deletions of nodes (e.g., [52, 59]). Since we do not make assumptions on how the topology is preserved, our model is applicable to all such expander-based networks. (We note that various prior work on dynamic network models make similar assumptions on preservation of topological properties — such as connectivity, expansion etc. — at every step under dynamic edge insertions/deletions — cf. Section 1.3. The issue of how such properties are preserved are abstracted away from the model, which allows one to focus on the dynamism. Indeed, this abstraction has been a feature of most dynamic models e.g., see the survey of [20].)

We study stable, almost-everywhere, agreement in our model. By “almost-everywhere”, we mean that almost all nodes, except possibly nodes (where is the order of the churn and is a suitably small constant — cf. Section 2) should reach agreement on a common value. (This agreed value must be the input value of some node.) By “stable” we mean that the agreed value is preserved subsequently after the agreement is reached.

Our main contribution is the design and analysis of randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability (i.e., with probability , for an arbitrary fixed constant ) even under high adversarial churn in a polylogarithmic number of rounds. Our algorithms also guarantee stability once agreement has been reached. In particular, we present the following results (the precise theorem statements are given in the respective sections below):

1. (cf. Section 4) An -round ( is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i.e., , for some small constant ), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge of what nodes join and leave and at what time, but is oblivious to the random choices made by the algorithm). Our algorithm requires only polylogarithmic in bits to be processed and sent (per round) by each node.

2. (cf. Section 5) An -round randomized algorithm that achieves almost-everywhere agreement with high probability under up to churn per round, for some small , that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Here refers to the size of the domain of input values. This algorithm requires up to polynomial in bits (and up to bits) to be processed and sent (per round) by each node.

3. (cf. Section 6) We also show that no deterministic algorithm can guarantee almost-everywhere agreement (regardless of the number of rounds), even under constant churn rate.

To the best of our knowledge, our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings. Our algorithms are localized (do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in P2P networks.

### 1.2 Technical Contributions

The main technical challenge that we have to overcome is designing and analyzing distributed algorithms in networks where both nodes and edges can change by a large amount. Indeed, when the churn rate is linear, i.e., say per round, in constant () number of rounds the entire network can be renewed!

We derive techniques for information spreading (cf. Section 3) for doing non-trivial distributed computation in such networks. The first technique that we use is flooding. We show that in an expander-based P2P network even under linear churn rate, it is possible to spread information by flooding if sufficiently many (a -fraction of the order of the churn) nodes initiate the information spreading (cf. Lemma 3.1). In other words, even an adaptive adversary cannot “suppress” more than a small fraction of the values. The precise statements and proofs are in Section 3.

To analyze these flooding techniques we introduce the dynamic distance, which describes the effective distance between two nodes with respect to the causal influence. We define the notions of influence sets and dynamic distance (or flooding time) in dynamic networks with node churn. (Similar notions have been defined for dynamic graphs with a fixed set of nodes, e.g., [48, 17]). In (connected) networks where the nodes are fixed, the effective diameter (e.g., [48]) is always finite. In the highly dynamic setting considered here, however, the effective distance between two nodes might be infinite, thus we need a more refined definition for influence set and dynamic distance.

The second technique that we use is “support estimation” (cf. Section 3.4). Support estimation is a randomized technique that allows us to estimate the aggregate count (or sum) of values of all or a subset of nodes in the network. Support estimation is done in conjunction with flooding and uses properties of the exponential distribution (similar to [26, 56]). Support estimation allows us to estimate the aggregate value quite precisely with high probability even under linear churn. But this works only for an oblivious adversary; to get similar results for the adaptive case, we need to increase the amount of bits that can be processed and sent by a node in every round.

Apart from support estimation, we also use our flooding techniques in the agreement algorithm for the oblivious case (cf. Algorithm 2) to sway the decision one way or the other. For the adaptive case (cf. Algorithm 3), we use the variance property of a certain probability distribution to achieve the same effect with constant probability.

### 1.3 Other Related Work

#### 1.3.1 Distributed Agreement

The distributed agreement (or consensus) problem is important in a wide range of applications, such as database management, fault-tolerant analysis of aggregate data, and coordinated control of multiple agents or peers. There is a long line of research on various versions of the problem with many important results (see e.g., [7, 53] and the references therein). The relaxation of achieving agreement “almost everywhere” was introduced by [32] in the context of fault-tolerance in networks of bounded degree where all but nodes achieve agreement despite faults. This result was improved by [66], which showed how to guarantee almost everywhere agreement in the presence of a linear fraction of faulty nodes. Both the work of [32, 66] crucially use expander graphs to show their results. We also refer to the related results of Berman and Garay on the butterfly network [18].

#### 1.3.2 Byzantine Agreement

We note that Byzantine adversaries are quite different from the adversaries considered in this paper. A Byzantine adversary can have nodes behaving arbitrarily, but no new nodes are added (i.e., no churn), whereas in our case (an external) adversary controls the churn and topology of the network but not the behavior of the nodes. Despite this difference it is worthwhile to mention that there has been significant work in designing peer-to-peer networks that are provably robust to a large number of Byzantine faults [35, 42, 57, 62]. These focus only on robustly enabling storage and retrieval of data items. The problem of achieving almost-everywhere agreement among nodes in P2P networks (modeled as an expander graph) is considered by King et al. in [47] in the context of the leader election problem; essentially, [47] is a sparse (expander) network implementation of the full information protocol of [46]. More specifically, [47] assumes that the adversary corrupts a constant fraction of the processes that are under its control throughout the run of the algorithm. The protocol of [47] guarantees that with constant probability an uncorrupted leader will be elected and that a fraction of the uncorrupted processes know this leader. Again, we note that the failure assumption of [47] is quite different from the one we use: Even though we do not assume corrupted nodes, the adversary is free to subject different nodes to churn in every round. Also note that the algorithm of [47] does not work for dynamic networks.

Other works on handling Byzantine nodes in the context of P2P networks include [62, 12, 34, 36, 14, 21, 68].

In [8], we have developed an almost-everywhere agreement algorithm that tolerates up to churn and churn per round, in a dynamic network model.

#### 1.3.3 Dynamic Networks

Dynamic networks have been studied extensively over the past three decades. Some of the early studies focused on dynamics that arise out of faults, i.e., when edges or nodes fail. A number of fault models, varying according to extent and nature (e.g., probabilistic vs. worst-case) and the resulting dynamic networks have been analyzed (e.g., see [7, 53]). There have been several studies on models that constrain the rate at which changes occur, or assume that the network eventually stabilizes (e.g., see [1, 31, 37]). Some of the early work on general dynamic networks include [2, 11] which introduce general building blocks for communication protocols on dynamic networks. Another notable work is the local balancing approach of [10] for solving routing and multicommodity flow problems on dynamic networks. Most of these papers develop algorithms that will work under the assumption that the network will eventually stabilize and stop changing.

Modeling general dynamic networks has gained renewed attention with the recent advent of heterogeneous networks composed out of ad hoc, and mobile devices. To address highly unpredictable network dynamics, stronger adversarial models have been studied by [9, 27, 58, 50] and others; see the recent survey of [20] and the references therein. The works of [50, 9, 27] study a model in which the communication graph can change completely from one round to another, with the only constraint being that the network is connected at each round ([50] and [27] also consider a stronger model where the constraint is that the network should be an expander or should have some specific expansion in each round). The model has also been applied to agreement problems in dynamic networks; various versions of coordinated consensus (where all nodes must agree) have been considered in [50]. The recent work of [24], studies the flooding time of Markovian evolving dynamic graphs, a special class of evolving graphs.

We note that the model of [49] allows only edge changes from round to round while the nodes remain fixed. In this work, we introduce a dynamic network model where both nodes and edges can change by a large amount (up to a linear fraction of the network size). Therefore, the framework we introduce in Section 2 is more general than the model of [49], as it is additionally applicable to dynamic settings with node churn. The same is true for the notions of dynamic distance and influence set that we introduce in Section 3.1, since in our model the dynamic distance is not necessarily finite. In fact, according to [48], coping with churn is one of the important open problems in the context of dynamic networks. Our paper takes a step in this direction.

An important aspect of our algorithms is that they will work and terminate correctly even when the network keeps continually changing. We note that there has been considerable prior work in dynamic P2P networks (see [59] and the references therein) but these do not assume that the network keeps continually changing over time.

Due to the mobility of nodes, mobile ad-hoc networks can also be considered as dynamic networks. The focus of [58] are the minimal requirements that are necessary to correctly perform flooding and routing in highly dynamic networks where edges can change but the set of nodes remains the same. In the context of agreement problems, electing a leader among mobile nodes that may join or leave the network at any time is the focus of [23]. To make leader election solvable in this model, Chung et al. introduce the notion of -connectedness, which ensures information propagation among all nodes that remain long enough in the network. Note that, in contrast to our model, this assumption prohibits the adversary from permanently isolating parts of the network. The recent work of [41] presents information spreading algorithms on dynamic networks based on network coding [3].

#### 1.3.4 Fault-Tolerance

In most work on fault-tolerant agreement problems the adversary a priori commits to a fixed set of faulty nodes. In contrast, [30] considers an adversary that can corrupt the state of some (possibly changing) set of nodes in every round. The median rule of [30] provides an elegant way to ensure that most nodes stabilize on a common output value within rounds, assuming a complete communication graph. The median rule, however, only guarantees that this agreement lasts for some polynomial number of rounds, whereas we are able to retain agreement ad infinitum.

Expander graphs and spectral properties have already been applied extensively to improve the network design and fault-tolerance in distributed computing (cf. [66, 32, 16]). Law and Siu [52] provide a distributed algorithm for maintaining an expander in the presence of churn with high probability by using Hamiltonian cycles. In [61] it is shown how to maintain the expansion property of a network in the self-healing model where the adversary can delete/insert a new node in every step. In the same model, [60] present a protocol that maintains constant node degrees and constant expansion (both with probability ) against an adaptive adversary, while requiring only logarithmic (in the network size) messages, time, and topology changes per deletion/insertion. In [6], it is shown that a SKIP graph (cf. [5]) contains a constant degree expander as a subgraph with high probability. Moreover, it requires only constant overhead for a node to identify its incident edges that are part of this expander. Later on, [43] presented a self-stabilizing algorithm that converges from any weakly connected graph to a SKIP graph in time polylogarithmic in the network size, which yields a protocol that constructs an expander with high probability. In [13] the authors introduce the hyperring, which is a search data structure supporting insertions and deletions, while being able to handle concurrent requests with low congestion and dilation, while guaranteeing expansion and node degree. The -Flipper algorithm of [54] transforms any undirected graph into an expander (with high probability) by iteratively performing flips on the end-vertices of paths of length . Based on this protocol, the authors describe how to design a protocol that supports deletions and insertions of nodes. Note that, however, the expansion in [54] is only guaranteed with high probability however, assuming that the node degree is .

Information spreading in distributed networks is the focus of [22] where it is shown that this problem requires rounds in graphs with a certain conductance in the push/pull model where a node can communicate with a randomly chosen neighbor in every round.

Aspnes et al. [4] consider information spreading via expander graphs against an adversary, which is related to the flooding techniques we derive in Section 3. More specifically, in [4] there are two opposing parties “the alert” and “the worm” (controlled by the adversary) that both try to gain control of the network. In every round each alerted node can alert a constant number of its neighbors, whereas each of the worm nodes can infect a constant number of non-alerted nodes in the network. In [4], Aspnes et al. show that there is a simple strategy to prevent all but a small fraction of nodes from becoming infected and, in case that the network has poor expansion, the worm will infect almost all nodes.

The work of [16] shows that, given a network that is initially an expander and assuming some linear fraction of faults, the remaining network will still contain a large component with good expansion. These results are not directly applicable to dynamic networks with large amount of churn like the ones we are considering, as the topology might be changing and linear churn per round essentially corresponds to total churn after rounds—the minimum amount of time necessary to solve any non-trivial task in our model.

In the context of maintaining properties in P2P networks, Kuhn et al. consider in [51] that up to nodes can crash or join per constant number of time steps. Despite this amount of churn, it is shown in [51] how to maintain a low peer degree and bounded network diameter in P2P systems by using the hypercube and pancake topologies. Scheideler and Schmid show in [63] how to maintain a distributed heap that allows join and leave operations and, in addition, is resistent to Sybil attacks. A robust distributed implementation of a distributed hash table (DHT) in a P2P network is given by [15], which can withstand two important kind of attacks: adaptive join-leave attacks and adaptive insert/lookup attacks by up to adverserial peers. Note that, however, that collisions are likely to occur once the number of attacks becomes .

## 2 Model and Problem Statement

We make the following assumptions about the kind of changes that our dynamic network can encounter:

Stable Network Size:

For all , , where is a suitably large positive integer. This assumption simplifies our analysis. Our algorithms will work correctly as long as the number of nodes is reasonably stable (say, between and for some suitably small constant ). Also, we assume that (or a constant factor estimate of ) is common knowledge among the nodes in the network444This assumption is important; estimating accurately in our model is an interesting problem in itself..

Churn:

For each ,

 |Vr∖Vr−1|=|Vr−1∖Vr|⩽L=εc(n),

where is the churn limit, which is some fixed fraction of the order of the churn ; the equality in the above equation ensures that the network size remains stable. Our work is aimed at high levels of churn up to a churn limit that is linear in , i.e., .

Bounded Degree Expanders:

The sequence of graphs is an expander family with a vertex expansion of at least , which is a fixed positive constant.555Note that the value of determines , i.e. the fraction of churn that we can tolerate. In particular, to tolerate linear amount of churn, we require constant expansion. In principle, our results can potentially be extended to graphs with weaker expansion guarantees as well; however the amount of churn that can be tolerated will be reduced. In other words, the adversary must ensure that for every and every such that , the number of nodes in with a neighbor in is at least . Note that we do not explicitly consider the costs (communication and computation) of maintaining an expander under churn. Instead, we assume that the duration of each time step in our model are normalized to be large enough to encompass an expander maintenance protocol such as [52, 60].

A run of a distributed algorithm consists of an infinite number of rounds. We assume that the following events occur (in order) in every round :

1. A set of at most nodes are churned in and another set of nodes are churned out. The edges of may be changed as well, but has to have a vertex expansion of at least . These changes are under the control of the adversary.

2. The nodes broadcast messages to their (current) neighbors.

4. Nodes perform computation that can change their state and determine which messages to send in round .

### Bounds on Parameters

Recall that the churn limit , where is a constant and is the churn order. When , is the fraction of the nodes churned out/in and therefore we require to be less than 1 and must adhere to Equation (1). Moreover, we require the bound regarding the right hand side of (1). However, when , can exceed 1. In the remainder of this paper, we consider to be a small constant independent of , such that

 (1) ε(1+α)α<β.

It will become apparent in Section 3 that (1) presents a sufficient condition for preventing the adversary from containing the information propagated by a set of nodes.

and that the churn expansion ratio presents a sufficient condition for information propagation in our model (cf. Lemma 3.1). Finally, we assume that is suitably large (cf. Equations 7 and 8).

### 2.1 Stable Agreement

We now define the Almost Everywhere Stable Agreement problem (or just the Stable Agreement problem for brevity). Each node has an associated input value from some value domain of size ; subsequent new nodes come with value . Let be the set of all input values associated with nodes in at the start of round 1. Every node is equipped with a special decision variable (initialized to ) that can be written at most once. We say that a node decides on when assigns to its . Note that this decision is irrevocable, i.e., every node can decide at most once in a run of an algorithm. As long as , we say that is undecided. Stable Agreement requires that a large fraction of the nodes come to a stable agreement on one of the values in . More precisely, an algorithm solves Stable Agreement in rounds, if it exhibits the following characteristics in every run, for any fixed adhering to (1).

Validity:

If, in some round , node decides on a value , then .

Almost Everywhere Agreement:

We say that the network has reached strong almost everywhere agreement by round , if at least nodes in have decided on the same value and every other node remains undecided, i.e., its decision value is . In particular, no node ever decides on a value in the same run, for .

Stability:

Let be the earliest round where nodes have reached almost everywhere agreement on value . We say that an algorithm reaches stability by round if, at every round , at least nodes in have decided on .

We also consider a weaker variant of the above problem that we call Almost Everywhere Binary Consensus (or simply, Binary Consensus) where the input values in are restricted to .

We consider two types of adversaries for our randomized algorithms. An oblivious adversary must commit in advance to the entire sequence of graphs . In other words, an oblivious adversary must commit independently of the random choices made by the algorithm. We also consider the more powerful adaptive adversary that can observe the entire state of the network in every round (including all the random choices made until round ), and then chooses the nodes to be churned out/in and how to change the topology of .

For the sake of readability, we treat as an integer and omit the necessary ceiling or floor operations if their application is clear from the context.

## 3 Techniques for Information Spreading

In this section, we first derive and analyze techniques to spread information in the network despite churn. First, we show that the adversary is unable to prevent a sufficiently large set of nodes (of size at least ) to propagate their information to almost all other nodes (cf. Lemma 3.1). Building on this result, we analyze the capability of individual nodes to spread their information. We show in Lemma 3.2 and Corollary 3.3 that at most nodes can be hindered by the adversary. Finally, we show in Lemmas 3.5 and 3.6 that there is a large set of nodes such that all nodes in are able to propagate their information to a large common set of nodes.

In Sections 3.4 and 3.5, we describe how to use the previously derived techniques on information spreading to estimate the “support” (i.e. number) of nodes that belong to a specific category (either red or blue). These protocols will form a fundamental building block for our Stable Agreement algorithms.

Due to the high amount of churn and the dynamically changing network, we use message flooding to disseminate and gather information. We now precisely define flooding. Any node can initiate a message for flooding. Messages that need to be flooded have an indicator bit bFlood set to 1. Each of these messages also contains a terminating condition. The initiating node sends copies of the message to itself and its neighbors. When a node receives a message with bFlood set to 1, it continues to send copies of that message to itself and its neighbors in subsequent rounds until the terminating condition is satisfied.

### 3.1 Dynamic Distance and Influence Set

Informally, the dynamic distance from node to node is the number of rounds required for a message at to reach . We now formally define the notion of dynamic distance of a node from starting at round , denoted by . When the subscript is omitted, we assume that .

Suppose node joins the network at round , and, from round onward, initiates a message for flooding whose terminating condition is: . If is churned out before , then is undefined. Suppose the first of those flooded messages reaches in round . Then, . Note that this definition allows to be infinite under two scenarios. Firstly, node may be churned out before any copy of reaches . Secondly, at each round, can be shielded by churn nodes that absorb the flooded messages and are then removed from the network before they can propagate these messages any further. The influence set of a node after rounds starting at round is given by:

 \mathscInflr(u,R)={v∈Vr+R:\mathscDDr(u→v)⩽R}.

Note that we require . Intuitively, we want the influence set of (in this dynamic setting) to capture the nodes currently in the network that were influenced by . Note however that the influence set of a node is meaningful even after is churned out. Analoguously, we define

 \mathscInflr(U,R)=∪u∈U\mathscInflr(u,R),

for any set of nodes .

If we consider only a single node , an (adaptive) adversary can easily prevent the influence set of this node from ever reaching any significant size by simply shielding with churn nodes that are replaced in every round.666An oblivious adversary can achieve the same effect with constant probability for linear churn.

### 3.2 Properties of Influence Sets

We now focus our efforts on characterizing influence sets. This will help us in understanding how we can use flooding to spread information in the network. For the most part of this section we assume that the network is controlled by an adaptive adversary (cf. Section 2.1). The following lemma shows that the number of nodes that are sufficient to influence almost all the nodes in the network is given by the churn-expansion ratio (cf. Equation (1)):

###### Lemma 3.1.

Suppose that the adversary is adaptive. Consider any set (for any ) such that . Then, after

 T=2⎡⎢ ⎢ ⎢⎢logn−logc(n)−log(β−ε(1+α)α)−1log(1+α)⎤⎥ ⎥ ⎥⎥

number of rounds, it holds that

 (2) ∣∣\mathscInflr(U,T)∣∣>n−βc(n).

When considering linear churn, i.e., , the bound becomes a constant independent of . On the other hand, when considering a churn order of , we get .

###### Proof.

Our proof assumes that for simplicity as the arguments extend quite easily to arbitrary values of . We proceed in two parts: First we show that the nodes in influence at least nodes in some rounds. More precisely, we show that . We use vertex expansion in a straightforward manner to establish this part. Then, in the second part we show that nodes in go on to influence more than nodes. We cannot use the vertex expansion in a straightforward manner in the second part because the cardinality of the set that is expanding in influence is larger than . Rather, we use a slightly more subtle argument in which we use vertex expansion going backward in time. The second part requires another rounds. Therefore, the two parts together complete the proof when we set .

To begin the first part, consider at the start of round 1 with . In round , up to nodes in can be churned out. Subsequently, the remaining nodes in influence some nodes outside as is an expander with vertex expansion at least . More precisely, we can say that

 (3) |\mathscInfl(U,1)|⩾(βc(n)−εc(n))(1+α).

At the start of round , the graph changes dynamically to . In particular, up to nodes might be churned out and they may all be in in the worst case. However, the influenced set will again expand. Therefore, cannot be less than . Of course, there will be more churn at the start of round 3 followed by expansion leading to: \linenomath

 |\mathscInfl(U,3)| ⩾(βc(n)(1+α)2 − εc(n)(1+α)2 − εc(n)(1+α) − εc(n))(1+α) =βc(n)(1+α)3 − εc(n)3∑k=1(1+α)k.
\endlinenomath

This cycle of churn followed by expansion continues and we get the following bound at the end of some round : \linenomath

 |\mathscInfl(U,i)| ⩾βc(n)(1+α)i−εc(n)i∑k=1(1+α)k =βc(n)(1+α)i +εc(n)1−(1+α)i+1α−εc(n)
\endlinenomath

Therefore, after

 (4) T1=⎡⎢ ⎢ ⎢⎢logn−logc(n)−log(β−ε(1+α)α)−1log(1+α)⎤⎥ ⎥ ⎥⎥

rounds, we get

 (5) |\mathscInfl(U,T1)|⩾n/2.

Now we move on to the second part of the proof. Let . If , we are done. Therefore, for the sake of a contradiction, assume that . Let , i.e., is the set of nodes in that were not influenced by at (or before) round . Moreover, because we have assumed that . We will start at round and work our way backward. For , let , be the set of all vertices in that, starting from round , influenced some vertex in at or before round . More precisely,

 Sq={s∈Vq:\mathscInflq(s,T−q)∩S≠∅}.

Suppose that . Then

 ST1∩\mathscInfl(U,T1)≠∅,

since by (5). Consider a node . Note that was influenced by and went on to influence some node in before (or at) round . However, by definition, no node in can be influenced by any node in at or before round . We have thus reached a contradiction.

We are left with showing that . We start with and work our way backwards. We know that . We want to compute the cardinality of . We first focus on an intermediate set , which we define as

 S′=S∪{s′:∃(s,s′)∈ET}.

Since is an expander, . Furthermore, it is also clear that each node in could influence some node in . Notice that is the set of nodes in that were churned in only at the start of round . Therefore, \linenomath

 |ST−1| ⩾|S′|−εc(n) ⩾|S|(1+α)−εc(n) >(βc(n)−εc(n))(1+α)−εc(n) =βc(n)(1+α)−εc(n)(1+α)−εc(n).
\endlinenomath

Continuing to work our way backwards in time, we get \linenomath

 |ST−2|>βc(n)(1+α)2 −εc(n)(1+α)2 −εc(n)(1+α)−εc(n),
\endlinenomath

Or more generally, \linenomath

 |ST−i| >βc(n)(1+α)i−εc(n)∑0⩽j⩽i(1+α)j =βc(n)(1+α)i+εc(n)1−(1+α)i+1α =βc(n)(1+α)i−εc(n)(1+α)i+1α+εc(n)α.
\endlinenomath

We now want the value of for which

 |ST−i|>n/2+εc(n)α>n/2.

In other words, we want a value of such that

 βc(n)(1+α)i−εc(n)(1+α)i+1α+εc(n)α>n/2+εc(n)α,

which is obtained when . Therefore, it is easy to see that if we set , we get , thereby completing the proof. ∎∎

At first glance, it might appear to be counterintuitive that the order of the bound decreases with increasing churn. When the adversary has the benefit of churn that is linear in , our bound on is a constant, but when the adversary is limited to a churn order of , we get . This, however, turns out to be fairly natural when we note that the size of the set of nodes that we start out with is in proportion to the churn limit.

We say that a node is suppressed for rounds or shielded by churn if ; otherwise we say it is unsuppressed. The following lemma shows that given a set with cardinality at least some node in that set will be unsuppressed.

###### Lemma 3.2.

Consider the adaptive adversary. Let be any subset of , , such that . Let be the bound derived in Lemma 3.1. There is at least one such that for some , is unsuppressed, i.e.,

 |\mathscInflr(u∗,R)|>n−βc(n).

In particular, when the order of the churn is , becomes a constant, and we have .

Before we proceed with our key arguments of the proof, we state a property of bipartite graphs that we will use subsequently.

###### Property 1.

Let be a bipartite graph in which and every vertex has at least one neighbor in . There is a subset of cardinality at most such that

 |{b:∃a∗∈A∗such that (a∗,b)∈E}|⩾⌈|B|/2⌉.
###### Proof.

(of Property 1) Consider each node in to be a unique color. Color each node in using the color of a neighbor in chosen arbitrarily. Now partition into maximal subsets of nodes with like colors. Consider the parts of the partition sorted in decreasing order of their cardinalities. We now greedily choose the first colors in the sorted order of parts of . We call the chosen colors . Observe that colors in cover at least as many nodes in as those not in . Suppose the colors in cover fewer than nodes in . Then the remaining colors will cover , but that is a contradiction. Therefore, colors in cover at least nodes in . The nodes in that have the colors in are the nodes that comprise , thereby completing our proof. ∎∎

###### Proof.

(of Lemma 3.2) Again, our proof assumes because it generalizes to arbitrary values of quite easily. From Lemma 3.1, we know that the influence of all nodes in taken together will reach nodes in rounds. This does not suffice because we are interested in showing that there is at least one node in that (individually) influences nodes in for some .

From Lemma 3.1, we know that (collectively) will influence at least nodes in T rounds, i.e.,

 |\mathscInfl(U,T)|>n−βc(n).

From Property 1, we know that there is a set of cardinality at most such that

 |\mathscInfl(U1,T)|>n−βc(n)2.

Recalling that , we know that . We can again use Lemma 3.1 to say that influences more than nodes in additional rounds and, by transitivity, influences more than nodes after rounds. We therefore have . Again, we can choose a set (using Property 1) that consists of nodes in such that . Subsequently applying Lemma 3.1 extends the influence set of to more than after rounds.

In every iteration of the above argument, the size of the set decreases by a constant fraction until we are left with a single node such that . ∎∎

Can (or more nodes) be suppressed for any significant number of (say, ) rounds? This is in immediate contradiction to Lemma 3.2 because any such suppressed set of nodes must contain an unsuppressed node. This leads us to the following corollary.

###### Corollary 3.3.

The number of nodes that can be suppressed for rounds is less than , even if the network is controlled by an adaptive adversary.

###### Corollary 3.4.

Consider an oblivious adversary that must commit to the entire sequence of graphs in advance. If we choose a node uniformly at random from , with probability at least , then will be unsuppressed, i.e.,

 ∣∣\mathscInfl(u,Ω(Tlogn))∣∣>n−βc(n).
###### Proof.

Let be the set of nodes suppressed for rounds. Under an oblivious adversary, the node chosen unformly at random from will not be in with probability , and hence, will not be suppressed with that same probability. ∎∎

The following two lemmas show that there exists a set of unsuppressed nodes, all of which can influence a large common set of nodes, given enough time.

###### Lemma 3.5.

Consider a dynamic network under linear churn that is controlled by an adaptive adversary. In some rounds, there is a set of unsuppressed nodes of cardinality more than such that

 ∣∣ ∣∣⋂v∈V∗\mathscInfl(v,r)∣∣ ∣∣>(1−β)n.
###### Proof.

Let be any set of unsuppressed nodes, i.e., in some rounds for some constant , the influence set of each has cardinality more than . Note that, however, we cannot guarantee that, for any two vertices and in ,

 |\mathscInfl(v1,c0logn)∩\mathscInfl(v1,c0logn)|>(1−β)n.

Assume for simplicity that is a power of 2. Consider any pair of vertices , both members of . Recalling that , we can say that

 ∣∣\mathscInfl(v1,c0logn)∩\mathscInfl(v2,c0logn)∣∣⩾βn.

Therefore, considering that the intersected set of nodes has cardinality at least , we can apply Lemma 3.1 leading to . We can partition into a set of pairs such that for each pair, the intersection of influence sets has cardinality more than after rounds. Similarly, we can construct a set of quadruples by disjointly pairing the pairs in . Using a similar argument, we can say that for any ,

 ∣∣ ∣∣⋂v∈Q\mathscInfl(v,c0logn+2T)∣∣ ∣∣>(1−β)n.

Progressing analogously, the set will equal and we can conclude that

 ∣∣ ∣∣⋂v∈Slog|V∗|\mathscInfl(v,c0logn+Tlog|V∗|)∣∣ ∣∣>(1−β)n.

Since , it holds that , thus completing the proof. ∎∎

###### Lemma 3.6.

Suppose that up to nodes can be subjected to churn in any round by an adaptive adversary. In some rounds, there is a set of unsuppressed nodes of cardinality at least such that

 ∣∣ ∣∣⋂v∈V∗\mathscInfl(v,r)∣∣ ∣∣>n−β√n.
###### Proof.

Since we assume that , the bound of Lemma 3.1 is in . Therefore, by instantiating Corollary 3.3, we know that each of the unsuppressed nodes in (which is of cardinality at least ) will influence more than nodes in time. We can use the same argument as in Lemma 3.5 to show that in rounds, all the unsuppressed nodes have a common influence set of size at least . That common influence set will grow to at least nodes within another rounds. Thus a total of rounds is sufficient to fulfill the requirements. ∎∎

### 3.3 Maintaining Information in the Network

In a dynamic network with churn limit , the entire set of nodes in the network can be churned out and new nodes churned in within rounds. How do the new nodes even know what algorithm is running? How do they know how far the algorithm has progressed? To address these basic questions, the network needs to maintain some global information that is not lost as the nodes in the network are churned out. There are two basic pieces of information that need to be maintained so that a new node can join in and participate in the execution of the distributed algorithm:

1. the algorithm that is currently executing, and

2. the number of rounds that have elapsed in the execution of the algorithm. In other words, a global clock has to be maintained.

We assume that the nodes in are all synchronized in their understanding of what algorithm to execute and the global clock. The nodes in the network continuously flood information on what algorithm is running so that when a new node arrives, unless it is shielded by churn, it receives this information and can start participating in the algorithm. To maintain the clock value, nodes send their current clock value to their immediate neighbors. When a new node receives the clock information from a neighbor, it sets its own clock accordingly. Since nodes are not malicious or faulty, Lemma 3.1 ensures that information is correctly maintained in more than nodes.

### 3.4 Support Estimation Under an Oblivious Adversary

Suppose we have a dynamic network with nodes colored red in . is also called the support of red nodes. We want the nodes in the network to estimate under an oblivious adversary. We assume that the adversary chooses and which nodes in to color red, but it does not know the random choices made by the algorithm. Furthermore, we assume that churn can be linear in , i.e., .

Our algorithm uses random numbers drawn from the exponential distribution, whose probability density function, we recall, is parameterized by and given by for all . Furthermore, we notice that the expected value of a random number drawn from the exponential distribution of parameter is . We now present two properties of exponential random variables that are crucial to our context. Consider independent random variables , each following the exponential distribution of rate .

###### Property 2 (see [39] for example).

The minimum among all ’s, for , is an exponentially distributed random variable with parameter .

The idea behind our algorithm exploits Property 2 in the following manner. If each of the red nodes generate an exponentially distributed random number with parameter 1, then the minimum among those random numbers will also be exponentially distributed, but with parameter . Thus serves as an estimate of . To get a more accurate estimation of , we exploit the following property that provides us with sharp concentration when the process is repeated a sufficient number of times.

###### Property 3 (see [56] and pp. 30, 35 of [29]).

Let . Then, for any ,

 Pr(∣∣∣XK−1λ∣∣∣⩾ςλ)⩽2exp(−ς2K3).

We now present our algorithm for estimating in pseudocode format (assuming ); see Algorithm 1.

###### Theorem 3.7.

Consider an oblivious adversary and let be a an arbitrary fixed constant . Let . By executing Algorithm 1 to estimate both and , we can estimate to within for any with probability at least .

###### Proof.

Without loss of generality, let . Out of the red nodes up to nodes (chosen obliviously) can be suppressed, leaving us with

 (6) R′⩾R−βn⩾(1−2β)R

unsuppressed red nodes (since ). In a slight abuse of notation, we use and to denote both the cardinality and the set of red nodes and unsuppressed red nodes, respectively. We define

 U=⋂v∈R′\mathscInfl(v,t);

note that and (cf. Lemma 3.5). Let be some node in . Let

 Vu={v:v∈R∧u∈\mathscInfl(v,t)}.

For all , . Notice that computed by in line number 6 of Algorithm 1 is based on random numbers generated by all nodes in . Therefore, at round , node is estimating using the exponential random numbers that were drawn by nodes in . Since our adversary is oblivious, the choice of is independent of the choice of the random numbers generated by each . Therefore, is an exponentially distributed random number with rate (cf. Property 2). For any , let . When parallel iterations are performed, where , the required accuracy is obtained with probability (cf. Property 3). ∎∎

The algorithm for support estimation under an oblivious adversary (cf. Section 3.4) does not work under an adaptive adversary. To estimate the support of red nodes in the network, each red node draws a random number from the exponential distribution and floods it in an attempt to spread the smallest random number. When the adversary is adaptive, the smallest random numbers can easily be targeted and suppressed. To mitigate this difficulty, we consider a different algorithm in which the number of bits communicated is larger. In particular, the number of bits communicated per round by each node executing this algorithm is at most polynomial in .

Let be the support of the red nodes. Every node floods its unique identifier along with a bit that indicates whether it is a red node or not. At most nodes’ identifiers can be suppressed by the adversary for rounds leaving at least unsuppressed identifiers (cf. Corollary 3.3). Each node counts the number of unique red identifiers and non-red identifiers that flood over it and estimates to be .

This support estimation technique generalizes quite easily to arbitrary churn order. Therefore, we state the following theorem more generally.

###### Theorem 3.8.

Consider the algorithm mentioned above in which nodes flood their unique identifiers indicating whether they are red nodes or not and assume that the network is controlled by an adaptive adversary. Let be the order of the churn; we assume for simplicity that is either or . Then the following holds:

1. At least nodes estimate between and . Furthermore, these nodes are aware that their estimate is within and .

2. The remaining nodes are aware that their estimate of might fall outside .

When , it requires only rounds, but when , it requires rounds.

###### Proof.

Let be any one of the nodes that receive at least unsuppressed identifiers (cf. Lemma 3.5 and Lemma 3.6). Let and be the number of unique identifiers from red nodes and non-red nodes, respectively, that flood over . Let . This means that estimates to be . Note that and since , is estimated between and . Furthermore, since received identifiers, it can be sure that its estimate is between and .

If a node does not receive at least identifiers, then it is aware that its estimate of might not be within .

From Lemma 3.5, when , the algorithm takes rounds to complete because we want to ensure that unsuppressed nodes have flooded the network. When , as a consequence of Lemma 3.6, the algorithm requires rounds. ∎∎

## 4 Stable Agreement Under an Oblivious Adversary

In this section we will first present Algorithm 2 for the simpler problem of reaching Binary Consensus, where the input values are restricted to (cf. Section 2.1). We will then use this algorithm as a subroutine for solving Stable Agreement in Section 4.2.

Throughout this section we assume suitable choices of and such that the upper bound

 (7) β<112

can be satisfied for ; note that (7) must hold in addition to bound (1). Moreover, we assume that a node can send and process up to bits in every round, where is the size of the input value domain.

### 4.1 Binary Consensus

A node that executes Algorithm 2 proceeds in a sequence of checkpoints that are interleaved by rounds. Each node has a bit variable that stores its current output value. At each checkpoint , node initiates support estimation of the number of nodes currently having 1 as their output bit by using the algorithm described in Section 3.4. (At checkpoint , nodes estimate both: the support of 1 and 0.) The outcome of this support estimation will be available in checkpoint where has derived the estimation . If believes that the support of 1 is small (), it sets its own output to 0; if, on the other hand, is large (), sets its output to 1. This guarantees stability once agreement has been reached by a large number of nodes. When the support of 1 is roughly the same as the support of 0, we need a way to sway the decision to one side or the other. This is done by flooding the network whereby the flooding message of node is weighted by some randomly chosen value, say . The adversary can only guess which node has the highest weight and therefore, with constant probability, the flooding message with this highest weight (i.e., smallest random number) will be used to set the output bit by almost all nodes in the network.


text:
## PhoenixFire Group Title Does anyone know how to calculate how many times a ball will bounce if dropped from some height? Information: Restitution = 0.85 Mass = 0.7 kg Drop Height = 10 m Gravity = 9.81 m/s Ground is Horizontal. No air resistance. one year ago one year ago

1. akash123 Group Title

velocity of separation = e (velocity of approach)

2. PhoenixFire Group Title

3. akash123 Group Title

|dw:1347425035783:dw|

4. akash123 Group Title

does it make sense?

5. akash123 Group Title

|dw:1347424692991:dw|

6. PhoenixFire Group Title

why are you subtracting 0?

7. akash123 Group Title

Velocity of approach = V' - zero...which is velocity of ground

8. akash123 Group Title

sorry...Velocity of approach = V - zero...which is velocity of ground

9. akash123 Group Title

ball is colliding with the ground..and use this velocity of separation = e (velocity of approach)

10. akash123 Group Title

similarly velocity of separation = V'-0

11. PhoenixFire Group Title

okay. so e is the math constant.. what am i solving for?

12. akash123 Group Title

so 1st calculate V, the velocity of ball from which it hits the ground 1st time..

13. akash123 Group Title

no...e is the coefficient of restitution...and for ur problem e =0.85(given)

14. PhoenixFire Group Title

Potential Energy completely becomes Kinetic Energy just before collision $E_{system}=0+mgh=(0.7)(9.81)(10)=68.67$$E_{kinetic}=E_{system}$$v_{before}=\sqrt{2E_{kinetic} \over m}=14.01[ms^{-1}]$$\mu_r = {E_{kin. after} \over E_{kin.before}}$$E_{kin. after}=\mu E_{kin. before}=(0.85)(68.67)=58.67[J]$$v_{after}=\sqrt{2E_{kinetic} \over m}=12.91[ms^{-1}]$ I have both the velocities. Before and after the bounce.

15. akash123 Group Title

but see 4th line in ur solution..

16. Vincent-Lyon.Fr Group Title

The ball will bounce an infinite number of times, but the process will have a finite duration.

17. akash123 Group Title

velocity of separation = e (velocity of approach) it does not mean that... Energy after collision =e( energy before collision)?

18. PhoenixFire Group Title

That's one of the formula we were given.. that restitution is energy after divided by energy before. so i just used that to calculate energy after collision and then the velocity.

19. akash123 Group Title

But the correct formula is for velocity not for energy velocity of separation = e( velocity of approach)

20. akash123 Group Title
21. PhoenixFire Group Title

So our professor gave us the wrong equation... awesome.

22. akash123 Group Title

where are you from?

23. PhoenixFire Group Title

I'm studying in New Zealand.

24. akash123 Group Title

ok

25. akash123 Group Title

anyway...u can solve this problem by using correct formula

26. PhoenixFire Group Title

Wait, what do I do now that I've got the velocity before and after collision? vel approach =14.01 vel separation = 11.91

27. akash123 Group Title

yes...If u have done correctly... Better use kinematics relation..and use symbols dont plug in the value now..just use h,g and all..then u'll get better understanding of this problem

28. akash123 Group Title

|dw:1347427306605:dw|

29. akash123 Group Title

t' = time of reaching at the peak after 1st collision

30. akash123 Group Title

does it make sense?

31. PhoenixFire Group Title

So far yes.

32. akash123 Group Title

|dw:1347427668995:dw|

33. akash123 Group Title

good...:)

34. akash123 Group Title

e, e^2, e^3...will keep decreasing on...

35. PhoenixFire Group Title

general formula $v_n=\mu_r^n \sqrt{2gh}$$t_n=\mu_r^n \sqrt{2h \over g}$ I need to find n.

36. akash123 Group Title

yes...now u can tell the answer :)

37. akash123 Group Title

the ball will stop when v(n)=0...right?

38. PhoenixFire Group Title

well not really. because I want to find when it stops bouncing right? so v=0 or t=0. ends up just being n=0.. unless i'm failing at algebra

39. akash123 Group Title

and restitution <1..so tell me the answer?

40. akash123 Group Title

the ball will stop when v(n)=0

41. PhoenixFire Group Title

v(n)=0 $0=\mu_r^n \sqrt{2gh}$ Right?

42. akash123 Group Title

but now the question is when v(n) will be zero?

43. akash123 Group Title

yes...are u noticing something? e, e^2, e^3... with each v(n) for n=1,2,3,4....

44. akash123 Group Title

and e=0.85 which is less than 1

45. akash123 Group Title

now tell me... e^n will approach zero when n approaches....?

46. PhoenixFire Group Title

infinity

47. akash123 Group Title

yes...perfectly right:)

48. akash123 Group Title

so the ball will bounce infinite times...

49. PhoenixFire Group Title

well i got that answer like 3 hours ago... but i figured that there would be an actual answer.

50. akash123 Group Title

ok

51. akash123 Group Title

actually after each collision h keeps on decreasing...and theoretically h will approach zero after infinite bounces..

52. PhoenixFire Group Title

Well, thanks for the help! Showed me one of the equations was wrong which let me fix the first bit of the question. I guess I'm happy with infinite bounces for now. But I'll have a talk with my professor next week and see what he says.

53. akash123 Group Title

but practically ball can't go up to a size of atom after some bounces for large n

54. akash123 Group Title

as according to ur problem..u r starting with h=10m...later on ...h will reach in nanometer scale...and it's not practical that ball will bounce up to some nm height.

55. Vincent-Lyon.Fr Group Title

What you CAN work out is not number of bounces (infinite), but total time taken.

56. PhoenixFire Group Title

@Vincent-Lyon.Fr Out of curiosity how would you go about doing that?

format: plain


text:
# How can I evaluate $\sum_{n=0}^\infty (n+1)x^n$

How can if find the sum for:

$$\sum_{n=1}^\infty \frac{2n}{3^{n+1}}$$

I know the answer thanks to Wolfram Alpha. I'm more concerned with how to get to to that number. It cites tests to prove that it is convergent, but my class has never learned these before so I feel that there must be a simpler method.

In general, how can I evaluate $$\sum_{n=0}^\infty (n+1)x^n?$$

-

No need to use Taylor Series, this can be derived in a similar way to the formula for geometric series. Lets find a general formula for the following sum: $$S_{m}=\sum_{n=1}^{m}nr^{n}.$$

Notice that $$S_{m}-rS_{m}=-mr^{m+1}+\sum_{n=1}^{m}r^{n}$$

$$=-mr^{m+1}+\frac{r-r^{m+1}}{1-r}=\frac{mr^{m+2}-(m+1)r^{m+1}+r}{1-r}.$$ Hence $$S_m = \frac{mr^{m+2}-(m+1)r^{m+1}+r}{(1-r)^2}.$$
This equality holds for any $r$, but in your case we have $r=\frac{1}{3}$ and a factor of $\frac{2}{3}$ in front of the sum. That is $$\sum_{n=1}^{\infty}\frac{2n}{3^{n+1}}=\frac{2}{3}\lim_{m\rightarrow\infty}\frac{m\left(\frac{1}{3}\right)^{m+2}-(m+1)\left(\frac{1}{3}\right)^{m+1}+\left(\frac{1}{3}\right)}{\left(1-\left(\frac{1}{3}\right)\right)^{2}}$$

$$=\frac{2}{3}\frac{\left(\frac{1}{3}\right)}{\left(\frac{2}{3}\right)^{2}}=\frac{1}{2}.$$

We can define $$S_m^k(r) =\sum_{n=1}^m n^k r^n.$$ Then the sum above considered is $S_m^1(r)$, and the geometric series is $S_m^0(r)$. We can evaluate $S_m^2(r)$ by using a similar trick, and considering $S_m^2(r) - rS_m^2(r)$. This will then equal a combination of $S_m^1(r)$ and $S_m^0(r)$ which already have formulas for.

This means that given a $k$, we could work out a formula for $S_m^k(r)$, but can we find $S_k^m(r)$ in general for any $k$? It turns out we can, and the formula is similar to the formula for $\sum_{n=1}^m n^k$, and involves the Bernoulli Numbers. In particular, the denominator is $(1-r)^{k+1}$.

-
 That's a great answer, much simpler than how I've approached this question before. – mixedmath♦ May 27 '11 at 23:09

As indicated in other answers, you can reduce this to summing $\displaystyle{\sum_{n=1}^\infty na^n}$ with $|a|<1$ (by pulling out the constant $\frac{2}{3}$ and rewriting with $a=\frac{1}{3}$). This in turn can be reduced to summing geometric series by rearranging and factoring. Note that, assuming everything converges nicely (which it does):

$\begin{matrix} &a & + & 2a^2 & + & 3a^3 &+& 4a^4 &+& \cdots\\ =&a &+& a^2 &+& a^3 &+& a^4 &+& \cdots\\ +& & & a^2 &+& a^3 &+& a^4 &+& \cdots\\ +& & & & & a^3 &+& a^4 &+& \cdots\\ +& & & & & & & a^4 &+& \cdots\\ +& & & & & & & & & \vdots \end{matrix}$

Factoring out the lowest power of $a$ in each row yields

\begin{align*} \sum_{n=1}^\infty na^n &= a(1+a^2+a^3+\cdots)\\ &+ a^2(1+a^2+a^3+\cdots)\\ &+ a^3(1+a^2+a^3+\cdots)\\ &+ a^4(1+a^2+a^3+\cdots)\\ &\vdots \end{align*}

Each row in the last expression has the common factor $a(1+a+a^2+a^3+\cdots)$, and factoring this out yields

\begin{align*}\sum_{n=1}^\infty na^n &=a(1+a+a^2+a^3+\cdots)(1+a+a^2+a^3+\cdots)\\ &=a(1+a+a^2+a^3+\cdots)^2.\end{align*}

Now you can finish by summing the geometric series.

Eric Naslund's answer was posted while I was writing, but I thought that this alternative approach might be worth posting. I also want to mention that in general one should be careful about rearranging series as though they were finite sums. To be more formal, some of the steps above would require justification based on absolute convergence.

-

If you want a solution that doesn't require derivatives or integrals, notice that \begin{eqnarray} 1+2x+3x^2+4x^3+\dots = 1 + x + x^2 + x^3 + \dots \\ + x + x^2+ x^3 + \dots\\ + x^2 + x^3 + \dots \\ +x^3 + \dots \\ + \dots \\ =1 + x + x^2 + x^3+\dots \\ +x(1+x+x^2+\dots) \\ +x^2(1+x+\dots)\\ +x^3(1+\dots)\\ +\dots \\ =(1+x+x^2+x^3+\dots)^2=\frac{1}{(1-x)^2} \end{eqnarray}

-
 I was going to say that! You are fast! – dot dot Oct 29 '12 at 22:44 wow this is dam clever – Justin Meltzer Oct 29 '12 at 22:47

Factor out the 2/3. Then write $$\sum_{n=1}^{\infty} \frac{n}{3^n} = \sum_{n=1}^{\infty} \frac{1}{3^n} + \sum_{n=2}^{\infty} \frac{1}{3^n} + \sum_{n=3}^{\infty} \frac{1}{3^n} + \cdots$$

It is easy to show that $$\sum_{n=m}^{\infty} \frac{1}{3^n} = \frac{3}{2} \left(\frac{1}{3} \right)^m$$ and so $$\sum_{n=1}^{\infty} \frac{n}{3^n} = \frac{3}{2} \sum_{n=1}^{\infty} \left( \frac{1}{3} \right)^n$$ which you can sum. Don't forget to put the 2/3 back in.

-

Hints

1. You know (don't you?) the formula for $S(a) = \sum_{n=0}^\infty a^n$ for $|a| < 1$

2. Take the derivative (with respect to $a$) of both sides to obtain a formula for $\sum_{n=1}^\infty n a^n$

3. Show that your series can be put in that form.

-
Thanks for answering. 1) No I don't know that formula 2) Can you explain by what you mean by derive both sides? – Backus Apr 3 '11 at 21:59
1. See here: en.wikipedia.org/wiki/Geometric_series 2) Derivation (or differentiation) is a mathematical operation (well, more than that) that is taught in Calculus - if you don't know about it, forget about my answer (and xen0m's). Perhaps you can solve your problem without knowing Calculus, by other methods... but normally you first learn calculus, then solve series. – leonbloy Apr 3 '11 at 22:05
Yeah I don't know calculus – Backus Apr 3 '11 at 22:06
The definition of 'convergence' is based on calculus. So without knowing calculus, it is pretty hard to understand anything about series. Perhaps you can tell us why you are interested in this particular sum? – wildildildlife Apr 3 '11 at 22:32
@wildildildlife I'm in a class that covers precalculus and calculus in one year, and we are transitioning currently. For whatever reason we learned series early. Our class still understood convergence without calculus though. – Backus Apr 3 '11 at 23:32

Note that $\int \left( 1 + 2x + 3x^2 + 4x^3 + \ldots \right)dx = x + x^2 + x^3 + \ldots + c$, i.e., a geometric series, which converges to $x/(1 - x)$. So $$\frac{d}{dx} \left( \frac{x}{1 - x} \right) = \frac{(1 - x)(1) - x(-1)}{(1 - x)^2} = \frac{1}{(1 - x)^2}.$$ Therefore $$1 + 2x + 3x^2 + 4x^3 + \ldots = \frac{1}{(1 - x)^2}.$$

-
 +1, but wouldn't it have been simpler to say that it was the derivative of $1+x+x^2+...$, converging to $\frac1{1-x}$? – Mike Oct 29 '12 at 22:46 I decided to start with what was given, so it is easier for the OP to see. – glebovg Oct 29 '12 at 22:48 Justin, observe that this only holds for $|x| < 1$, otherwise your sum simplifies to $\infty$. – glebovg Oct 29 '12 at 22:54 What I meant is that you chose $c=0$ while $c=1$ is a more well known series and is easier to take the derivative of. – Mike Oct 29 '12 at 23:23

You can find by differentiation. Just notice that $(x^n)' = nx^{n-1}$. By the theory of power series we obtain (by uniform convergence on any compact subset of $(-1,1)$) that $$\left(\sum_{n=1}^\infty x^n\right)' = \sum_{n=1}^\infty (x^n)' = \sum_{n=1}^\infty n x^{n-1}.$$ The sum on the left hand side is equal to $\left(\frac{x}{1-x}\right)'$. You need to notice that your sum can be written in a similar way as $\sum_{n=1}^\infty nx^{n-1}$.

-
 Thank you for helping, but I have never learned differentiation. – Backus Apr 3 '11 at 21:58

My favorite proof of this is here

I also have the following method for $\sum_{n=1}^\infty {n\over 2^{n-1}}$ (one can use a similar method for $\sum_{n=1}^\infty {n\over3^n}$):

We first show that $\sum\limits_{n=7}^\infty {n\over 2^{n-1}} ={1\over4}$.

We start with a rectangle of width 1 and height $1/4$. Divide this into eights:

Now divide each eighth-rectangle above in half and take 7 of them. This gives $A_1={7\over 2^6}$.

There are $2\cdot8-7=9$ boxes left over, each having area $2^{-6}$.

Divide each remaining $16^{\rm th}$-rectangle in half and take 8 of them. This gives $A_2={7\over 2^6}+{8\over 2^7}$.

There are $2\cdot9-8=10$ boxes left over, each having area $2^{-7}$.

Divide each remaining $32^{\rm nd}$-rectangle in half and take 9 of them. This gives $A_3={7\over 2^6}+{8\over 2^7}+{9\over 2^8}$.

There are $2\cdot10-9=11$ boxes left over, each having area $2^{-8}$.

Divide each remaining $64^{\rm th}$-rectangle in half and take 10 of them. This gives $A_4={7\over 2^6}+{8\over 2^7}+{9\over 2^8}+{10\over2^9}$.

There are $2\cdot11-9=12$ boxes left over, each having area $2^{-9}$.

At each stage, we double the number of remaining boxes, keeping the same leftover area, and take approximately half of them to form the next term of the series.

At the $n^{\rm th}$ stage, we have $$A_n= {7\over 2^6}+{8\over 2^7}+\cdots+{6+n\over2^{5+n}},$$

with leftover area $$2(n+7)-(n+6)\over 2^{n+5}.$$

It follows that, $${7\over2^6}+{8\over2^7}+{9\over2^8}+\cdots= {1\over4}.$$ Consequently, $$\sum_{n=1}^\infty{n\over 2^{n-1}}= \sum_{n=1}^6 {n\over 2^{n-1}} +\sum_{n=7}^\infty{n\over 2^{n-1}} ={15\over 4}+{1\over4}=4.$$

You can also "Fubini" this (I think this is what Jonas is doing).

-


text:
The marvellous @solvemymaths tweeted some time ago about finding least common multiples and highest common factors:

I broadly agree with Ed - I have an antipathy towards Venn diagrams that’s probably more fierce than they deserve. The tweet got me thinking about how I think about LCM and HCF calculations. I’m going to pick two sizeable numbers, 768 and 480, for my example.

### Generate the factors

There are all sorts of methods for doing this, and I don’t really care about the details. Here’s the way I instinctively did it on the whiteboard - you might prefer a tree, or more working. Doesn’t matter. Give me a correct prime factorisation and I don’t care if it was whispered into your ear by the ghost of Fermat.

So I’ve worked out that $768 = 2^8 \times 3$ and that $480 = 2^5 \times 3 \times 5$

### A note on language

The language of ‘least common multiple’ and ‘highest common factor’ is counterintuitive, but correct: the one with ‘highest’ in is less than the one with ‘least’ in. That’s because factors are never bigger than the number you’re working with, and multiples are never smaller. So: it’s worth focussing on the kind of number you want rather than the words highest and least. It will trip people up.

### LCM

The least common multiple is the smallest number that you can divide by both of your examples. Its prime factorisation must include all of the factors of both numbers. So, we look at all of the powers-of-a-prime factors of each number in turn, and pick whichever one has the bigger power (or, if it’s a tie, the number in question).

Here, that’s $2^8$, $3^1$ and $5^1$, so the LCM is $2^8 \times 3^1 \times 5^1$, which is $128 \times 3 \times 5 = 3,840$.

### HCF

The highest common factor is the biggest number that divides into both of your example; in this case, we look at each power-of-a-prime factor and pick the smaller power. Again, if it’s a tie, we just take the common number; if a factor appears in one number but not the other, we ignore it. For this one, it’s $2^5$ and $3^1$. (If you’re uncomfortable with ditching the 5, you can consider 768 as having a factor of $5^0$.)

Working it out, that gives $32 \times 3 = 96$ as the highest common factor of both.


text:
# Bitcoin is incentive-aligned savings technology

Posted by : at

Category : bitcoin

Society is an extremely complex system. People interact in an intricate network of relationships, both on a personal level or as part of more complex institutions (companies, associations, political parties, religions, geographical communities). This makes it very difficult to analyze − and therefore, to predict − how the system will evolve over time. Will those interactions bring to an improvement of conditions for most people? Nobody can say for sure, and the road to progress is a bumpy one.

But there are certainly ways to look at this complexity and still make some educated guesses on what can (and likely will) happen. One such way is to look at where are the incentives in the system. People (and any other entities in the system) are likely to do what brings them a benefit. While benefit itself is a very wide concept that can mean different things for different people, a very common type of benefit is definitely at the center of how our civilization operates: financial gains. People (and even more so companies) are likely to do what brings them a financial benefit.

Admittedly, this is a simplification, as people are also driven by other incentives. There are benefactors that are willing sacrifice some wealth for the benefit of other people. There are magnates that are willing to finance enterprises (or even artists) for some greater good, because they want to bring an improvement to the world.

Yet, making sure that the financial incentives of the participants in a system are aligned with the goals and values of the system is of paramount importance. When that happens, the natural state of the system is such that the satisfaction of certain properties is guaranteed, and a small deviation will naturally be met with an opposite force that brings the system back to its equilibrium. Instead, a system where the incentives are not aligned is like the egg in the picture above, that needs an external force to stay in place. When that force is removed, the egg will roll on its side, and if you’re unlucky, you’ll soon find it splattered on the ground.

Discovering that the incentives of participants of a system are not aligned with the desired properties and behavior of the system itself is a red flag that calls into question its long term sustainability.

In this article, we explore the incentives at play in the process of printing money, for different forms of money − and why Bitcoin is different.

# Governance and money production

Who prints the money? In early forms of money, the answer was nobody: money likely emerged without any central authority. People naturally appreciated certain items, which made them desirable to collect, which in turn led to the appearance of the monetary properties of those items out of pure necessity. [1] By virtue of being the right combination of rare and hard to make, shells, wearables and jewelry naturally served the purpose of facilitating trade.

Among the collectibles, precious metals like silver and gold eventually took over as better forms of money, as they had many desirable properties for a monetary medium: they are easy to carry and to protect, they are relatively easy to assess in terms of quality to decide their value, and they are rare in nature. Scarcity is essential: valuable items bring a constant incentive to find or produce more of them, therefore flooding the market (and crashing the price) of anything that is not hard to find/produce.

## Coinage

The invention of coinage made them much easier to use for day-to-day trade: by forging metals in standardized forms, with coins that always contained the same amount of the precious metal, one could easily use them as units of value, making it possible to pay someone else any exact amount by choosing the right amount of the right coins. As coins were issued by someone as trusted as the King, the convenience was greatly increaed as well, as people didn’t have to check how much precious metal was in each coin (assuming that there are not too many fake coins in circulation).

### With coinage comes debasement

Unlike raw metals, coins are designed to always have the same value. Therefore, they have a serious defect: by removing small amounts of the material used to make the coin, you extract some precious metal without changing the face value of the coin itself. Multiple methods of coin debasement existed to shave off some of the juicy metal − which were, of course, illegal.

Governments weren’t immune to the temptation to do the same − with the additional benefit that nobody could jail them for it. The Roman Denarius, which had 6.81g of silver in 267 BC, was progressively retariffed with smaller amounts of precious metals in later coinages, by decreasing both its weight and its purity. By 241 AD it weighed 3.31g, half the original weight, with its purity reduced to just 48% by making alloys with other cheap metals.

### Incentive analysis

• People have the incentive to debase coins by shaving them.
• Government have the incentive to debase the currency, either by shaving them or by a new coinage with a smaller amount of precious metal.

## Representative money

As a way to overcome the shortcomings of commodity money (where the value of the coin equals the value of the commodity making it), representative money was used instead: here, the coins (or paper notes) have carry little or no value, but they represent a claim on some commodity that is stored and guaranteed in a safe place.

Commodity-backed money was widely used in modern times, backed by silver or by gold. The convertibility with the commodity that the claim represents ensured that, to all practical effects, the coins and notes could be used in place of the backing commodity. Except in one aspect, that is not strictly practical, therefore goes unnoticed in the short term: it alters the incentives.

### Incentive analysis

• Shaving coins is pointless. People have an incentive to debase the currency by making counterfeit coins that look just like the real ones. As long as a proper effort is put into place to make it difficult (or risky by means of hefty punishments), this can become unlikely.
• The central authorities has a clear incentive to debase the currency by covertly creating coins or notes in excess to the ones that are backed by the actual reserves, or to unilaterally change the conversion rate against the backed asset.
• In the most extreme case, the government can exploit the dominant position of the currency to end the convertibility against the backed asset, as the 1971 Nixon shock.

In some instances (including the Nixon shock) such measures were called “temporary”. But while there is an incentive to introduce them, there is no incentive in reversing them!

## Fiat money

Once the backing is removed completely, we reach the most modern form of centralized money: fiat money, which is money by decree. It doesn’t have any intrinsic value, nor it is backed by anything that has value and is stored elsewhere. A pure

The government cannot directly print money. Central banks, instead, can expand the money supply by extending loans.

Governments can sell government bonds in order to get extra money to spend, therefore getting indebted. But when these bonds end up into the balance sheet of central banks, that results in an increase of money supply (=money printing).

### Incentives analysis

• Public debt: there is a clear, perpetual incentive for the current politicians to increase public debt. That gives them money to spend now, while any negative consequences will be suffered by someone else in the future¹.
• Money supply expansion: banks make money out of loans they extend, and the state is usually a trusted client. So when government emit bonds, a large fraction tends to be purschased from central banks.

Given that governments have an incentive to increase debt, and banks have a financial incentive to purchase government debt, one would expect that, over time:

• politicians will use their power to influence banks so that they can increase the amount of public indebtedness
• central banks will increase the amount of government bonds in their balance sheets, in turn becoming less independent from the government.

# What’s going to happen?

By looking at the incentives of each of the money systems above, we can summarize as follows:

• Early forms of money were replaced by precious metals
• Convenience leads to precious metals being adopted by means of coinage
• Incentives lead to commodity money being replaced by representative money (backed by reserves)
• Incentives lead to representative money overgrowing its reserves, and eventually to become fiat money

And what will happen to fiat money? The incentives simply suggest that governments will keep getting indebted, and central banks will keep buying this debt, therefore increasing the money supply. As the economic rubberband keeps getting stretched, I see only two possible outcomes:

• Government default. The government admits that the debt is never going to be paid back.
• Money is printed directly to pay off debt, with a direct, huge increase of the monetary base which will devaluate the currency heavily.

Both will have large scale consequences that are hard to predict, and frankly quite scary.

But what do I know? I’m not an economist. Years ago, I was discussing the second option with a friend who know much more than me about the inner workings of macroeconomics, and he told me that the second option is an absurdity. Except that it is now a regular topic of discussion in the US political debate, see for example here.

# Bitcoin and incentives

Like any distributed protocol, making sure that incentives were aligned was certainly one of the aspects that kept Satoshi awake. As Bitcoin still didn’t collapse, it looks like they did a good job.

There are many participants in the system, with different sets of incentives; a full discussion can’t prescind from a detailed technical discussion of how Bitcoin works, and it goes beyond the scope of this post. Here, I just want to discuss the incentives at play in the process of minting new Bitcoins. In other words, who prints new coins? What prevents them from printing more?

## Nodes and rules

The Bitcoin network is composed of (at least) tens of thousands of nodes. Each of them is a machine that is connected to the Internet, and it does a bunch of things that keep the network alive. The most important task is that of verifying a certain number of consensus rules: each node will refuse to propagate a transaction or a block that violates the rules. A special kind of node software is used by miners: they are the only ones that can actually add a new block to the blockchain; a new block is where the new transactions are stored, so there is no progress without miners. Running a miner requires specialized hardware that is built to participate in Proof of Work mechanisms that secures the blockchain.

New Bitcoins are issued for every new block, according to a scheduled that Satoshi set in stone since the beginning: initially, the miner that created a block were rewarded 50 ₿. But the reward is halved about every 4 years (more precisely, every 210000 blocks). Therefore, in November, 2012, the reward became 25 ₿, then 12.5 ₿ in July 2016, and only 6.25 ₿ in May 2020. Sometime aroung year 2140, the issuance of new bitcoins will stop completely, and the network will only circulate the existing coins.

## Changing the rules

Because the network is designed to kick out any bad guy that does not respect the consensus rules, no participant of the network has the incentive to violate them. Therefore, a node that tried to publish an invalid transaction (or a miner who tried to propagate an invalid block assigning 1000 ₿ to himself) would be very disappointed.

But after all, rules are part of the software, and the software can be changed. What prevents the majority of the nodes to change the rules, and − say − bring the block reward to 1000 ₿? You name it: incentives! Why would they? Most of the nodes that participate to the economic activity (buying, selling or holding bitcoins) own some of them. Therefore, implementing new rules that decrease the value of the coins they possess goes against their financial incentive.

The only rule changes that can find consensus of the majority of the nodes are those that improve Bitcoin for everyone, or at least the vast majority of the users².

It is a sometimes claimed that the majority of the miners can change the rules if they want to do it. That would be a problem, as they clearly have a potential interest in doing so, for example by issuing more coins so they can earn more money. A detailed discussion of whether this is possible is out of scope for this post. The short answer is: they could potentially impose some types of changes that can be implemented via a soft-fork (for example: censoring some transactions); but changing the issuance requires a hard-fork. The fact that even a supermajority of miners can’t easily impose a hard-fork was tested in 2017 when miners abandoned the contentious Segwit2X hard-fork proposal that was supported by a majority of 90% of the miners, once it became clear that the market supported the regular Segwit soft-fork instead.

Therefore, we can be reasonably certain that Bitcoin won’t ever introduce inflation, because the it’s incentive-aligned with its absence.

# What does this mean?

This paragraph is about the future, therefore it’s purely my opinion. There’s plenty of people who thinks that Bitcoin will fail and go to zero, or that it’s probably rat poison squared (but at least, by virtue of being squared, it should never go below zero, unlike oil!). Do your own research and invest in learning first and foremost.

At the time of writing, the price of 1 ₿ is above 11000$, and the total value of all Bitcoins in circulation is just above 200 billion dollars, which is still a relatively small number in the scale of global economy (see [2] for a great comparative visualization of the size of different type of money and other assets). Therefore, it’s still too small to have a substantial impact on the world economy. But it now exists. While it is still not widely considered as a savings technology, recognition is growing. Hedge fund manager Paul Tudor Jones bought Bitcoin; using his words, “Every day that goes by that Bitcoin survives, the trust in it will go up”. More recently, The Business Intelligence company MicroStrategy bought 250M$ worth of Bitcoin, allocating to it 20% of their cash reserves.

As Bitcoin has a number of properties that make it a better saving technology than anything else that exists, I expect Bitcoin to still grow in terms of market capitalization; more people, companies and funds will start using it as hedge against economic collapse, rather than a speculation; this will help stabilize its value. Less volatility will lead to even more people and companies allocating it as part of their savings.

How much of the world’s wealth will ultimately be stored in Bitcoin is anyone’s guess. But if it doesn’t fail, people will have a real savings technology that is free and permissionless, cannot be debased or controlled by any central party.

This will have profound implications, which I can’t claim to fully understand. But I believe that saving is common sense, and that’s what Bitcoin brings back.

Bitcoin restores the right to save.

# References

1. Nick Szabo, Shelling Out: The Origins of Money
2. Jeff Desjardins, All of the World’s Money and Markets in One Visualization

# Footnotes

¹ Unless you believe that you can have the free cake since “debt is money that we owe to ourselves” like a famous economist, an argument that would make anyone extremely wary, unless they studied economics.

² Well, even in that case, it’s a long and difficult process that typically requires years. The 2017 Segregated Witness upgrade was in the works since 2015.


text:
## CryptoDB

### Xiwang Cao

#### Publications

Year
Venue
Title
2010
EPRINT
In this note, we prove that the order of $x^p-x-1\in \F_p[x]$ is $\frac{p^p-1}{p-1}$, where $p$ is a prime and $\mathbb{F}_p$ is the finite field of size $p$. As a consequence, it is shown that $x^p-x-a\in \mathbb{F}_p[x]$ is primitive if and only if $a$ is a primitive element in $\mathbb{F}_p$.
2010
EPRINT
Let $\mathbb{F}_{q}$ be a finite field, $\mathbb{F}_{q^s}$ be an extension of $\mathbb{F}_q$, let $f(x)\in \mathbb{F}_q[x]$ be a polynomial of degree $n$ with $\gcd(n,q)=1$. We present a recursive formula for evaluating the exponential sum $\sum_{c\in \mathbb{F}_{q^s}}\chi^{(s)}(f(x))$. Let $a$ and $b$ be two elements in $\mathbb{F}_q$ with $a\neq 0$, $u$ be a positive integer. We obtain an estimate of the exponential sum $\sum_{c\in \mathbb{F}^*_{q^s}}\chi^{(s)}(ac^u+bc^{-1})$, where $\chi^{(s)}$ is the lifting of an additive character $\chi$ of $\mathbb{F}_q$. Some properties of the sequences constructed from these exponential sums are provided also.

Lei Hu (1)


text:
# Self-adjoint, globally defined Hamiltonian operators for systems with boundaries - Mathematical Physics

Self-adjoint, globally defined Hamiltonian operators for systems with boundaries - Mathematical Physics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: For a general self-adjoint Hamiltonian operator \$H 0\$ on the Hilbert space\$L^2\RE^d\$, we determine the set of all self-adjoint Hamiltonians \$H\$ on\$L^2\RE^d\$ that dynamically confine the system to an open set \$\Omega \subset\RE^d\$ while reproducing the action of \$ H 0\$ on an appropriate operatordomain. In the case \$H 0=-\Delta +V\$ we construct these Hamiltonians explicitlyshowing that they can be written in the form \$H=H 0+ B\$, where \$B\$ is asingular boundary potential and \$H\$ is self-adjoint on its maximal domain. Anapplication to the deformation quantization of one-dimensional systems withboundaries is also presented.

Autor: Nuno Costa Dias, Andrea Posilicano, Joao Nuno Prata

Fuente: https://arxiv.org/


text:
# Find the line of intersection between two planes.

Consider the planes:

$$\begin{eqnarray}x + y + 2z = 1\\ −x + 2y + z = 5\end{eqnarray}$$

1. Find the angle between the two planes.
2. Find the line of intersection of the two planes.

I was able to answer part (1), and I found that the angle was $$60$$ degrees ($$\pi/3$$ radians). The part that I'm having trouble with is finding the line of intersection of the two planes. I have no idea where to start, any help would be much appreciated.

Adding both equations we get $$3y+3z=6$$ or $$y=2-z$$ substituting $$z=t$$ we obtain $$y=2-t$$ and $$x=2-t+2t=1$$ gives us $$x=-1-t$$ So our line has the equation $$[x,y,z]=[-1,2,0]+t[-1,-1,1]$$ where $$t$$ is a real number.

• Thanks for the help. The only part I don't understand is how you came up with the second last line. I'm a bit confused. – N_Mathematics_B Sep 25 '19 at 8:35
• @N_Mathematics_B The usual method for this question: let one of the variables be a "parameter" (that you can rename $t$), then solve the system for the other two variables: you get a parametric equation of the line. Here $z$ is the parameter, so the parametric equation is $(x=f(t), y=g(t), z=t)$, with linear functions $f$ and $g$. – Jean-Claude Arbaut Sep 25 '19 at 8:38
• I understand now, thanks for the help. – N_Mathematics_B Sep 25 '19 at 8:39

As an alternative, the normal vectors to the planes are:

• $$n_1=(1,1,2)$$
• $$n_2=(-1,2,1)$$

then a direction vector for the line is

$$n_1 \wedge n_2 = (-3,-3,3)$$

• +1 Interestingly, normal vectors also give very easily an answer to the first question. – Jean-Claude Arbaut Sep 25 '19 at 8:36
• @Jean-ClaudeArbaut Yes, that's a very good point! – user Sep 25 '19 at 8:50


text:
# Prime numbers and Topology

I was doing this homework for my university in which I had to prove that the set of prime numbers was infinite, just like Harry Furstenburg did by considering the following topology:

Let $\mathcal{O} \subset \mathcal{P}(\mathbb{Z})$ be a topology defined as:

$\mathcal{O}:=\{\emptyset\}\cup\{A\subset\mathbb{Z}:A$ is an arbitrary union of arithmetic progressions$\}$

Remember that an arithmetic progression is a subset $S\subset\mathbb{Z}$ defined as $S:=\{r+nd : n \in \mathbb{Z}\}$, where $r,d\in\mathbb{Z}$ and $d\neq0$.

Everything went well until I got to the last question, which I unfortunately couldn't even start. It said:

Is $(\mathbb{Z},\mathcal{O})$ a metrizable topology?

Thank you very much.

• It means there is a homeomorphism (bi-continuous, bijective) map from your topology onto a metric space. – BananaCats Category Theory App Mar 11 '15 at 17:44
• See arxiv.org/pdf/1008.0713.pdf. They define a norm. Then a metric is just $d(x,y) = | x - y|$ – BananaCats Category Theory App Mar 11 '15 at 17:52
• @EnjoysMath: I think it'd be better if you had written $\lVert x-y\rVert$. That is the notation of the paper, and far less confusing: $\lvert x-y\rvert$ has a commonly accepted meaning (for integers), which would make the topology discrete. – tomasz Mar 11 '15 at 18:00
• Thank you Enjoys Math for that incredible pdf and thank you tomasz as well, I totally agree with that. – GSF Mar 11 '15 at 19:15

There are only countably many arithmetic progressions, and the arithmetic progressions form a base $\mathscr{B}$ for $\mathcal{O}$, so the space is second countable. It’s clearly $T_1$, since for any distinct integers $m$ and $n$ the nbhd
$$\left\{m+k\big(|m-n|+1\big):k\in\Bbb Z\right\}\in\mathscr{B}$$
of $m$ misses $n$.
Let $B=\{r+nd:n\in\Bbb Z\}\in\mathscr{B}$. If $m\in\Bbb Z\setminus B$, $\{m+nd:n\in\Bbb Z\}$ is an open nbhd of $m$ disjoint from $B$, so $B$ is clopen. The space is therefore $T_3$ and second countable, so it’s metrizable by the Uryson metrization theorem. In fact, since it’s a countable metrizable space without isolated points, it’s homeomorphic to $\Bbb Q$ with the usual topology.


text:
# Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$

Corollary 7.3.2.13. Let $F: \operatorname{\mathcal{C}}\rightarrow \operatorname{\mathcal{D}}$ be a functor of $\infty$-categories, and let $U: \operatorname{\mathcal{C}}\rightarrow \Delta ^1$ be a cocartesian fibration having fibers $\operatorname{\mathcal{C}}_{0} = \{ 0\} \times _{ \Delta ^1} \operatorname{\mathcal{C}}$ and $\operatorname{\mathcal{C}}_{1} = \{ 1\} \times _{\Delta ^1} \operatorname{\mathcal{C}}$. Choose a functor $G: \operatorname{\mathcal{C}}_0 \rightarrow \operatorname{\mathcal{C}}_1$ and a natural transformation $\beta : \operatorname{id}_{\operatorname{\mathcal{C}}_0} \rightarrow G$ which exhibits $G$ as given by covariant transport along the nondegenerate edge of $\Delta ^1$ (see Definition 5.2.2.4). The following conditions are equivalent:

$(1)$

The functor $F$ is left Kan extended from $\operatorname{\mathcal{C}}_0$.

$(2)$

The natural transformation $F(\alpha ): F|_{ \operatorname{\mathcal{C}}_0} \rightarrow F|_{ \operatorname{\mathcal{C}}_1 } \circ G$ exhibits $F|_{ \operatorname{\mathcal{C}}_1 }$ as a left Kan extension of $F|_{ \operatorname{\mathcal{C}}_0 }$ along $G$.

Proof. Let us regard the functor $G$ as fixed. Let $M = (\Delta ^1 \times \operatorname{\mathcal{C}}_0) \coprod _{ ( \{ 1\} \times \operatorname{\mathcal{C}}_0 )} \operatorname{\mathcal{C}}_{1}$ be the mapping cylinder of $G$, and let us abuse notation by identifying $\operatorname{\mathcal{C}}_0 \simeq \{ 0\} \times \operatorname{\mathcal{C}}_0$ and $\operatorname{\mathcal{C}}_1$ with (disjoint) simplicial subsets of $M$. We can then identify $\alpha$ with a morphism of simplicial sets $\mu : M \rightarrow \operatorname{\mathcal{C}}$ which is the identity when restricted to $\operatorname{\mathcal{C}}_0$ and $\operatorname{\mathcal{C}}_1$.

Note that the tautological map

$\Delta ^1 \times \operatorname{\mathcal{C}}_0 \simeq \operatorname{\mathcal{C}}_{0} \star _{ \operatorname{\mathcal{C}}_0} \operatorname{\mathcal{C}}_0 \rightarrow \operatorname{\mathcal{C}}_{0} \star _{ \operatorname{\mathcal{C}}_1 } \operatorname{\mathcal{C}}_1$

extends to a morphism of simplicial sets $\lambda : M \rightarrow \operatorname{\mathcal{C}}_0 \star _{ \operatorname{\mathcal{C}}_1} \operatorname{\mathcal{C}}_1$ which is the identity on $\operatorname{\mathcal{C}}_1$; moreover, $\lambda$ is a categorical equivalence (Proposition 5.2.4.4). It follows that precomposition with $\lambda$ induces an equivalence of $\infty$-categories

$\operatorname{Fun}_{ \operatorname{\mathcal{C}}_0 \coprod \operatorname{\mathcal{C}}_1 / }( \operatorname{\mathcal{C}}_0 \star _{ \operatorname{\mathcal{C}}_1 } \operatorname{\mathcal{C}}_1, \operatorname{\mathcal{C}}) \rightarrow \operatorname{Fun}_{ \operatorname{\mathcal{C}}_0 \coprod \operatorname{\mathcal{C}}_1 / }( M, \operatorname{\mathcal{C}}).$

We can therefore choose a functor $G: \operatorname{\mathcal{C}}_0 \star _{\operatorname{\mathcal{C}}_1} \operatorname{\mathcal{C}}_1 \rightarrow \operatorname{\mathcal{C}}$ satisfying $G|_{ \operatorname{\mathcal{C}}_0 } = \operatorname{id}_{\operatorname{\mathcal{C}}_0}$ and $G|_{ \operatorname{\mathcal{C}}_1} = \operatorname{id}_{ \operatorname{\mathcal{C}}_1 }$, where $G \circ \lambda$ is isomorphic to $\mu$ as an object of the $\infty$-category $\operatorname{Fun}_{ \operatorname{\mathcal{C}}_0 \coprod \operatorname{\mathcal{C}}_1 / }( M, \operatorname{\mathcal{C}})$ Since condition $(2)$ depends only on the homotopy class of the natural transformation $\alpha$ (Remark 7.3.1.9), we are free to modify $\alpha$ and may therefore assume that $G \circ \lambda = \mu$. In this case, Proposition 7.3.2.10 allows us to reformulate condition $(2)$ as follows:

$(2')$

The functor $(F \circ G): \operatorname{\mathcal{C}}_0 \star _{ \operatorname{\mathcal{C}}_1} \operatorname{\mathcal{C}}_1 \rightarrow \operatorname{\mathcal{D}}$ is left Kan extended from $\operatorname{\mathcal{C}}_0$.

Since $\lambda$ and $\mu$ are categorical equivalences of simplicial sets (Proposition 5.2.4.4), the functor $G$ is an equivalence of $\infty$-categories (Remark 4.5.3.5). The equivalence of $(1)$ and $(2')$ is now a special case of Proposition 7.3.3.14. $\square$