Welcome to Ben's website.
Text and more text.
Loreum islkdsfja ;lekf f lwk .
Facetime should run facial recognition to pinpoint areas to encode with higher resolution.
Some thoughts on synchrony and oscillating waveforms: We need a model that captures different network topologies and directly maps that topology to a degree of partial synchrony. This motivates us modeling the network topology as a set of waveforms at different locations; each oscillation corresponds to a message that has circulated a subset (or the entire) network. The more interesting question is what happens when waves overlap; this is where we define a concept of synchrony. 0------------->1-------------->2------------ ----->A--------------------------->B-------- At a given clock time, (a period of real time between two clock ticks; OR, and integer that identifies a numbered wave in the reference clock signal), another signal is synchronous with it if it coincides twice within that clock time (nyquist??), proving that the signal can be reached within a given clock from the location. (AKA - the observed signal has a shorter wavelength than the clock signal.) ------- alternative: if you stare at an oscillating light, and it doesn't appear to flash, the light is synchronous w.r.t. your observation signal (even if you don't send anything to the light?). (and at last I see... the liiiiight...) But again, this could be unidirectional/ ------- Alright: Here's another type up. Last time we were talking about how the topology of a network might affect the performance of Dolevs'. For instance, Dolev's can probably run fairly well on Jun's random edge-selection graph. This is an attempt to model the network behavior and establish bounds? for synchrony on a given network. Moreover, this opens avenues for modifying the topology of networks to be more synchronous. - Q: given a network topology/behavior map, how synchronous can it be? More specifically, at what frequency can we run a synchronous algorithm (rounds of the synchronous assumption) for a subset of nodes M? If M = majority? Q: Is a minority synchronous M useful? - The model: Insight: local clock times, delivery times, crashes, too complicated. Generalization: every node, is a clock! If the node i has crashed, its frq_i = 0. If the node i is always online, its frq_i = +inf. Message sending is also modeled with clocks: each edge with a message delay is modeled as passing through another node, with a clock, with frq_d = d, the frequency of messages that can traverse this edge. Clocks therefore represent processing delay. So, given a network topology, add a clock to each node and each edge, representing the processing delay. Edges now deliver messages instantaneously. Unprocessed messages are kept in infinite queues (assumption). Now what? Let's simplify, and say that edges between two nodes A and B have a clock frq equivalent to the slowest of the two nodes, and is undirected (that is, both directions share the same frequency). With this network in mind, that has no message delays, the only thing that matters is the node clocks. This is easier to intuit, though I think the following work might apply to full edge/node graphs as well. In sum, in this simplification, edges have no message delay, but nodes have a processing delay. One more unrealistic assumption: node frequencies do not change over time. The question is, how fast can the network process a runloop that involves multiple nodes M? Let's say each node i can execute a function on messages in the queue and its own memory. It can execute this runloop at its frequency f_i. The goal is to output True if its frequency can drive M = N/2 (for now) of the network, and False otherwise, after O(N) (or O(N^2)?) iterations. If it can satisfy this goal then it can run the actual synchronous algorithm (in other words, other nodes can assume synchrony if they can hear from this node). A node returning False can prove? that it is not a bottleneck node (you should wait for it before proceeding, but that's redundant. Proceed once we get all N/2 falses = proceed once we get N/2 unique messages). To solve this, the final insight is that nodes can measure the clock times of its neighbor nodes. \exists a function COMPARE_i(node_i clock, incoming_j clock) = (slower, same, faster) that runs in O(1) node_i cycles. With this information, a node can flood the network with these boolean comparisons, and each node keeps a local copy of a directed graph of node clock speeds. Assume every node knows the base topology of the network (but not other clock times). Each node can do a topological sort. In O(N) node_i cycles, each node i must get the map of all faster parents and their parents (since all these other clock nodes are faster than node i). It doesn't necessarily get a map of the slow nodes. Finally, a node can compare clock times with a sibling, if the sibling forwards clock signals through its (faster) parent (something something nyquist freq??). Because the parent is faster, it should preserve granularity as if the siblings were directly sending messages to each other. Because siblings can therefore also compare clocks (through forwarding), each node_i can construct an upside down tree of synchrony in O(n^2), mayble less, cycles of f_i. The node at the bottom/root of the tree is the slowest. If the node has M >= N/2 subtree, then return True. The node where M=N/2 + 1 is unique. The question is, does this accomplish more than just waiting for N/2 + 1 messages. - no - but can alter topology (change speeds of clocks) more optimally, discover bottlenecks - for nice networks, can wait for more than half for slightly slower runtime - look at ring networks. Can look at best case and worst case topologies. - if we have this base synchrony graph, we can say "oh! it tolerates only 1 malicious snip!" You can do a min-cut on this graph. (e.g. ring network with one faulty process. Where do we cut? Clearly in the middle.) - So adversaries are actually relevant here. Q: Given a topology: How synchronous is it? How much asynchrony can it tolerate for a majority algorithm? Err.... Presenting: Start with a ring network. Let's say N nodes. N - 1 of them run with f = c. 1 of them has f = 0. Can I run a synchronous [N/2] algorithm with f = c? Yes. (this measures liveness). Next question: How much asynchrony does this network tolerate? Answer: it depends. If the asynchrony is totally malicious, (a snip that makes a node f = 0), the answer is none. How do we methodically evaluate the robustness of any network? Q: is this a graph of connectivity? Yes. To measure, we need to be able to connect to them. This isn't immediately clear though; what happens when you kill a node? Your synchrony graph will be out of date - may no longer be able to reach certain nodes... We can keep the old edges in, to maintain this.