Fast IP Hopping Protocol SDI Implementation

Background/Objectives: This paper suggests a new approach against Distributed Denial of Service attacks and traffic eavesdropping in TCP/IP networks. Methods/Statistical Analysis: In our method, DDoS resistance is achieved by introducing a new address policy in IP networks. This policy hides physical location of protected server for all unauthorized clients by dynamic mapping of server’s address on a large set of temporary addresses. This paper provides detailed description of the method and its mathematical model. Findings: The authors discuss basic implementation, its major practical constraints and results of initial validation. The proposed method is compatible with Software Defined Network and we discuss major possible advantages of IP Fast Hopping application in SDN. Applications/Improvements: The demonstrated technique suggests new addressing policy that based on randomizing of server’s address. This new addressing policy does not require any global significant changes in the existing Internet architecture and can be implemented as software solution on client and server ends without impact on transit infrastructure. Fast IP Hopping Protocol SDI Implementation Vladimir Krylov*, Kirill Kravtsov and Eleanora Sokolova Nizhny Novgorod State Technical University Named after RE Alekseev, Nizhny Novgorod, Russian Federation; vkrylov@heterarchica.com, kirill@kravtsov.biz, essokolowa@gmail.com

Introduction
In this article, we discuss security challenges in TCP/IP networks and, especially, Software Defined Networks. Such networks are vulnerable to various types of network attacks like traffic eavesdropping, IP Spoofing Attacks, Denial of Service etc 1 . The current study focuses on protection against Distributed Denial of Service attacks (and DoS attacks as a special case) and traffic eavesdropping. However, our method can be applied against other types of attacks when a male factor generates a separate data stream to a victim, also introduced technique increases confidentiality of communication session by hiding of destination of this session.
DDoS attack is one of the major threats to modern networks; the size and frequency of such a type of attacks continue growing despite the fact that quite a number of defense approaches were proposed. Such type of network attack, initiated against controller of software defined networks, can introduce a significant harm and prevent expected behavior of the whole network. During DDoS attacks, a number of malefactor terminals (botnet) and legitimate users are connected to the victim server at the same time. Each bot sends a big number of requests to the victim that create a heavy malicious traffic targeted to the server. Since the increase in the flow of requests is created here increase the number of terminals, therefore, whichever level of server performance has not been achieved, starting from a certain number of bots, they create a flow of requests exceeding the permissible level for any server. In related literature, a certain number of different classifications of DDoS detection and mitigation solutions are presented. According to various principles, they can be divided into groups: Based on the location of their deployment (source-based, network-based or destination-based) 2 , based on the type of the applied algorithm (statistical, knowledge-based, soft computing, data mining and machine learning methods 3 ) and, according to other principles, there are a couple of more groups to be found 4,5 .
However, generally, we can see that a greater part of existing DDoS protection mechanisms is based on a wide range of traffic analysis and filtering algorithms. They uses reactive strategy, where, on the first stage, a method analyses traffic, tries to detect active DDoS attack and after that filters malicious traffic. In these approaches, the network address of a node is a unique identifier of this node. Therefore, if a botnet initiates a traffic stream targeted to an address and there is no DDoS protection mechanism, this stream achieves victim node unchanged. We can say that DDoS solutions deal with a direct network tract between a set of sources and a victim terminal (receiver). In this paper, we describe an alternative approach: DDoS attacks resistance can be achieved via randomization of this tract by a specific addressing policy when a network address is only temporary conditional identifier of a victim server. This technique called convoluted multi address networks and is being discussed in the next paragraph. In this paper, we demonstrate a general approach of network address manipulation that lead to boosting robustness of networks and data against a wide range of different treats like DDoS attacks, traffic eavesdropping and analysis, etc.

A Model of Convoluted Multiaddress Networks
To demonstrate our network security method, consider a mathematical model of network traffic traversing with decomposition mapping of instantaneous traffic intensity from a network node with address x to network node with address y on three separate mappings: Mapping in(x, i) of an outgoing network traffic to network address space; automorphism m(n, R) of a network address space, where is n is delay in traffic traversing and R is a substitution function on a set of address pairs; mapping out(j, y) from a network address space to an incoming traffic ( Figure 1). Consider a matrix with a number of rows and columns, corresponding to the size of the address space of the network, as a model of the network address space. Elements a(t, i, j) of the matrix are the value of traffic intensity from address i to address j at moment t. . We call this solution is referred to as address hoping. There are two hopping functions -hopping of source hi(t, j) and hopping of receiver ho(t, j) . If these functions are equal, the commutativity of the diagram of mappings is also retained. Evidently, there are other possible mappings (which retain commutativity), but the abovementioned solutions are suffice for this study. Now, consider a case with multiple sources and one receiver. Taking into account the initial mapping for each pair source-receiver (x, y), it is easy to see that traffic intensity at network node y from multiple sources x ∈ X can be treated as an additive value: To protect a network described in the model from distributed denial of service and other types of network attacks with independent streams of malicious traffic, we should find an addressing policy which brakes additivity in Equation (1) in the following way: Traffic intensity from a particular ("legitimate") source x 1 is being transmitted to a particular receiver y without losses, but for all other sources x ∈ X x ≠ x 1 ,intensity of traffic targeted to node with address y will be attenuated in K times. We can see that this task has a solution using the following definitions of mappings: In fact, according to commutativity of the diagram of mappings, traffic from a legitimate source x 1 will be transmitted unchanged via the network. For all other sources x, traffic transmission will occur only at particular time moments when the values of hopping functions hi(t, j) and ho(t, j) match. Therefore, if such time moments do not exist, the traffic intensity from the corresponding source for receiver y will be equal to zero. If the values of hopping functions are equal at particular time moments, the network traffic from illegitimate sources will be transmitted to receiver y only at these moments. Average traffic attenuation is defined by the following expression: where |T m | is the cardinality of a set of time moments of message transmission, |T h | is the cardinality of a set of time moments when the values of the hopping function are equal. In this abstract model we shown that applying the special addressing policy in a network provides a way to attenuate or completely block malicious traffic in this network. Our approach does not contain analyzing and processing network traffic and, furthermore, is based only on an addressing policy applied in a particular network. In our work, networks, in which such a policy is implemented, are called convoluted multiaddress networks and the addressing policy itself -address hopping. The Convoluted multiaddress network technique is based on the following principle: A network address does not provide a unique identification of a particular network node. Instead, the system has a special set of mapping functions, which builds a dynamic dependence between a physical network node and an address with a set of parameters. As has been demonstrated above, the filtering ability of this method depends on the selected hopping function and the size of address space.

IP Fast Hopping
IP Fast Hopping technique 6,7 is intended to make the real destination of a client's communication invisible for all external terminals and, consequently, to prevent DDoS attacks and unauthorized access from illegitimate clients. IP Fast Hopping method is based on our model of convoluted multiaddress networks and is implementation of this model in TCP/IP networks. In the IP Fast Hopping approach, a server has a random IP address for each particular client at the each time moment. After this method has been applied, for an external observer close to a client, a communication session between the client and the server does no longer look like a packet stream between these two Internet terminals. Instead of this, an observer detects a packet flow between a client and a number of independent (topologically and physically) terminals in the Internet. None of the streams in this flow has a correlation between packets inside the stream.
IP Fast Hopping is similar to radio systems with frequency hopping. In such systems, a receiver and a transmitter are switching from one frequency to another frequency synchronously during an ongoing data transmission session. A malefactor's transmitter, which is going to introduce a noise into such a session, does not have an actual schedule of frequency hopping; therefore, such an attacker cannot do noticeable harm to the legitimate transmitter defended by the frequency hopping mechanism. In our case, frequency can be treated as an IP address. So, the legitimate client must know the schedule of the server's IP address changing. At the same time, the schedule should be unavailable to non-legitimate clients.

Abstract Model of IP Fast Hopping
To illustrate the basic idea of applying of convoluted multiaddress networks in TCP/IP networks, consider a system model, with a server with address s, a set of clients C = {c 1 , ..., c l }, a subset of network address space IP V = {ip 1 , ip 2 , ..., ip N } where s ∉ IP V and a set of gateways R = {r 1 , ..., r M } where M ≤ N. Each client c i ∈ C has a representation of server's address s: s¢ or "initial address". Each message a from whole set of messages A from the client c i to the server s is being transmitted via route p with input point p in (gateway) with address y and output point p out (gateway) with address x. In this model we can logically split the system on three independent addressing subsystems: 1. Subsystem (subnetwork) W 1 from the client c i to input point p in of the route p; 2. Subnetwork W 2 of the route p; 3. subnetwork W 3 from out point P out of the route p to the server s. When a message a is being transmitted through the particular subnetwork W z , a has a specific destination address IP dstW . Obviously, IP s dstW 1 = ', IP x dstW 2 = , IP s dstW 3 = To make entire system model consistent, each W z has a function F z that maps the destination address of a message a in the preceding W z -1 to a destination address in the current subnetwork W z (Figure 2).
In common client-server architecture of Internet networks, the destination address of message a is always equal to s, which means that P in = c i and x = s. So, our system model simplifies as shown in Figure 2. In this case, function F z is trivial and, thus, all messages from c i addressed to s¢ are being transmitted directly to server s.
In this case, an external observer can easily identify the address of traffic destination and initiate a malicious data stream to address s and this traffic achieves the physical server. Therefore, an unauthorized client can acquire access to the server. In addition, in these conditions, a set of malefactor terminals (botnet) B = {b 1 , ..., b k } can initiate a brute-force DDoS attack on address s ( Figure 3).
As has been reflected before, nowadays most of DDoS prevention techniques suggests installing firewalls and filtering solutions in a network between a set of clients C and victim server s. With reference to our model (Figure 1.), we can treat getaway P out as a firewall, which performs traffic analyzing and filtering according to one of existing defensive methods against DDoS attacks. Therefore, in these approaches, W 3 subsystem remains unprotected and is treated as trusted. Still, in terms of addressing policy the whole system remains transparent, i.e., all messages targeted to the server always have destination address equal to s. In this paper, it is suggested to conceal s in untrusted subsystems W 1 and W 2 in order to hide the location of a victim server and, as a result, prevent unauthorized access from illegitimate clients.
In IP Fast Hopping, s¢ = y and s is unavailable outside W 3 . Each client c i is connected to shared global network W 2 via security gateway P in . Due to the fact that s¢, c i local representation of server's address s, is equal to the address of this gateway, all messages a targeted to the server with address s will achieve this gateway. The packet a has a pair of keys that uniquely identify this message: 1) timestamp (message creation time) of a, t a , as a public key and 2) unique identification of the client-originator of this packet, ID c i , as a private key. The system model under consideration has a pseudo-random function H t ID n N a c i , ; ( ) = ∈    1 that determinates valid virtual address ip n of the server for particular message a. This function is regarded as a hopper function because of it defines the hopping of the IP address of the protected server in convoluted multiaddress networks. Due to the fact that unique identification of the client is part of the domain of function H, hopping of s can be different for different clients. These virtual addresses ip n are a representation of s in subnetwork IP V . Therefore,  (Figure 4). Gateway r m validates all incoming packets and maps destination address of these messages IP dst on address in W 3 using function F 3 (NB: Zero address means here that the message should be treated as malicious): The same rules are applied for the source address of all responses from the server to clients c i . As a result, a stream of messages between the server and clients are separated into independent streams between independent terminals in the network.

Implementation
IP Fast Hopping has a variety of possible implementations.
In this section, one of simplest approaches is described.
In such simple form of our method, the timestamp of TCP header of each packet is used as timestamp t a for hopper function H t ID a c i , ( ) . Also, unique identification ID c i of packets' client-originator ID c i is defined   during authorization. To make this approach consistent with other network protocols, DNS servers contains information about the address of an authorization server instead of address s of the protected server. In this case, our addressing rules do not change the existing network architecture or protocol except the fact that our technique requires adding several network terminals (getaways), which are responsible for calculation, validation and changing destination IP address of packets. This additional functionality can be added to network routers. Therefore, as example implementation, we implement IP Fast Hopping mechanism as kernel module of OS GNU/ Linux. In this case, installing of this module on GNU/ Linux-based routers would be enough to deploy the suggested system. Linux kernel contains built-in firewall Netfilter, which is responsible for packet filtering and forwarding according to predefined rules by iptables utility. Netfilter supports five hooks of rules: Prerouting, Input, Forward, Output, Postrouting. In the implementation suggested above, Netfilter contains a new module, which is responsible for changing of IP address into destination field of outgoing packets and into source field of ingoing packets. This module calculates a new IP address according to the IP Fast Hopping rules (by timestamp field and session UID). During a handshake, an authorization server adds new set of rules into Postrouting hook on a client's terminal and into Prerouting hook on each gateway. This rule activates the kernel module, which implements the following algorithm: On the client side this module calculates a • hash-function using the timestamps field and session UID for each outgoing packet addressed to the initial IP address. After that, the module uses this result as index of correct address into IP pool, which should be put into the destination field of the packet. For each ingoing packet from the same communication session, the module performs the same actions for the source address field: Checks the current value of the field (by calculating the same hash-function) and changes it on the initial address.
On the switches side this module calculates the same • hash-function using the timestamps field and session UID for each ingoing packet addressed to IP addresses from IP pool. If the current destination address corresponds to the timestamps field and session UID, the real IP address of the server will be placed into the destination field. Otherwise, the packet will be dropped. For all ingoing packets issued by the server, the module will replace the source field by one of virtual addresses according to the current value of the hash-function.

Initial Experimental Results
The described basic implementation of IP Fast Hopping approach has been validated on small test stand. The main purpose of our experiments is to show that IP Fast Hopping successfully filters traffic from unauthorized clients. To achieve this goal, we built test stand consisting of several Virtual Machines: Client, client's router and server router (both machines had implemented Netfilter module installed), authorization server, victim server and bot.
During the experiment, we measured the average traffic intensity at the server's network interface during active DoS attacks and without attack (see Figure 5). For generating DDoS attack we used third-party application, LOIQ. Easy to see, that even such minimal testing has shown that applying of IP Fast Hopping methods leads to filtering of malicious traffic stream from incoming traffic of a protected server.
Implementation of IP Fast Hopping in SDN does not require any significant changes in the suggested implementation. Software Defined Infrastructure is frequently based on GNU/Linux solution, so such basic implementation is compatible and easy to adopt. Furthermore, protected SDN controller may be utilized here to balance load between switches which perform validation of packets addresses. the dynamic change of a server's IP address. Server IP address is changed according to a pseudo-random law known only to authorized clients. In comparison with IP Fast Hopping method, the proposed technique contains the following major differences: The IP address of the victim is changed only during an active DDoS attack on the server; the new IP address is assigned for all client sessions simultaneously on a relatively long time (suggested period is around 5 minutes); accurate time synchronization is required for the calculation of each next IP address since external timestamp is used.
Another paper 9 suggests a Network Address Space Randomization (NASR) technique that is intended to protect enabled networks against hitlist worms. This method presupposes that an address from a global IP address space pool is randomly assigned and this randomization suggested to be performed on protected server directly. So, a basic form of NASR can be implemented by configuring the DHCP server to expire DHCP leases at particular intervals 10 . Therefore, the scope of NASR implementation is limited to local regions.

Conclusions
We described novel approach for increasing DDoS and traffic eavesdropping resistance of Software Defined Networks. Our theoretical and basic experimental analysis has shown that IP Fast Hopping filters malicious traffic from incoming traffic of a victim server. The demonstrated technique suggests new addressing policy that based on randomizing of server's address. However, this new addressing policy does not require any global significant changes in the existing Internet architecture and can be implemented as software solution on client and server ends without impact on transit infrastructure.

Acknowledgments
This work was supported by the Ministry of Education and Science of the Russian Federation (grant agreement №14.574.21.0034 from 06/17/2014, the unique identifier applied research RFMEFI57414X0034).

Practical Constraints
The model under discussion illustrates the basic idea of IP Fast Hopping mechanism and how this technique ensures hiding the destination of a client's traffic from external observers. The approach has a various possible implementations, each of them can have particular limitations, but in this section, we review basic constraints of our technique: I • f IP pool IP v is not large enough, a botnet can start an attack on each IP address using masquerading of malicious traffic as legitimate data stream by IP spoofing technique. In this case, gateways redirect part of hateful traffic together with legal traffic to a protected server. Therefore, the IP pool, which is used for IP Fast Hopping, should be large enough to make such an excessive attack way too consuming in terms of resources and inefficient for possible attackers. Obviously, the method will be more efficient in IPv6 systems. In this case, IP pool can contain a thousands of addresses related to a number of different routers in the Internet. The method is not session-less; because of the fact • that a client unique identification is part of a hopper function's domain. IP Fast Hopping requires clients' authorization since • a hopper function (especially its domain and codomain) should be available only to legitimate clients. Therefore, the protocol is not applicable for publicly available Internet resources. In addition, our approach does not provide any native ways for secure and DDoS-resistant client's authorization.

Related Work
Our method should not be confused with IP hopping. In IP hopping approach, the address of a victim server is changed directly after detection of a DDoS attack to make the physical terminal unavailable for malicious traffic. In this case, this sort of replacement will have a much more far-reaching effect and affect DNS server too. On this condition DDoS attack may be initiated to the domain name instead of IP address of a victim to avoid such protection mechanism.
In addition, the community suggested several DDoS mitigation solutions based on dynamic IP address changing and network space randomization. For example, the paper 8 introduces DDoS defense mechanism based on


Beyond the Hyperbole: Information Literacy Reconsidered

Information literacy, as a concept, has suffered from terminological confusion and has been burdened with untenable expectations. In addition, insufficient attention has been given to the place of information with the context of information behavior or information practices generally. Significant challenges remain to developing information literacy, but its value remains relevant.

Introduction
Information literacy has been lauded as a potential savior for multiple global challenges. The United Nations enumerates our primary, current global issues (http://www.un.org/en/globalissues/index.shtml), which include a range of challenges, from aging and climate change to environmental sustainability; human rights; peace and security; refugees; and terrorism. The United Nations Educational, Scientific, and Cultural Organization (UNESCO) makes significant claims about the key role of information literacy in addressing these challenges and achieving goals such as good government and democracy (2009). Such claims may excite librarians, who rightfully lay professional claim to information literacy expertise, but they place unmanageable burdens on information literacy as a concept. Information literacy remains elusive for much of the general population, and information literacy instruction is challenged by significant barriers to success. Before exploring these issues, this paper discusses the fundamental challenge of definition.

Conceptual Confusion
The concept of "information literacy" is troubled by terminological confusion and frequent messiness. In library and information science we use a very wide range of terms in this general topic area: information/digital/media/ICT/computer/ computational/technological/trans-/meta-literacy/fluency, among others. Although particular authors, organizations, or institutions will insist on specific and unique meanings for these terms, in practice they overlap in their meanings, and, importantly, are employed differently by different speakers, authors and agencies. Thus, understanding of a particular term's meaning, from any single perspective, requires careful investigation, and assumptions of mutual understanding are perilous. There is cachet in using the term "digital," so "digital literacy" is perhaps a term to be preferred, unless one wishes to include non-digital literacies. The concept of literacy itself has broadened in contemporary usage, from traditional notions of reading and writing, to a more expansive definition that includes a range of texts, written or otherwise. Thus, "text" refers to the traditional written word, recorded on paper or digitally, but also to a range of multi-media. In addition, competencies Julien Beyond the Hyperbole [ PERSPECTIVES ] 126 COMMUNICATIONS IN INFORMATION LITERACY | VOL. 10, NO. 2, 2016 with "text" have also expanded beyond traditional consumption to include interpretive and creative competencies. It is now well understood (in theory, if not reflected in practice), that these competencies are culturally situated within particular social conditions. So, literacy is meaning-making within a social, economic, political, technological (etc.) context (Hoechsmann & Poyntz, 2012). This meaning-making will, therefore, differ in profound ways for people of different ages and educational backgrounds in different cultural and economic circumstances, supported by different technological affordances.
From a pragmatic perspective, and particularly in the context of higher education, information literacy may be defined as the set of skills, knowledge, and attitudes required to access information effectively, efficiently, and ethically. More broadly, information literacy ought to include knowing how to interpret and evaluate information, and how to use it to make meaning across a range of contexts: in decision-making, in creative activities, in academic pursuits, in daily life, and in the workplace. Crucially, information literacy must go far beyond the narrow confines of competence with academic information sources, the traditional purview of those information literacy super-fans, academic librarians.

Burdens
In addition to terminological confusion, it is also important to recognize the immense burdens that we have placed on the term "information literacy" (and its synonyms). From the UNESCO perspective (UNESCO, 2009), media and information literacy (the preferred UNESCO term) is fundamental to freedom of expression and information, and empowers citizens to recognize how media and other information providers function. For UNESCO, media and information literacy supports the ability to critically evaluate information and to make informed decisions. UNESCO emphasizes citizens' dual roles as consumers and as producers of information and media. The expectations placed on this concept, however, are quite particular: for UNESCO, media and information literacy is essential to sustainable human development, participatory civic societies, sustainable world peace, freedom, democracy, good governance, and fostering of intercultural knowledge and mutual understanding. These goals are laudable but lofty, and they place a range of serious burdens-intellectual, political, and practical-on a concept such as information literacy.
While some of these claims may have merit, there is no doubt a significant element of hyperbole within them. When similar claims come from the lips of librarians, perhaps a

[ PERSPECTIVES ]
Julien Beyond the Hyperbole motivation for self-promotion or even self-preservation is palpable, for it is our community of practice, the community of librarians, which has most emphatically claimed ownership of information literacy. Deconstructing the motivations for those claims will be left to others, but the fact remains: we see ourselves at the forefront of these great goals when the notion of information literacy is invoked.

Information Practices
Although librarians like to "own" information literacy, the place of traditional approaches (that is, the standard introduction to information searching and evaluation that comprises the majority of "information literacy instruction" in academic libraries) merits attention. In particular, consultation of formal information sources (published materials) and rational searches reflect a relatively small proportion of information behavior (or information practices). The expertise of librarians typically lies in facility with formal information sources, and with efficient and rational approaches to information searching. However, it would be wise to contextualize information literacy within a larger context of information practices generally, since information literacy is really all about information practices. People's information practices are socially and culturally situated, mediated, and coconstructed with others in their social and cultural milieux. Thus, information practices are situated, social, and embodied. They are culturally and contextually bound, so information literacy therefore takes very different forms, depending on context. In addition, as we seek to develop information literacy skills in our clients, we need to remember that information seeking is a dynamic process-information needs may arise or dissipate quickly, and "need" is changeable. We ought not to assume simple, linear models of information seeking (Case, 2012;Cole, 2012).
Our information literacy instruction also needs to be informed about other aspects of information practices. For example, people tend to favor habitual practices, and very often act on the principles of convenience and efficiency, which strongly affect those information practices that librarians might call "ideal." We also know that source memory is fragile and easily confused. That is, people have a hard time recalling the source of "facts," of what they "know" to be true; thus, subjecting preconceived ideas or opinions to critical evaluation is a very tricky business. In other words, teaching people to evaluate information is not as straightforward as simply providing lists of evaluative criteria. "Education" of any kind does not work on a banking model; as Brenda Dervin noted decades ago, people's brains are not empty buckets into which we can toss "bricks" of useful information, such as information literacy skills (Dervin, 1983).

Human Nature
We also know that a significant driver of decision-making is social conformity, so that if one's neighbors are doing something, one is more inclined to do the same. This is important when considering what techniques will encourage behavior change-information literacy is a necessary but insufficient basis for change. More important is appealing to social norms; those are key to changing behavior.
So, my claim is that if we account for social conditions and context, for the complexity of information behavior or information practices in general, and for common cognitive confusions, this diversity of complications and limitations reduces significantly the potential claimed for information literacy to ameliorate social and political challenges.
We also need to keep in mind that while some level of information literacy may promote pro-social behaviors and attitudes, people balance meeting their own needs with a more altruistic focus on social benefits. We need to seriously ask whether we really expect that information literacy alone can shift that balance of attention towards the social good. Would a stronger grounding in information literacy change the attitudes and behaviors of terrorist extremists? Could enhanced information literacy alter violent worldviews? Or promote sustainable environmental practices? Unfortunately, it is quite common for perfectly well-educated, and information literate, individuals to hold beliefs that many other, equally well-educated and information literate individuals would abhor.

Challenges to Developing Information Literacy
We also need to understand how information literacy skills are developed. These skills are not developed through experience alone; this holds true especially for evaluation skills. Equally, effective and efficient information-finding skills take time and effort to learn. Information is organized in complex ways, and can be difficult to find and to evaluate. We recognize that, for most people, confidence in information skills exceeds actual skill level (Gross & Latham, 2012). Many people do not understand the context of information-how or why it is produced, nor the purposes for which different types of information are made available. Thus, critical evaluation is difficult. In addition, many people do not understand (or respect) ethical boundaries on using others' ideas and writing, relying on cut-and-paste techniques to bring disparate information together. Given this status quo, what can be done? Presumably, information literacy skills can be learned from teachers in school; however, there is ample evidence for the challenges associated with that goal, and the paucity of solid outcomes (Julien & Barker, 2009;Smith, DeLong, Given, Julien & Oullette, 2012). Many school teachers are not information literate themselves, and even when curricular mandates are in place, information literacy instruction is typically not tested, and so is given short shrift. Thus, students graduating from secondary school are not typically information literate. At the post-secondary level, information literacy instruction is often limited, or is unsystematic or poorly implemented. Similar concerns apply to opportunities at public libraries and other community centers, where typically few formal information literacy instruction opportunities are offered, and where librarians are not viewed as information literacy experts.
An ongoing challenge is that there are widely-held but unsupported beliefs about the information literacy skills of "digital natives," as well as inappropriate assumptions that experience with computing technologies without formal information literacy instruction will lead to information literacy. Another challenge is unfounded assumptions about the capacity of libraries to play significant roles in developing citizens' information literacy skills. Libraries often face severe resource challenges, library administrators may place relatively little emphasis on client training in information literacy, library patrons may lack confidence in the potential for librarians to contribute to information literacy training, and librarians are often poorly prepared for instructional work (Julien & Genuis, 2011). Typically, there is limited coordination between school teachers and librarians in public libraries and academic libraries, as well as insufficient numbers of teacher-librarians in schools. In many jurisdictions globally, librarian positions in schools have been eliminated entirely. Where potential exists for librarians across contexts to work together to develop community capacity in information literacy, actual cooperation or coordination is not the norm.

The True Potential for Information Literacy
As a scholar who has been thinking and teaching in the area of information literacy for over two decades, I am convinced that information literacy is critical to many important social phenomena, including positive health outcomes (of particular importance when so much health information is now obtained online), workforce development, and participative governance (since participatory citizenship is dependent upon relatively sophisticated information-finding skills). Increasingly, governments are delivering information and services online, and online only, which requires citizens to be at least minimally information literate in order to access that information. In addition, participation in the "commons" and in "civil society" depends on citizens' ability to find and evaluate information. Information literacy is also recognized as an essential competency for job performance, since information gathering, manipulation, and application are key work tasks. Those without good information literacy skills will be marginalized in private and public life, including employment.
In order to promote these positive outcomes, I propose that librarians need a solid understanding of information practices or information behavior, and the place of information literacy within that theory. This is the work of educators in library and information science, and curricula in these programs of study should graduate information professionals who are fully versed in that theory and its application in information service contexts. In addition, there is significant need for collaboration among all stakeholders, including funders and policy makers; libraries and librarians; schools and teachers; and parents. None of these entities can ensure development of information literacy alone: collaboration and participation from all these perspectives is needed to cultivate information literacy among citizens of all ages and backgrounds. Above all, what is needed is a sense of perspective. Information literacy is not a silver bullet to slay the world's ills, nor sufficient to achieve all of humankind's loftiest goals, but it is an important goal, and should remain on our practice and advocacy agendas.


extfieldsofstudy:
Mathematics
Computer Science

s2fieldsofstudy:
Computer Science
Mathematics

text:
Design of Dynamic Algorithms via Primal-Dual Method

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an $O(f^2)$-approximately optimal solution in $O(f \cdot \log (m+n))$ amortized update time, where $f$ is the maximum"frequency"of an element, $n$ is the number of sets, and $m$ is the maximum number of elements in the universe at any point in time. (2) For the dynamic $b$-matching problem, we maintain an $O(1)$-approximately optimal solution in $O(\log^3 n)$ amortized update time, where $n$ is the number of nodes in the graph.

Introduction
The primal-dual method lies at the heart of the design of algorithms for combinatorial optimization problems. The basic idea, contained in the "Hungarian Method" [16], was extended and formalized by Dantzig et al. [6] as a general framework for linear programming, and thus it became applicable to a large variety of problems. Few decades later, Bar-Yehuda et al. [2] were the first to apply the primal-dual method to the design of approximation algorithms. Subsequently, this paradigm was applied to obtain approximation algorithms for a wide collection of NP-hard problems [10,11]. When the primal-dual method is applied to approximation algorithms, an approximate solution to the problem and a feasible solution to the dual of an LP relaxation are constructed simultaneously, and the performance guarantee is proved by comparing the values of both solutions. The primal-dual method was also extended to online problems [5]. Here, the input is revealed only in parts, and an online algorithm is required to respond to each new input upon its arrival (without being able to see the future). The algorithm's performance is compared against the benchmark of an optimal omniscient algorithm that can view the entire input sequence in advance.
In this paper, we focus on dynamic algorithms for optimization problems. In the dynamic setting, the input of a problem is being changed via a sequence of updates, and after each update one is interested in maintaining the solution to the problem much faster than recomputing it from scratch. We remark that the dynamic and the online setting are completely different: in the dynamic scenario one is concerned more with guaranteeing fast (worst-case or amortized) update times rather than comparing the algorithms' performance against optimal offline algorithms. As a main contribution of this paper, we develop a dynamic version of the primal-dual method, thus opening up a completely new area of application of the primal-dual paradigm to 2 Maintaining a Fractional Hypergraph b-Matching in a Dynamic Setting

Preliminaries
We first define a linear program for fractional hypergraph b-matching (Definition 1.5). Next, we define the concept of a "λ-maximal" solution of this LP (Definition 2.1) and prove the approximation guarantee for such a solution (Theorem 2.2). Our main result is summarized in Theorem 2.3 and Corollary 2.4.
Below, we write a linear program for a fractional hypergraph b-matching.
We next define the concept of a "λ-maximal" solution. (1) is λ-maximal (for λ ≥ 1) iff for every edge e ∈ E with x(e) < µ, there is some node v ∈ V e such that e ′ ∈Ev x(e ′ ) ≥ c v /λ.

Theorem 2.2.
Let f ≥ max e∈E |V e | be an upper bound on the maximum possible "frequency" of an edge. Let OPT be the optimal objective value of LP (1). Any λ-maximal solution to LP (1) has an objective value that is at least OPT/(λf + 1).
Proof. Let {x * (e)} be a λ-maximal solution to the primal LP. Construct a dual solution {y * (v), z * (e)}, as follows. For every v ∈ V , set y * (v) = 1 if e∈Ev x * (e) ≥ c v /λ, and y * (v) = 0 otherwise. For every e ∈ E, set z * (e) = 1 if x * (e) = µ and z * (e) = 0 otherwise. Consider the dual constraint corresponding to any edge e ′ ∈ E. Since the primal solution {x * (e)} is λ-maximal, either x * (e) = µ or there is some v ′ ∈ V e ′ for which y * (v ′ ) = 1. In the former case we have z * (e) = 1, whereas in the latter case we have y * (v ′ ) = 1. Hence, the dual constraint under consideration is satisfied. This shows that the values {y * (v), z * (e)}, constitute a feasible dual solution. Next, we infer that: ≤ v∈V :y * (v)=1 λ · e∈Ev x * (e) + e∈E:z * (e)=1 x * (e) holds since each edge can be incident upon at most f nodes. Thus, we have constructed a feasible dual solution whose objective is at most (λf +1)-times the objective of the λ-maximal primal solution. The theorem now follows from weak duality.
Our main result is summarized below. For the rest of Section 2, we focus on proving Theorem 2.3. Theorem 2.3. We can maintain a (f + 1 + ǫf )-maximal solution to the dynamic fractional hypergraph b-matching problem in O(f · log(m + n)/ǫ 2 ) amortized update time.

The (α, β)-partition and its properties.
For the time being, we restrict ourselves to the static setting. Inspired by the primal-dual method for setcover, we consider the following algorithm for the fractional hypergraph b-matching problem.
• Consider an initial primal solution with x(e) ← 0 for all e ∈ E, and define F ← E.
• WHILE there is some primal constraint that is not tight: -Keep increasing the primal variables {x(e)}, e ∈ F , uniformly at the same rate till some primal constraint becomes tight. At that instant, "freeze" all the primal variables involved in that constraint and delete them from the set F , and set the corresponding dual variable to one.
In Figure 1, we define a variant of the above procedure that happens to be easier to maintain in a dynamic setting. The main idea is to discretize the continuous primal growth process. Define c min = min v∈V c v , and without any loss of generality, assume that c min > 0. Fix two parameters α, β > 1, and define L = ⌈log β (mµα/c min )⌉.
Claim 2.5. If we set x(e) ← µ · β −L for all e ∈ E, then we get a feasible primal solution.
Proof. Clearly, x(e) ≤ µ for all e ∈ E. Now, consider any node v ∈ V . We have e∈Ev Hence, all the primal constraints are satisfied. Our new algorithm is described in Figure 1. We initialize our primal solution by setting x(e) ← µβ −L for every edge e ∈ E, as per Claim 2.5. We call a node v nearly-tight if its corresponding primal constraint is tight within a factor of f αβ, and slack otherwise. Furthermore, we call an edge nearly-tight if it is incident upon some nearly tight node, and slack otherwise. Let V L ⊆ V and E L ⊆ E respectively denote the sets of nearly tight nodes and edges, immediately after the initialization step. The algorithm then performs L − 1 iterations.
At iteration i ∈ {L − 1, . . . , 1}, the algorithm increases the weight x(e) of every slack edge e by a factor of β. Since the total weight received by every slack node v (from its incident edges) never exceeds c v /(f αβ), this weight-increase step does not violate any primal constraint. The algorithm then defines V i (resp. E i ) to be the set of new nodes (resp. edges) that become nearly-tight due to this weight-increase step.
Finally, the algorithm defines V 0 (resp. E 0 ) to be the set of nodes (resp. edges) that are slack at the end of iteration i = 1. It terminates after increasing the weight of every edge in E 0 by a factor of β.
When the algorithm terminates, it is easy to check that for every node v ∈ V 0 . Furthermore, at the end of the algorithm, every edge e ∈ E \ E 0 is nearly-tight, and every edge e ∈ E 0 has weight x(e) = µ. We, therefore, reach the following conclusion.
Claim 2.6. The algorithm described in Figure 1 returns an (f αβ)-maximal solution to the fractional hypergraph b-matching problem with the additional property that c Our goal is to make a variant of the procedure in Figure 1 work in a dynamic setting. Towards this end, we introduce the concept of an (α, β)-partition (see Definition 2.7) satisfying a certain invariant (see Invariant 2.9). The reader is encouraged to notice the similarities between this construct and the output of the procedure in Figure 1.
Definition 2.7. An (α, β)-partition of the graph G partitions its node-set V into subsets V 0 . . . V L , where L = ⌈log β (mµα/c min )⌉ and α, β > 1. For i ∈ {0, . . . , L}, we identify the subset V i as the i th "level" of this partition, and call i the level ℓ(v) of a node v. We also define the level of each edge e ∈ E as ℓ(e) = max v∈Ve {ℓ(v)}, and assign a "weight" w(e) = µ · β −ℓ(e) to the edge e.
Given an (α, β)-partition, let E v (i) ⊆ E v denote the set of edges incident to v that are in the i th level, and let E v (i, j) ⊆ E v denote the set of edges incident to v whose levels are in the range [i, j].
Similarly, we define the notations D v and D v (i, j).
Given an (α, β)-partition, let W v = e∈Ev w(e) denote the total weight a node v ∈ V receives from the edges incident to it. We also define the notation W v (i). It gives the total weight the node v would receive from the edges incident to it, if the node v itself were to go to the i th level. Thus, we have W v = W v (ℓ(v)).
Since the weight of an edge e in the hierarchical partition is given by w(e) = µ · β −ℓ(e) , we derive the following equations for all nodes v ∈ V .
Proof. Fix any (α, β)-partition and any node v ∈ V . We prove the first part of the lemma as follows.
Fix any node v ∈ V , and focus on the value of W v (i) as we go down from the highest level i = L to the lowest level i = 0. Lemma 2.8 states that W v (i) ≤ c min /α when i = L, that W v (i) keeps increasing as we go down the levels one after another, and that W v (i) increases by at most a factor of β between consecutive levels.
We will maintain a specific type of (α, β)-partition, where each node is assigned to a level in a way that satisfies the following Invariant 2.9. This invariant is a relaxation of the bounds on e∈Ev x(e) for every node v stated in Claim 2.6. Proof. By Invariant 2.9, we have W v ≤ (f αβ) · c * v = c v for every node v ∈ V . Next, note that w(e) ≤ µ for every edge e ∈ E. Thus, the weights {w(e)}, e ∈ E, define a feasible solution to LP (1).
We claim that for every edge e ∈ E with w(e) < µ, there is some node v ∈ V e for which W v ≥ c v /(f αβ). This will imply that the weights {w(e)}, e ∈ E, form an (f αβ)-maximal feasible solution to the primal LP.

The algorithm: Handling the insertion/deletion of an edge.
We now show how to maintain an (α, β)-partition under edge insertions and deletions. A node is called dirty if it violates Invariant 2.9, and clean otherwise. At the beginning of the algorithm the edge-set E is empty, and, thus, every node is initially clean and at level zero. Now consider the time instant just prior to the t th update. By induction hypothesis, at this instant every node is clean. Then the t th update takes place, which inserts (resp. deletes) an edge e in E with weight w(e) = µβ −ℓ(e) . This increases (resp. decreases) the weights {W v }, v ∈ V e . Due to this change, the nodes v ∈ V e might become dirty. To recover from this, we call the subroutine in Figure 2, which works as follows Consider any node v ∈ V and suppose that In this event, the algorithm increments the level of the node. since α > 1, equation 17 implies that W v (L) < W v (ℓ(v)) and, hence, we have L > ℓ(v). In other words, when the procedure described in Figure 2 decides to increment the level of a dirty node v (Step 02), we know for sure that the current level of v is strictly less than L (the highest level in the (α, β)-partition).
Next, consider an edge e ∈ E v . If we change ℓ(v), then this may change the weight w(e), and this in turn may change the weights {W z }, z ∈ V e . Thus, a single iteration of the WHILE loop in Figure 2 may lead to some clean nodes becoming dirty, and some other dirty nodes becoming clean. If and when the WHILE loop terminates, however, we are guaranteed that every node is clean and that Invariant 2.9 holds.

Data structures.
We now describe the relevant data structures that will be used by our algorithm.
• We maintain for each node v ∈ V : • When the graph gets updated due to an edge insertion/deletion, we may discover that a node violates Invariant 2.9. Recall that such a node is called dirty, and we store the set of such nodes as a doubly linked list DIRTY-NODES. For every node v ∈ V , we maintain a bit STATUS[v] ∈ {dirty, clean} that indicates if the node is dirty or not. Every dirty node stores a pointer to its position in the list DIRTY-NODES.

• The collection of linked lists
} is denoted by the phrase "incidence lists of v". For every edge e ∈ E, we maintain a counter LEVEL[e] to keep track of ℓ(e). Furthermore, for every edge e ∈ E, we maintain |V e | bidirectional pointers corresponding to the nodes in V e . The pointer corresponding to a node v ∈ V e points to the position of e in the incidence lists of v. Using these pointers, we can update the incidence lists of the relevant nodes when the edge e is inserted into (resp. deleted from) the graph, or when some node v ∈ V e increases (resp. decreases) its level by one.

Bounding the amortized update time.
We devote this section to the proof of the following theorem.
The main idea is as follows. After an edge insertion or deletion the data structure can be updated in time O(1), plus the time to adjust the levels of the nodes, i.e., the time for procedure RECOVER. To bound the latter quantity we note that each time the level of an edge e ∈ E changes, we have to update at most f lists (one corresponding to each node v ∈ V e ). Hence, the time taken to update the lists is given by f · δ l , where δ l is the number of times the procedure in Figure 2 changes the level of an edge. Below, we show that Hence, to complete the proof of Theorem 2.11, we need to give an amortized bound on the number of times we have to change the level (or, equivalently, the weight) of an already existing edge. During a single iteration of the WHILE loop in Figure 2, this number is exactly D v (0, i) when node v goes from level i to level i + 1, and at most D v (0, i) when node v goes from level i to level i − 1.
Specifically, we devote the rest of this section to the proof of Theorem 2.12, which implies that on average we change the weights of O(L/ǫ) = O(log(m + n)/ǫ 2 ) edges per update in G. Theorem 2.12. Set α ← 1+ 1/f + 3ǫ and β ← 1+ ǫ. In the beginning, when G is an empty graph, initialize a counter COUNT ← 0. Subsequently, each time we change the weight of an already existing edge in the hierarchical partition, set COUNT ← COUNT + 1. Then COUNT = O(tL/ǫ) just after we handle the t th update in G.
Recall that the level of an edge e is defined as ℓ(e) = max v∈Ve (ℓ(v)). Consider the following thought experiment. We have a bank account, and initially, when there are no edges in the graph, the bank account has a balance of zero dollars. For each subsequent edge insertion/deletion, at most 3L/ǫ dollars are deposited to the bank account; and every time our algorithm changes the level of an already existing edge, one dollar is withdrawn from it. We show that the bank account never runs out of money, and this implies that COUNT = O(tL/ǫ) after t edge insertions/deletions starting from an empty graph.
Let B denote the total amount of money (or potential) in the bank account at the present moment. We keep track of B by distributing an ǫ-fraction of it among the nodes and the current set of edges in the graph.
In the above equation, the amount of money (or potential) associated with an edge e ∈ E is given by Φ(e), and the amount of money (or potential) associated with a node v ∈ V is given by Ψ(v). At every point in time, the potentials {Φ(e), Ψ(v)} will be determined by two invariants. But, before stating the invariants, we need to define the concepts of "active" and "passive" nodes. Definition 2.13. Consider any node v ∈ V . In the beginning, there is no edge incident upon the node v, and we initialize a counter κ v ← 0. Subsequently, whenever an edge-insertion occurs in the graph, if the inserted edge is incident upon v, then we set κ v ← κ v + 1. At any given time-step, we say that a node v ∈ V is active if µκ v ≥ c v and passive otherwise.
It is easy to check that if a node is active at time-step t, then it will remain active at every time-step t ′ > t. A further interesting consequence of the above definition is that a passive node is always at level zero, as shown in the lemma below.
Lemma 2.14. At any given time-step, if a node v ∈ V is passive, then we have ℓ(v) = 0.
Proof. We prove this by induction. Let ℓ (t) (v) and κ (t) v respectively denote the level of the node v and the value of the counter κ v at time-step t. Further, let W (t) v denote the value of W v at time-step t. Initially, at time-step t = 0, the graph is empty, we have W (0) v = 0, and hence ℓ (0) (v) = 0. Now, by induction hypothesis, suppose that at time-step t the node v is passive and ℓ (t) (v) = 0, and, furthermore, suppose that the node v remains passive at time-step (t + 1). Given this hypothesis, we claim that ℓ (t+1) (v) = 0. The lemma will follow if we can prove the claim.
To prove the claim, note that since the node v is passive at time- Since the node v has at most κ (t+1) v edges incident to it at time-step (t + 1), and since each of these edges has weight at most µ, we have W the node v can never become dirty during the execution of the procedure in Figure 2 after the edge insertion/deletion that occurs at time-step (t + 1). Thus, the node v will not change its level, and we will have ℓ (t+1) (v) = 0. This concludes the proof.
We are now ready to state the invariants that define edge and node potentials.
When the algorithm starts, the graph has zero edges, and all the nodes v ∈ V are passive and at level Consequently, equation 20 implies that B = 0. Theorem 2.12, therefore, will follow if we can prove the next two lemmas. Their proofs appear in Section 2.6 and Section 2.7 respectively. Lemma 2.17. Consider the insertion (resp. deletion) of an edge e in E. It creates (resp. destroys) the weight w(e) = µ · β −ℓ(e) , creates (resp. destroys) the potential Φ(e), and changes the potentials {Ψ(v)}, v ∈ V e . Due to these changes, the total potential B increases by at most 3L/ǫ. Figure 2, the total increase in COUNT is no more than the net decrease in the potential B.

Proof of Lemma 2.17.
Edge-insertion. Suppose that an edge e is inserted into the graph at time-step t. Then the potential Φ(e) is created and gets a value of at most (1 + ǫ)L units. Now, fix any node v ∈ V e , and consider three possible cases.
Case 1. The node v was passive at time-step (t − 1) and remains passive at time-step t. In this case, due to the edge-insertion, the potential Ψ(v) increases by β/ (f (β − 1)).
Case 2. The node v was passive at time-step (t − 1) and becomes active at time-step t. In this case, we must have: v . By Invariant 2.16, just before the insertion of the edge e we had: Since the node v was passive at time-step (t − 1), by Lemma 2.14 we infer that ℓ (t−1) (v) = 0. Hence, by Invariant 2.16, just after the insertion of the edge e we get: By equations 21, 22, the potential Ψ(v) increases by at most Case 3. The node v was active at time-step (t−1). In this case, clearly the node v remains active at time-step t, the weight W v increases, and hence the potential Ψ(v) can only decrease.

Edge-deletion.
If an edge e is deleted from E, then the potential Φ(e) is destroyed. The weight W v of each node v ∈ V e decreases by at most µ · β −ℓ(v) . Furthermore, no passive node becomes active due to this edge-deletion, and, in particular, the counter κ v remains unchanged for every node v ∈ V . Hence, each of the potentials The potentials of the remaining nodes and edges do not change. Since |V e | ≤ f , by equation 20, the net increase in B is at most 2L/ǫ ≤ 3L/ǫ.

Proof of Lemma 2.18.
Throughout this section, fix a single iteration of the WHILE loop in Figure 2 and suppose that it changes the level of a dirty node v by one unit. We use the superscript 0 (resp. 1) on a symbol to denote its state at the time instant immediately prior to (resp. after) that specific iteration of the WHILE loop. Further, we preface a symbol with δ to denote the net decrease in its value due to that iteration. For example, consider the potential B. We have B = B 0 immediately before the iteration begins, and B = B 1 immediately after iteration ends. We also have δB = B 0 − B 1 . A change in the level of node v does not affect the potentials of the edges e ∈ E \ E v . This observation, coupled with equation 20, gives us the following guarantee.
Remark. Since the node v is changing its level, it must be active. Hence, by Invariant 2.16, we must have We will use this observation multiple times throughout the rest of this section.
We divide the proof of Lemma 2.18 into two possible cases, depending upon whether the concerned iteration of the WHILE loop increments or decrements the level of v. The main approach to the proof remains the same in each case. We first give an upper bound on the increase in COUNT due to the iteration. Next, we separately lower bound each of the following quantities: δΨ(v), δΦ(e) for all e ∈ E v , and δΨ(u) for all u ∈ V \ {v}. Finally, applying equation 23, we derive that δB is sufficiently large to pay for the increase in COUNT.

Remark.
Note that ℓ 0 (u) = ℓ 1 (u) for all nodes u ∈ V \ {v}, and E 0 u = E 1 u for all nodes u ∈ V . Thus, we will use the symbols ℓ(u) and E u without any ambiguity for all such nodes.

Case 1:
The level of the node v increases from k to (k + 1).

Claim 2.21. We have COUNT
Proof. When the node v changes its level from k to (k + 1), this only affects the levels of those edges that are at level k or below.

Claim 2.24.
For every node u ∈ V \ {v}, we have: Proof. Consider any node u ∈ V \ {v}. If the node u is passive, then we have δΨ(u) = 0, and the claim is trivially true. Thus, for the rest of the proof we assume that the node u is active. Clearly, we have ℓ 0 (e) = ℓ 1 (e) for each edge e ∈ E u \ E v . Hence, we get δw(e) = 0 for each edge E u \ E v . Next, by Claim 2.20, we have ℓ 0 (e) = ℓ 1 (e) for each edge e ∈ E u ∩ E 0 v (k + 1, L). Thus, we get δw(e) = 0 for each edge e ∈ E u ∩ E 0 v (k + 1, L). We therefore conclude that: Using this observation, we infer that: Equation 24 holds since either |E u ∩ E 0 v (0, k)| = 0, or there is an edge e ∈ E u ∩ E 0 v (0, k). In the former case, equation 24 is trivially true. In the latter case, by Claim 2.19 we have ℓ 0 (e) = k, and since ℓ 0 (e) ≥ ℓ(u), we infer that ℓ(u) ≤ k and β ℓ(u)−k ≤ 1.

Claim 2.25. We have:
Proof. We have: Thus, Claim 2.21 implies that the net decrease in the potential B in no less than the increase in COUNT. This proves Lemma 2.18 for Case 1.  Proof. Consider any edge e ∈ E 0 v (0, k). Using the same argument as in the proof of Claim 2.19, we can show that ℓ 0 (e) = k. Since ℓ 0 (e) = k, we must have w 0 (e) = µβ −k .
The next claim bounds the degree D 0 v (0, k) of node v, which we then use in the following claim to bound the increase in COUNT.

Claim 2.27. We have
Proof. Since the node v decreases its level from k to (k−1), Step 04 ( Figure 2) ensures that . We conclude that: Proof. The node v decreases its level from k to k − 1. Due to this event, the level of an edge changes only if it belongs to E 0 v (0, k). Thus, we have Proof. Fix any node u ∈ V \ {v}. If the node u is passive, then we have δΨ(u) = 0, and the claim is trivially true. Thus, for the rest of the proof we assume that the node u is active.
We now partition the edge-set E v into two subsets, X and Y , according to the level of the other endpoint.
Proof. Fix any edge e ∈ E v . We consider two possible scenarios.
This concludes the proof of the Claim.
Next, we partition W 0 v into two parts: x and y. The first part denotes the contributions towards W 0 v by the edges e ∈ X, while the second part denotes the contribution towards W 0 v by the edges e ∈ Y . Note that X ⊆ E 0 v (0, k), which implies that x = e∈X w 0 (e) = µβ −k · |X|. Thus, we get the following equations. .

Proof. Equation 28 states that
Since ℓ 0 (v) = k, we get: As the node v decreases its level from k to k − 1, we have: Accordingly, we have W 1 v = β · x + y, which implies the following equation.
We now consider two possible scenarios depending upon the value of (f αc * v − βx − y). We show that in each case δB ≥ c * v β k /µ. This, along with Claim 2.28, implies that δB ≥ COUNT 1 − COUNT 0 . This proves Lemma 2.18 for Case 2.

Maintaining a Set-Cover in a Dynamic Setting
We first show the link between the fractional hypergraph b-matching and set-cover.

Lemma 3.1. The dual LP (4) is an LP-relaxation of the set-cover problem (Definition 1.1).
Proof. Given an instance of the set-cover problem, we create an instance of the hypergraph b-matching problem as follows. For each element u ∈ U create an edge e(u) ∈ E, and for each set S ∈ S, create a node v(S) ∈ V with cost c v(S) = c S . Ensure that an element u belongs to a set S iff e(u) ∈ E v(S) . Finally, set µ = max v∈V c v + 1.
Since µ > max v∈V c v , it can be shown that an optimal solution to the dual LP (4) will set z(e) = 0 for every edge e ∈ E. Thus, we can remove the variables {z(e)} from the constraints and the objective function of LP (4) to get a new LP with the same optimal objective value. This new LP is an LP-relaxation for the set-cover problem.
We now present the main result of this section.

Maintaining a b-Matching in a Dynamic Setting
We will present a dynamic algorithm for maintaining an O(1)-approximation to the maximum b-matching (see Definitions 1.3, 1.4). Our main result is summarized in Theorem 4.8. We use the following approach. First, we note that the fractional b-matching problem is a special case of the fractional hypergraph b-matching problem (see Definition 1.5) with f = 2 (for each edge is incident upon exactly two nodes). Hence, by Theorems 2.2 and 2.3, we can maintain a O(f 2 ) = O(1) approximate "fractional" solution to the maximum b-matching problem in O(f log(m + n)) = O(log n) amortized update time. Next, we perform randomized rounding on this fractional solution in the dynamic setting, whereby we select each edge in the solution with some probability that is determined by its fractional value. This leads to Theorem 4.8.
Notations. Let G = (V, E) be the input graph to the b-matching problem. Given any subset of edges E ′ ⊆ E and any node v ∈ V , let N (v, E ′ ) = {u ∈ V : (u, v) ∈ E ′ } denote the set of neighbors of v with respect to the edge-set E ′ , and let deg(v, E ′ ) = |N (v, E ′ )|. Next, consider any "weight" function w : E ′ → R + that assigns a weight w(e) to every edge e ∈ E ′ . For every node v ∈ V , we define ). Finally, for every subset of edges E ′ ⊆ E, we define w(E ′ ) = e∈E ′ w(e).
Recall that in the b-matching problem, we are given an "input graph" G = (V, E) with |V | = n nodes, where each node v ∈ V has a "capacity" c v ∈ {1, . . . , n}. We want to select a subset E ′ ⊆ E of edges of maximum size such that each node v has at most c v edges incident to it in E ′ . We will also be interested in "fractional" b-matchings. In the fractional b-matching problem, we want to assign a weight w(e) ∈ [0, 1] to every edge e ∈ E such that u∈N (v,E) w(u, v) ≤ c v for every node v ∈ V , and the sum of the edge-weights w(E) is maximized. In the dynamic version of these problems, the node-set V remains fixed, and at each time-step the edge-set E gets updated due to an edge insertion or deletion. We now show how to efficiently maintain an O(1)-approximate fractional b-matching in the dynamic setting.
Further, the size of the optimal b-matching in G is O(1) times the sum e∈E w(e).
Proof. Note that the fractional b-matching problem is a special case of fractional hypergraph b-matching where µ = 1, m = n 2 , and f = 2.
We scale down the capacity of each node v ∈ V by a factor of γ, by definingc v = c v /γ for all v ∈ V . Next, we apply Theorem 2.3 on the input simple graph G = (V, E) with µ = 1, m = n 2 , f = 2, and the reduced capacities {c v }, v ∈ V . Let {w(e)}, e ∈ E, be the resulting (f + 1 + ǫf )-maximal matching (see Definition 2.1). Since ǫ < 1/3 and f = 2, we have λ ≥ f + 1 + ǫf . Since ǫ is a constant, the amortized update time for maintaining the fractional b-matching becomes O(f · log(m + n)/ǫ 2 ) = O(log n). Finally, by Theorem 2.2, the fractional b-matching {w(e)} is an (λf + 1) = 9-approximate optimal b-matching in G in the presence of the reduced capacities {c v }. But scaling down the capacities reduces the objective of LP (1) by at most a factor of γ. Hence, the size of the optimal b-matching in G is at most 9γ = O(1) times the sum e∈E w(e). This concludes the proof.
Set λ = 4, γ = 1 + 4ǫ and ǫ ∈ (0, 1/4) for the rest of this section. We will show how to dynamically convert the fractional b-matching {w(e)} from Theorem 4.1 into an integral b-matching, by losing a constant factor in the approximation ratio. The main idea is to randomly sample the edges e ∈ E based on their w(e) values. But, first we introduce the following notations.
Say that a node v ∈ V is "nearly-tight" if W v ≥ c v /λ and "slack" otherwise. Let T denote the set of all nearly-tight nodes. We also partition of the node-set V into two subsets: B ⊆ V and S = V \ B. Each node v ∈ B is called "big" and has deg(v, E) ≥ c log n, for some large constant c > 1. Each node v ∈ S is called "small" and has deg(v, E) < c log n. Define E B = {(u, v) ∈ E : either u ∈ B or v ∈ B} to be the subset of edges with at least one endpoint in B, and let E S = {(u, v) ∈ E : either u ∈ S or v ∈ S} be the subset of edges with at least one endpoint in S. We define the subgraphs G B = (V, E B ) and G S = (V, E S ). Overview of our approach. Our algorithm maintains the following structures.  Pr[e ∈ H S ] = p e = min(1, w(e) · (cλ log n/ǫ)) ∀e ∈ E S .
The events {[e ∈ H S ]}, e ∈ E S , are mutually independent.
For each edge e ∈ H S , we have w S (e) = w(e) if p e ≥ 1; ǫ/(cλ log n) if p e < 1. (46) We define Z S (e) ∈ {0, 1} to be an indicator random variable that is set to one if e ∈ H S and zero otherwise.
. Then the following conditions hold with high probability.
The following conditions hold with high probability.
• For each node v ∈ S, we have deg(v, H S ) = O(log 2 n). Finally, since w : E → [0, 1] is a fractional b-matching in G, the set of edges E * is also a b-matching in G.
Proof. Consider any edge (u, v) ∈ E. If u / ∈ T and v / ∈ T , then by equation 39, we must have (u, v) ∈ E * . In contrast, if there is some node x ∈ {u, v} such that x ∈ T , then we must have either x ∈ B ∩ T or x ∈ S ∩ T .
In other words, every edge (u, v) satisfies this property: Either (u, v) ∈ E * , or it is incident upon some node in B ∩ T , or it is incident upon some node S ∩ T . Thus, each edge e ∈ E contributes at least w(e) to the sum w(E * ) + v∈B∩T W v + v∈S∩T W v . The lemma follows.

Case 2.
v∈B∩T W v ≥ (1/3) · w(E). In this case, we condition on the event under which Lemma 4.5 holds. Thus, we get: In this case, we condition on the event under which Lemma 4.6 holds. Thus, we get: The last inequality holds since M S is a maximal b-matching in G S (H) = (V, H S ), and since every maximal b-matching is a 2-approximation to the maximum fractional b-matching (this follows from LP duality). Accordingly, we have e∈H S w S (e) ≤ 2 · |M S |.
Since λ, ǫ are constants, this concludes the proof of Theorem 4.8.

Proof of Lemma 4.5 Lemma 4.12. With high probability, we have
and c v ≥ cλ log n/ǫ. Linearity of expectation, in conjunction with equations 41, 43 and Observation 4.2 imply that we have The lemma follows if we take a union bound over all nodes v ∈ B ∩ T . For the rest of the proof, suppose that v ∈ B. Applying an argument similar to the one used in the proof of Lemma 4.12, we infer that E[W B v ] = W v ≤ c v /γ. The last inequality holds due to equation 38. Since γ > (1 + ǫ) and c v ≥ cλ log n/ǫ, applying Chernoff bound we derive that W B v ≤ c v with high probability. Thus, for each node v ∈ V , we have W B v ≤ c v with high probability. The lemma now follows if we take a union bound over all nodes v ∈ B.
Finally, applying a similar argument we can show that for every big node v ∈ B, we have W S v ≤ c v with high probability.

Full Details
For every node v ∈ V , we partition the node-set N (v, E S ) into two subsets -X(v) and Y (v) -as defined below.
Next, for every node v ∈ V , we define: Since N (v, E S ) ⊆ N (v, E) for every node v ∈ V , by equation 38 we have: Since X(v) ⊆ N (v, E S ) and w S (u, v) = w(u, v) for every node u ∈ X(v), we get: Lemma 4.14. For every node v ∈ V , if δ Y (v) ≤ ǫ/λ, then with high probability, we have: w S (u, v) ≤ 2ǫ/λ.
To prove the second part of the lemma, we simply note that, as in the proof of Lemma 4.14, we have  Proof. Fix any node v ∈ V . Note that X(v) ⊆ N (v, H S ) and w(u, v) = w S (u, v) ≥ ǫ/(cλ log n) for every node u ∈ X(v). By equation 52, we have u∈X(v) w S (u, v) = δ X (v) for every node v ∈ V . Thus, we get: |X(v)| ≤ (cλ log n/ǫ) · δ X (v) = O ((log n/ǫ) · δ X (v)) (53)